#include<stdio.h>
#include<stdlib.h>
#include<time.h>

struct table
/* Pointeur vers un tableau d'entiers et taille du tableau */
{
   int *tableau;
   int taille;
};

typedef struct table Table;

/*****************************************************************************************/
/* Fonctions de manipulation de base des tables                                          */
/*****************************************************************************************/

Table *ALLOUER_TABLE(int longueur, int longueur_allouee)
/* Retourne un pointeur vers une Table de taille longueur_allouee, allouée dynamiquement */
/* Seules les longueur premières positions seront reconnues...*/
{
   if(longueur>longueur_allouee)
   {
      printf("Erreur d'allocation de longueurs!\n");
      return NULL;
   }
   Table *ptrtable;
   ptrtable=(Table*)malloc(sizeof(Table));
   ptrtable->tableau=(int*)malloc(longueur_allouee*sizeof(int));
   ptrtable->taille=longueur;
   return ptrtable;
}

void DESALLOUER_TABLE(Table *ptrtable)
/* Libere la place précédemment allouée */
{
   if(ptrtable==NULL) return;
   free(ptrtable->tableau);
   free(ptrtable);
}

void AFFECTER_TABLE(Table *ptrtable)
/* Lorsque la table est affectée, demande d'entrer le nombre convenable de valeurs */
{
   int i, valeur;
   if(ptrtable==NULL) return;
   printf("entrez %d valeurs.\n", ptrtable->taille);
   for(i=0;i<ptrtable->taille;i++)
   {
      printf("valeur suivante? ");
      scanf("%d",&valeur);
      ptrtable->tableau[i]=valeur;
   }
}

void GENERER_TABLE(Table *ptrtable)
/* Fabrique une table aléatoire de n entiers */
{
   int i;
   if(ptrtable==NULL) return;
   for(i=0;i<ptrtable->taille;i++) ptrtable->tableau[i]=rand()%2000;
}

void AFFICHER_TABLE(Table *ptrtable)
/* Affiche le contenu du champ tableau de la table */
{
   int i;
   if(ptrtable==NULL) return;
   for(i=0;i<ptrtable->taille;i++) printf("%d ",ptrtable->tableau[i]);
   printf("\n");
}

void ECHANGER(Table *ptrtable, int i, int j)
/* Echange les éléments d'indice i et j du tableau */
{
   int tempo;
   int longueur;
   if(ptrtable==NULL) return;
   longueur=ptrtable->taille;
   if((i>=longueur)||(j>=longueur)) return;
   tempo=ptrtable->tableau[i];
   ptrtable->tableau[i]=ptrtable->tableau[j];
   ptrtable->tableau[j]=tempo;
}

/*****************************************************************************************/
/* Fonctions liées aux tas                                                               */
/*****************************************************************************************/

void ECHANGE_DESCENDANT(Table *ptrtable, int i)
/* Rétablit la condition APO à partir du noeud d'indice i vers les feuilles */
{
   int fils, n;
   if(ptrtable==NULL) return;
   n=ptrtable->taille;
   fils=2*i+1;
   if(fils>=n) return;
   if((fils<n-1)&&(ptrtable->tableau[fils]<ptrtable->tableau[fils+1])) fils=fils+1;
   if(ptrtable->tableau[i]<ptrtable->tableau[fils])
   {
      ECHANGER(ptrtable,i,fils);
      ECHANGE_DESCENDANT(ptrtable, fils);
   }
}

void ECHANGE_MONTANT(Table *ptrtable, int i)
/* Rétablit la condition APO à partir du noeud d'indice i vers la racine */
{
   int pere;
   if(ptrtable==NULL) return;
   if(i==0) return;
   pere=(i-1)/2;
   if(ptrtable->tableau[i]>ptrtable->tableau[pere])
   {
      ECHANGER(ptrtable,pere,i);
      ECHANGE_MONTANT(ptrtable, pere);
   }
}

void INSERER(Table *ptrtable, int k)
/* Insere une nouvelle étiquette dans un tas déjà existante */
/* ATTENTION : la taille allouée à la table doit être suffisante, sinon??? */
{
   if(ptrtable==NULL) return;
   ptrtable->tableau[ptrtable->taille]=k;
   ptrtable->taille++;
   ECHANGE_MONTANT(ptrtable, ptrtable->taille-1);
}


void FABRIQUER_TAS(Table *ptrtable)
/* Transforme sur place un tableau en tas par succession d'échanges descendants */
{
   int i;
   if(ptrtable==NULL) return;
   for(i=(ptrtable->taille)/2-1;i>=0;i--) ECHANGE_DESCENDANT(ptrtable, i);
}

void EXTRAIRE_RACINE(Table *ptrtable)
/* Extrait la racine du tas, la place en dernier et reconstitue un tas de taille plus petite */
{
   if(ptrtable==NULL) return;
   if (ptrtable->taille>1)
   {
      ECHANGER(ptrtable, 0, ptrtable->taille-1);
      ptrtable->taille--;
      ECHANGE_DESCENDANT(ptrtable,0);
   }
}

void TRIE_TAS(Table *ptrtable)
/* Réalise le tri sur place d'un tableau qui est déjà constitué en tas */
{
   int i, n;
   if(ptrtable==NULL) return;
   n=ptrtable->taille;
   for(i=1;i<n;i++)
   {
      ECHANGER(ptrtable, 0, ptrtable->taille-1);
      ptrtable->taille--;
      ECHANGE_DESCENDANT(ptrtable,0);
   }
   ptrtable->taille=n;
}


/*****************************************************************************************/
/* Les fonctions de tri                                                                  */
/*****************************************************************************************/
/* SELECTION                                                                             */
/*****************************************************************************************/

void TRI_SELECTION(Table *ptrtable)
/* Réalise le tri sur place par sélection */
{
   int i, j, n, min;
   n=ptrtable->taille;
   for(i=0;i<n-1;i++)
   {
      min=i;
      for(j=i+1;j<n;j++) if(ptrtable->tableau[j]<ptrtable->tableau[min]) min=j;
      ECHANGER(ptrtable, i, min);
   }
}

/*****************************************************************************************/
/* INSERTION                                                                             */
/*****************************************************************************************/

void TRI_INSERTION(Table *ptrtable)
/* Réalise le tri sur place par insertion */
{
   int i, k, n, temp;
   n=ptrtable->taille;
   for(i=1;i<n;i++)
   {
      k=i-1; temp=ptrtable->tableau[i];
      while((k>=0)&&(temp<ptrtable->tableau[k]))
      {
         ptrtable->tableau[k+1]=ptrtable->tableau[k]; k--;
      }
      ptrtable->tableau[k+1]=temp;
   }
}

/*****************************************************************************************/
/* BULLES                                                                                */
/*****************************************************************************************/

void TRI_BULLES(Table *ptrtable)
/* Réalise le tri sur place par bulles */
{
   int fini;
   int i, j, n;
   n=ptrtable->taille;
   fini=0;
   for(i=n;i>1;i--) if(fini==0)
   {
      fini=1;
      for(j=0;j<i-1;j++) if(ptrtable->tableau[j]>ptrtable->tableau[j+1])
      {
         ECHANGER(ptrtable, j, j+1);
         fini=0;
      }
   }
}

/*****************************************************************************************/
/* FUSION                                                                                */
/*****************************************************************************************/

void FUSION(Table *ptrtable, Table *ptr1, Table *ptr2)
/* Fusion de deux tables. On suppose que la taille de la grande est la somme des deux autres */
{
   int i, j, k, n1, n2, n;
   j=0; k=0; n1=ptr1->taille; n2=ptr2->taille; n=ptrtable->taille;
   for(i=0;i<n;i++)
   {
      if((j<n1)&&((k>=n2)||(ptr1->tableau[j]<=ptr2->tableau[k])))
      {
         ptrtable->tableau[i]=ptr1->tableau[j]; j++;
      }
      else
      {
         ptrtable->tableau[i]=ptr2->tableau[k]; k++;
      }
   }
}
void TRI_FUSION(Table *ptrtable)
/*Réalise le tri fusion, pas sur place... */
{
   int i, n1, n2, n;
   Table *ptr1, *ptr2;
   n=ptrtable->taille;
   if(n==1) return;
   n1=n/2; n2=n-n1;
   ptr1=ALLOUER_TABLE(n1,n1); ptr2=ALLOUER_TABLE(n2,n2);
   for(i=0;i<n1;i++) ptr1->tableau[i]=ptrtable->tableau[i];
   for(i=0;i<n2;i++) ptr2->tableau[i]=ptrtable->tableau[n1+i];
   TRI_FUSION(ptr1); TRI_FUSION(ptr2);
   FUSION(ptrtable, ptr1, ptr2);
   DESALLOUER_TABLE(ptr1);DESALLOUER_TABLE(ptr2);
}

/*****************************************************************************************/
/* TRI PAR TAS                                                                             */
/*****************************************************************************************/

void TRI_TAS(Table *ptrtable)
/* Réalise le tri par tas sur place */
{
   FABRIQUER_TAS(ptrtable);
   TRIE_TAS(ptrtable);
}

/*****************************************************************************************/
/* TRI RAPIDE                                                                            */
/*****************************************************************************************/

int PARTAGE(Table *ptrtable, int i, int j, int p)
/* Classe autour du pivot les éléments d'indices i à j */
{
   int g, d, pivot;
   g=i; d=j;
   ECHANGER(ptrtable, p, j);
   pivot=ptrtable->tableau[j];
   do
   {
      while(ptrtable->tableau[g]<pivot) g++;
      while((d>=g)&&(ptrtable->tableau[d]>=pivot)) d--;
      if(g<d)
      {
         ECHANGER(ptrtable, g, d);
         g++; d--;
      }
   }
   while(g<=d);
   ECHANGER(ptrtable, g, j);
   return g;
}

int choix(int i, int j)
/* Retourne un nombre aléatoire entre i et j */
{
   return i+rand()%(j-i);
}

void TR(Table *ptrtable, int i, int j)
/* Trie récursivement entre les indices i et j */
{
   int p, k;
   if(i>=j) return;
   p=choix(i,j);
   k=PARTAGE(ptrtable, i, j, p);
   TR(ptrtable, i, k-1); TR(ptrtable, k+1, j);
}

void TRI_RAPIDE(Table *ptrtable)
/* Réalise le tri rapide sur place */
{
   TR(ptrtable, 0, ptrtable->taille-1);
}

int main(void)
{
   Table *a;
   int i;
   unsigned long temps1, temps2;
   a=ALLOUER_TABLE(30000,30000);
/* Tri sélection */
   for(i=1;i<7;i++)
   {
      a->taille=5000*i;
      srand(1);
      GENERER_TABLE(a);
      printf("liste de taille %d :\n", a->taille);
      temps1=clock();
      TRI_SELECTION(a);
      temps2=clock();
      printf("tri selection : %ld ms\n",(temps2-temps1)/1000);
   }
/* Tri par insertion */
   for(i=1;i<7;i++)
   {
      a->taille=5000*i;
      srand(1);
      GENERER_TABLE(a);
      printf("liste de taille %d :\n", a->taille);
      temps1=clock();
      TRI_INSERTION(a);
      temps2=clock();
      printf("tri insertion : %ld ms\n",(temps2-temps1)/1000);
   }
/* Tri par bulles */
   for(i=1;i<7;i++)
   {
      a->taille=5000*i;
      srand(1);
      GENERER_TABLE(a);
      printf("liste de taille %d :\n", a->taille);
      temps1=clock();
      TRI_BULLES(a);
      temps2=clock();
      printf("tri par bulles : %ld ms\n",(temps2-temps1)/1000);
   }
/* Tri par tas */
   for(i=1;i<7;i++)
   {
      a->taille=5000*i;
      srand(1);
      GENERER_TABLE(a);
      printf("liste de taille %d :\n", a->taille);
      temps1=clock();
      TRI_TAS(a);
      temps2=clock();
      printf("tri par tas : %ld ms\n",(temps2-temps1)/1000);
   }
/* Tri fusion */
   for(i=1;i<7;i++)
   {
      a->taille=5000*i;
      srand(1);
      GENERER_TABLE(a);
      printf("liste de taille %d :\n", a->taille);
      temps1=clock();
      TRI_FUSION(a);
      temps2=clock();
      printf("tri fusion : %ld ms\n",(temps2-temps1)/1000);
   }
/* Tri rapide */
   for(i=1;i<7;i++)
   {
      a->taille=5000*i;
      srand(1);
      GENERER_TABLE(a);
      printf("liste de taille %d :\n", a->taille);
      temps1=clock();
      TRI_RAPIDE(a);
      temps2=clock();
      printf("tri rapide : %ld ms\n",(temps2-temps1)/1000);
   }


}