#include<stdio.h>
#include<stdlib.h>
#include<time.h>
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;
}
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,0};
void test(int n, int j)
{ int t[n], i;
  for(i=n;i--;) t[i]=i;
  melange_aleatoire(t,n);
  for(;f[j];j++)
  { int u[n], 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)?"bon":"faux");
  }
}
int main()
{ srand(time(0));
  test(10,0);
  test(100,1);
  test(1000,1);
  test(10000,1);
  return 0;
}