#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int teq(int *t,int *u,int n)
{ while(n--) if(*t++!=*u++) return 0;
  return 1;
}
int trie(int t[],int n)
{ while(--n>0) if(t[n]<t[n-1]) return 0;
  return 1;
}
void melange_aleatoire(int t[],int n)
{ for(;n>1;n--,t++)
  { int j=rand()%n, x=*t; *t=t[j], t[j]=x; } // on échange t[0] et la case aléatoire t[j]
}
void tri_aleatoire(int t[], int n)
{ while(!trie(t,n)) melange_aleatoire(t,n); }

void tri_a_bulle(int t[], int taille)
{ int i,j,temp;
  for(i=1;i<taille;i++)
   for(j=0;++j<taille;)
    if(t[j-1]>t[j])
     temp=t[j-1],t[j-1]=t[j],t[j]=temp;
}
void tri_a_bulle2(int t[], int taille)
{ int j,temp;
  for(;taille>1;taille--)
   for(j=0;++j<taille;)
    if(t[j-1]>t[j])
     temp=t[j-1],t[j-1]=t[j],t[j]=temp;
}
void tri_a_bulle3(int t[], int taille)
{ int j,k,temp;
  for(;taille>1;taille=k)
   for(j=k=0;++j<taille;)
    if(t[j-1]>t[j])
     temp=t[j-1],t[j-1]=t[j],t[k=j]=temp;
}
int *trav;
void fusion(int tab[],int d,int m,int f)
{ int /*t[f+1]*/ *t=trav, i=d, j=m+1, k=d;
  while(i<=m && j<=f)
   if(tab[i]<tab[j]) t[k++]=tab[i++];
   else              t[k++]=tab[j++];
  while(i<=m) t[k++]=tab[i++];
  while(j<=f) t[k++]=tab[j++];
  for(k=d;k<=f;k++) tab[k]=t[k];
}
void tri_fusion(int tab[], int d, int f)
{ if(d<f)
  { int m=(d+f)/2;
    tri_fusion(tab,d,m);
    tri_fusion(tab,m+1,f);
    fusion(tab,d,m,f);
  }
}
void tri_fus(int t[],int n) { tri_fusion(t,0,n-1);}
void Fusion1(int tab[],int m,int n)
{ int /*t[n]*/*t=trav, i=0, j=m, k=0;
  while(i<m && j<n)
   if(tab[i]<tab[j]) t[k++]=tab[i++];
   else              t[k++]=tab[j++];
  while(i<m) t[k++]=tab[i++];
//while(j<n) t[k++]=tab[j++];
//for(k=0;k<n;k++) tab[k]=t[k];
  while(k--) tab[k]=t[k];
}
void Fusion(int t[],int m,int n)
{ int /*u[m]*/*u=trav, i, j, k;
  for(i=0;i<m;i++) u[i]=t[i];
  for(i=k=0,j=m;i<m && j<n;)
   if(u[i]<t[j]) t[k++]=u[i++];
   else          t[k++]=t[j++];
  while(i<m) t[k++]=u[i++];
}
void tri_Fusion(int tab[], int n)
{ if(n>1)
  { int m=n/2;
    tri_Fusion(tab,m);
    tri_Fusion(tab+m,n-m);
    Fusion(tab,m,n);
  }
}
void tri_denombrement(int tab[], int taille, int max)
{ int i,j,k,*m=trav; // m[max+1]
  for(j=0;j<=max;j++) m[j]=0;
  for(i=0;i<taille;i++) m[tab[i]]++;
  for(i=j=0;j<=max;j++)
   for(k=0;k<m[j];k++) tab[i++]=j;
}
void tri_den(int t[], int n) { tri_denombrement(t,n,n-1); }
void tri_shell_pratt(int t[], int n)
{ int h,i,x;
  for(h=n;h>0;h--)
   if(729*729*729%(h/(h&-h))==0)  // si h est de la forme 2^i 3^j
    for(i=0;i+h<n;i++)
     if(t[i]>t[i+h])
	  x=t[i],t[i]=t[i+h],t[h+i]=x;
}
/* Dans partition et partition2 on peut évidemment utiliser d à la place de i et f à la place de j, en supprimant i=d; et en remplaçant j=f+1 par f++.
   Cela gagne deux variables, mais ne gagne pas de temps quand on compile avec -O3. De plus cela complique l'explication du fonctionnement de la procédure,
   car i devient la valeur courante de d et d devient la valeur initiale de d. 
*/
int partition(int t[], int d, int f)  // dans cette version le pivot est mis à sa place
{ int piv=t[d], i=d, j=f+1;
  for(;;)
  { while(t[--j]>piv) ;  // t[i]=piv  sert de sentinelle.
    if(i==j) return i;   // donc t[i]=piv
    t[i]=t[j], t[j]=piv; // On échange t[i] et t[j].
    while(t[++i]<piv) ;  // t[j]=piv  sert de sentinelle.
    if(i==j) return i;
    t[j]=t[i], t[i]=piv; // On échange t[i] et t[j].
  }
}
void tri_rapide(int t[],int d,int f)
{ while(d<f)
  { int p=partition(t,d,f);
    tri_rapide(t,d,p-1); d=p+1;  // on a remplacé if(d<f) par while(d<f) en remplaçant l'appel récursif terminal partition(t,p+1,f) par d=p+1
  }
}
void tri_rap(int t[],int n) { tri_rapide(t,0,n-1); }   
int partition2(int t[], int d, int f)  // dans cette version le pivot n'est pas mis à sa place
{ int pivot=t[d], i=d, j=f+1, x;
  for(;;)
  { while(t[--j]>pivot) ;
    if(i>=j) return j;    // si la boucle externe se fait une seule fois alors i=j=d donc [d..f] est coupé en [d] [d+1..f]. Sinon i>=d+1 et j<=f-1 et donc j>=i-1>=d
    x=t[i], t[i]=t[j], t[j]=x;      
    while(t[++i]<pivot) ;      // a priori on met plutôt cette ligne, 3 lignes plus haut en initialisant i=d-1.  cf https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
  }                            // mais alors sa première exécution est faite 0 fois et a pour seul effet de faire passer i de d-1 à d.
}
void quicksort(int t[],int d,int f)
{ while(d<f)
  { int p=partition2(t,d,f);
    quicksort(t,d,p); d=p+1;  // on a remplacé if(d<f) par while(d<f) en remplaçant l'appel récursif terminal partition(t,p+1,f) par d=p+1
  }
}
void quickso(int t[],int n) { quicksort(t,0,n-1); }
void aff(int t[], int n)
{ while(n--) printf("%d ",*t++); printf("\n"); }
void (*f[])(int[],int)={tri_aleatoire,tri_a_bulle,tri_a_bulle2,tri_a_bulle3,tri_shell_pratt,tri_fus,tri_Fusion,tri_rap,quickso,tri_den,0};
void test(int n, int j)
{ int i, *t=malloc(4*n*sizeof(*t)), *u=t+n, *v=u+n;
  trav=v+n;
  for(i=n;i--;) t[i]=i;
  if(0) melange_aleatoire(t,n);
  else for(i=n;i--;) t[i]=rand()%n;
  for(i=n;i--;) v[i]=t[i];
  tri_den(v,n);
  for(;f[j];j++)
  { int a=clock();
    for(i=n;i--;) u[i]=t[i];
    if(0) aff(u,n);
    f[j](u,n);
    if(0) aff(u,n);
    a=clock()-a;
    printf("Le tri %d de %d nombres dure %d microsecondes. Il est %s.\n",
      j,n,a,trie(u,n) && teq(u,v,n)?"bon":"faux");
  }
  free(t);
}
int main()
{ srand(time(0));
  test(10,0);
  test(100,1);
  test(1000,1);
  test(10000,1);
  test(100000,4);
  test(1000000,4);
  if(0) test(10000000,5);
  if(0) getchar();
  return 0;
}