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

struct cellule
{
  int val;
  struct cellule *suiv;
};

typedef struct cellule Cellule;

typedef Cellule *Liste;

Liste SAISIR_LISTE(void) /* Saisie d'une liste de longueur quelconque */
{
   Liste ptrcell;
   int n;
   printf("nombre (0 pour arreter)? ");
   scanf("%d",&n);
   if(n==0) return NULL;
   ptrcell=(Liste)malloc(sizeof(Cellule));
   ptrcell->val=n;
   ptrcell->suiv=SAISIR_LISTE();
   return ptrcell;
}

Liste GENERER_LISTE(int n) /* Engendre une liste pseudo-aleatoire de longueur n */
{
   Liste ptrcell;
   if(n==0) return NULL;
   ptrcell=(Liste)malloc(sizeof(Cellule));
   ptrcell->val=rand()%2000;
   ptrcell->suiv=GENERER_LISTE(n-1);
   return ptrcell;
}


void AFFICHER_LISTE(Liste ptrcell) /* Affichage */
{
   if(ptrcell==NULL)printf("\n");
   else
   {
      printf("%d ", ptrcell->val);
      AFFICHER_LISTE(ptrcell->suiv);
   }
}

int LONGUEUR(Liste ptrcell) /* Retourne la longueur d'une liste */
{
   int longueur;
   if(ptrcell==NULL) return 0;
   longueur=1+LONGUEUR(ptrcell->suiv);
   return longueur;
}

Cellule *MINIMUM(Liste ptrcell) /* Retourne un pointeur vers la cellule ayant la plus petite valeur */
{
   Cellule *minimum;
   Cellule *suivant;
   minimum=ptrcell;
   suivant=ptrcell;
   while(suivant!=NULL)
   {
      if(suivant->val < minimum->val) minimum=suivant;
      suivant=suivant->suiv;
   }
   return minimum;
}

Liste FUSION_LISTES(Liste a, Liste b) /* Fusionne deux listes a et b
La fusion est effectuee sur place : a et b sont modifiees */
{
   Liste ptrcell;
   if(a==NULL) return b;
   if(b==NULL) return a;
   if(a->val < b->val)
   {
      ptrcell=a->suiv;
      a->suiv=FUSION_LISTES(ptrcell,b);
      return a;
   }
   else
   {
      ptrcell=b->suiv;
      b->suiv=FUSION_LISTES(ptrcell,a);
      return b;
   }
}

void COUPER_LISTE(Liste *a, Liste *b, Liste ptrcell, int u) /* Coupe une liste ptrcell en deux parties
La coupure est faite sur place : les listes resultantes pointent vers les segments de ptrcell */
{
   int i;
   Cellule *suivante;
   if(u==0)
   {
      *a=NULL;
      *b=ptrcell;
      return;
   }
   if(u>=LONGUEUR(ptrcell))
   {
      *a=ptrcell;
      *b=NULL;
      return;
   }
   suivante=ptrcell;
   for(i=1;i<u;i++)
   {
      suivante=suivante->suiv;
   }
   *a=ptrcell;
   *b=suivante->suiv;
   suivante->suiv=NULL;
   return;
}

/* Dans les fonctions suivantes, le tri est effectue sur place. La liste passee en parametre est
eventuellement modifiee */

/* tri par selection du minimum */
Liste TRI_SELECTION(Liste ptrcell)
{
   int tempo;
   Cellule *minimum;
   if(ptrcell==NULL) return NULL;
   minimum=MINIMUM(ptrcell);
   if(minimum->val<ptrcell->val)
   {
      tempo=ptrcell->val;
      ptrcell->val=minimum->val;
      minimum->val=tempo;
   }
   ptrcell->suiv=TRI_SELECTION(ptrcell->suiv);
   return ptrcell;
}


/* tri par bulles */
Liste TRI_BULLES(Liste ptrcell)
{
   int longueur;
   int i;
   int tempo;
   int continuer;
   Cellule *suivant;
   longueur=LONGUEUR(ptrcell);
   if(longueur<2) return ptrcell;
   do
   {
      continuer=0;
      suivant=ptrcell;
      for(i=1;i<longueur;i++)
      {
         if((suivant->val)>(suivant->suiv->val))
         {
            tempo=suivant->val;
            suivant->val=suivant->suiv->val;
            suivant->suiv->val=tempo;
            continuer=1;
         }
         suivant=suivant->suiv;
      }
      longueur--;
   }
   while(continuer==1);
   return ptrcell;
}

/* tri fusion */
Liste TRI_FUSION1(Liste ptrcell, int longueur)
{
   int u,v;
   Liste a,b;
   if(longueur==0) return NULL;
   if(longueur==1) return ptrcell;
   u=longueur/2;
   v=longueur-u;
   COUPER_LISTE(&a,&b,ptrcell,u);
   return FUSION_LISTES(TRI_FUSION1(a,u),TRI_FUSION1(b,v));
}


Liste TRI_FUSION(Liste ptrcell)
{
   return TRI_FUSION1(ptrcell, LONGUEUR(ptrcell));
}


int main(void)
{
   Liste a, b;
   int i, longueur;
   unsigned long temps1, temps2;
/*   printf("Saisir liste a\n"); */
/*   a=SAISIR_LISTE();*/
/*   AFFICHER_LISTE(a);*/
/*   printf("Saisir liste b\n");
   b=SAISIR_LISTE();
   AFFICHER_LISTE(b);
   COUPER_LISTE(&c,&d,a,7);
   AFFICHER_LISTE(c);
   AFFICHER_LISTE(d);*/

/* tri selection */
   for(i=1;i<5;i++)
   {
      longueur=5000*i;
      printf("liste de taille %d :\n", longueur);
      srand(1);
      a=GENERER_LISTE(longueur);
      temps1=clock();
      b=TRI_SELECTION(a);
      temps2=clock();
      printf("tri selection : %ld ms\n",(temps2-temps1)/1000);
   }
/* tri bulles */
   for(i=1;i<5;i++)
   {
      longueur=5000*i;
      printf("liste de taille %d :\n", longueur);
      srand(1);
      a=GENERER_LISTE(longueur);
      temps1=clock();
      b=TRI_BULLES(a);
      temps2=clock();
      printf("tri bulles : %ld ms\n",(temps2-temps1)/1000);
   }
/* tri fusion */
   for(i=1;i<11;i++)
   {
      longueur=5000*i;
      printf("liste de taille %d :\n", longueur);
      srand(1);
      a=GENERER_LISTE(longueur);
      temps1=clock();
      b=TRI_FUSION(a);
      temps2=clock();
      printf("tri fusion : %ld ms\n",(temps2-temps1)/1000);
   }

/*   AFFICHER_LISTE(b);*/
}