#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;
    int x=*t; *t=t[j], t[j]=x; // on échange t[0] et 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-1;j++)
    if(t[j]>t[j+1]) temp=t[j],t[j]=t[j+1],t[j+1]=temp;
  }
}
void tri_a_bulle3(int t[], int taille)
{ int i,j,temp;
  while(taille>1)
  { int k=0;
    for(j=0;j<taille-1;j++)
    if(t[j]>t[j+1]) temp=t[j],t[j]=t[j+1],t[j+1]=temp,k=j;
    taille=k+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_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. 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;
}