#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/* On choisit un élément au hasard parmi les n éléments du tableau,
les n éléments étant équiprobables. On le met dans la dernière case,
en l'échangeant. Puis on mélange le sous tableau formé des n-1 premiers
éléments. De cette façon les n! permutations du tableau sont équiprobables.
*/
void melange_aleatoire(int *t, int n)
{ 
}
// Le tableau n'est pas trié quand il existe deux éléments consécutifs non triés.
int trie(int *t, int n)
{ 
}
// Tant que le tableau n'est pas trié, on le mélange aléatoirement.
void tri_aleatoire(int *t, int n)
{ }

// Pour i=1, 2, ..., n on compare et on échange éventuellement t[i-1] et t[i].
// Puis on recommence en remplaçant n par la dernière valeur de i pour laquelle on a fait un échange.
void tri_a_bulle(int *t, int n)
{ 
}

// On cherche la place du plus grand des n éléments du tableau. On l'échange avec le dernier.
// Puis on trie le sous tableau formé des n-1 premiers éléments, en diminuant n de 1 et en recommençant tout.
void tri_selection(int *t, int n)
{ 
}

void tri_insertion(int *t, int n)
{ 
}

void tri_denombrement(int *t, int n, int max)
{ 
}

/* L'écriture en binaire de -h s'obtient à partir de celle de h, en gardant tous les 0 du bas et le premier 1, et en complémentant les autres bits.
Donc h&-h est la plus grande puissance de 2 qui divise h.
Donc 729*729*729%(h/(h&-h)) est nul ssi h est le produit d'une puissance de 2 par une puissance de 3.
La procédure suivante prend donc les nombres de cette forme dans l'ordre décroissant.
Cette suite de pas proposée en 1971 par Pratt, accélère et simplifie l'algorithme de tri proposé en 1959 par Shell.
Dans l'algorithme de Shell, pour une suite de pas h décroissante on fait un tri par insertion sur chacune
des h sous-suites t[i], t[i+h], t[i+2*h] ... . Pour un pas h donné le temps maximal est donc de h(n/h)²=n²/h.
Avec une suite de pas formant une progression géométrique approximative, si deux pas consécutifs sont toujours premiers entre eux,
alors le temps de calcul global maximal est en O(n^1.5).
La suite de pas proposée par Pratt, contient beaucoup plus de pas : Log_2(n)xLog_3(n)/2=O((ln n)²) au lieu de O(ln n).
Mais pour chaque pas h le temps de calcul maximal est abaissé de n²/h à n, ce qui donne un temps global en O(n(ln n)²).
En effet un tableau h-trié (trié par pas de h) reste h-trié si on le trie pour un autre pas h'.
Donc par exemple lorsque l'on fait le tri final par pas de 1, le tableau est déjà 2-trié et 3-trié.
Si t[i]>t[i+1] alors ces deux nombres sont plus grands que tous les t[j] pour j<i et plus petit que tous les t[j] pour j>i+1.
Donc après les avoir échangés, ils sont à leur place définitive. 
Le 1-tri final peut donc se faire en O(n) par :
  pour tout i=1, 2, 3, ..., n-1 faire si t[i]<t[i-1] on échange ces 2 nombres.
De même le 18-tri se fait alors que le tableau est déjà 36-trié et 54-trié et peut donc se faire en O(n) par :
  pour tout i=18, 19, 20, ..., n-1 faire si t[i]<t[i-18] on échange ces 2 nombres.
*/
void tri_shell_pratt(int *t, int n)
{ 
}
// On écrit le nombre t[i] en base 256 : t[i]=c(i,0)+c(i,1)256+c(i,2)256²+...  avec 0<=c(i,j)<256.
void tri_radix(int *t, int n)
{ 
}

/* On écrira  while(t[f]>x) --f;  et non pas  while(f>d && t[f]>=x) --f;  car x=t[d] servira de sentinelle.
 Idem pour    while(t[d]<x) ++d;  et non pas  while(f>d && t[d]<=x) ++d;  car x=t[f] servira de sentinelle.
 De plus si par exemple tous les t[i] sont égaux (à x) alors les deux boucles while sont toujours faites 0 fois
 la boucle extrerne sera faite (f-d)/2 fois et la valeur rendue sera (d+f)/2 : La partition se fera en deux parties
 de longueurs à peu près égales. Le temps de calcul du tri rapide sera en O(n ln n).
 Avec   while(f>d && t[f]>=x) --f;  on aurait partition(t,d,f)=d et le temps du tri rapide serait en n².
*/
int partition(int *t, int d, int f)
{ int x=t[d];
  for(;;)
  { while(t[f]>x) --f;
// à compléter
  }
}
void tri_rapide(int *t, int d, int f)
{ 
}
void tri_rapi(int *t, int n) { tri_rapide(t,0,n-1); }

void fusion(int *t, int d, int m, int f)
{ f++, m++;   // après cela les deux parties commencent en t[d] et t[m] et leurs longueurs sont m-d et f-m. 
// à compléter
}
void tri_fusion(int *t, int d, int f)
{ 
}
void tri_fusi(int *t, int n) { tri_fusion(t,0,n-1); }

int Max=100;
void tri_denom(int *t, int n) { tri_denombrement(t,n,Max); }

void taleat(int *t, int n)
{ unsigned z=0;
  while(n--) z=~z*1234567, t[n]=z%(Max+1);
}
void afft(int *t, int n)
{ while(n--) printf(" %d",*t++); printf("\n"); }

void test_tris(int n, int max)
{ void (*f[])(int*,int)={tri_aleatoire,tri_a_bulle,tri_selection,tri_insertion,tri_shell_pratt,tri_fusi,tri_rapi,tri_radix,tri_denom,0};
  int t[n], i, d;
  Max=max;
  for(i=(n>10)+3*(n>10000);f[i];i++) taleat(t,n), d=clock(), f[i](t,n), d=clock()-d, printf("%2d  %6d %s",i,d,trie(t,n)?"":"non trie "), afft(t,n<10?n:10);
}
  
int main()
{ int n;
  test_tris(6,30);
  for(n=10;n<=1000000;n*=10) test_tris(n,n);
  return 0;
}