Objectif : Ecrire un programme Java implémentant l'algorithme du tri rapide.
 

Spécifications de l’algorithme :
 

Global :Tab[min..max] tableau d'entier    fonction Partition( G , D : entier )  résultat : entier  Local : i , j ,  piv , temp : entier  début      piv  ¬  Tab[D];      i  ¬ G-1;      j  ¬ D;      repeter         repeter  i ¬  i+1 jusquà Tab[i] >= piv;         repeter  j ¬  j-1 jusquà Tab[j] <= piv;         temp ¬  Tab[i];         Tab[i] ¬  Tab[j];         Tab[j] ¬  temp      jusquà j <= i;      Tab[j] ¬  Tab[i];      Tab[i] ¬  Tab[d];      Tab[d] ¬  temp;      résultat ¬  i FinPartition Algorithme TriRapide( G  , D : entier ); Local :  i : entier  début  si D > G alors     i ¬ Partition( G , D );    TriRapide( G , i-1 );    TriRapide( i+1 , D );  Fsi FinTRiRapide

Implantation en Java

On ajoute deux sentinelles au tableau, une au début (minimum absolu) l'autre à la fin (maximum absolu). Ce qui se traduira en Java par la déclaration d'un tableau t[m], les cellules t[0] et t[m+1] contienenant les deux sentinelles, les cellules utiles allant alors de 1 à m.(de 1 à table.length-2)
 
 

Proposition de squelette de classe Java à implanter :
 

/*  les cellules [0] et [20] contiennent des sentinelles,      les cellules utiles vont de 1 à 19.(de 1 à table.length-2) */

Remonter 

---