D) Complexité :

Nous donnons les résultats classiques et connus mathématiquement (pour les démonstrations nous renvoyons aux ouvrages de R.Sedgewick & Aho-Ullman cités dans la bibliographie).
 
L'opération élémentaire choisie est la comparaison de deux cellules du tableau.

Comme tous les algorithmes  qui divisent et traitent le problème en sous-problèmes le nombre moyen de comparaisons est en O(n.log(n)) que l'on nomme complexité moyenne.

L'expérience pratique montre que cette complexité moyenne en O(n.log(n))  n'est atteinte que lorsque les pivots successifs divisent la liste en deux sous-listes de taille à peu près équivalente.

Dans le pire des cas (par exemple le pivot choisi est systématiquement à chaque fois la plus grande valeur) on montre que la complexité est en O(n²).

Comme la littérature a montré que ce tri était le meilleur connu en complexité, il a été proposé beaucoup d'améliorations permettant de choisir un pivot le meilleur possible, des combinaisons avec d'autres tris par insertion généralement,  si le tableau à trier est trop petit etc...
 
Ce tri est pour nous un excellent exemple illustrant la récursivité et en outre un exemple de tri en n.log(n).

 

E) Programme pascal :
 
program TriQuickSort;
const N = 10;  { Limite supérieure de tableau }
type TTab = array [0..N] of integer;   { TTab : Type Tableau }
var Tab : TTab ;
 
function Partition ( G , D : integer) : integer;
   var i , j : Integer;
       piv, temp  : integer;
begin
     i := G-1;
     j := D;
     piv := Tab[D];
     repeat
         repeat i := i+1 until Tab[i] >= piv;
         repeat j := j-1 until Tab[j] <= piv;
         temp :=Tab[i];
         Tab[i] :=Tab[j];
         Tab[j] :=temp;
     until j <= i;
     Tab[j] := Tab[i];
     Tab[i] := Tab[d];
     Tab[d] := temp;
     result := i;
end;{Partition}
procedure TriRapide( G, D : integer);
var i: Integer;
begin
   if D>G then
   begin
     i := Partition( G , D );
     TriRapide( G , i-1 );
     TriRapide( i+1 , D );
   end
end;{TriRapide}
procedure Initialisation(var Tab:TTab) ; 
{ Tirage aléatoire de N nombres de 1 à 100 }
var i : integer;  { i : Indice de tableau de N colonnes }
begin
  randomize;
  for i := 1 to N do
     Tab[i] := random(100);
  Tab[0] := -Maxint ; // la sentinelle
end;
procedure Impression(Tab:TTab) ; 
{ Affichage des N nombres dans les colonnes }
var i : integer;
begin
  writeln('------------------------');
  for i:= 1 to N do write(Tab[i] : 3, ' | ');
       writeln;
end;
begin
  Initialisation(Tab); 
  writeln('TRI RAPIDE');
  writeln;
  Impression(Tab);
  TriRapide( 1 , N );
  Impression(Tab);
  writeln('----------------------');
end.

Résultat de l'exécution du programme précédent :


 
 
 F) Classe Java (tableau d'entiers)

class  ApplicationTriQSort
 {
 static  int [] table  =  new  int [21]  ;  // le tableau à trier en attribut
 /*  Les cellules [0] et [20] contiennent 
     des sentinelles,
     Les cellules utiles vont de 1 è 19.
     (de 1 à table.length-2)
 */
 
  static void  impression  ( ) 
 {
   // Affichage sans les sentinelles
   int  n  =  table.length - 2 ;
  for (  int  i  =  1 ;  i <= n ;  i ++ ) 
    System.out.print ( table[i] + " , ");
   System.out.println ();
 }
 
 static void  initialisation   ( ) 
 {
   // remplissage aléatoire du tableau 
   int  n  =  table.length - 2 ;
  for( int  i  =  1 ;  i <= n ;  i ++ )  
    table[i]  =  ( int )( Math.random () * 100 );
   // Les sentinelles:
   table[0]  = - Integer.MAX_VALUE ;
   table[n + 1]  =  Integer.MAX_VALUE ;
 }
 
  // ----> Tri rapide :
 
  static  int  partition  ( int  G,  int  D  )
 {  // partition / Sedgewick /
   int  i, j, piv, temp ;
   piv  =  table[D] ;
   i  =  G - 1 ;
   j  =  D ;
  do
   {
    do
      i ++ ;  
    while ( table[i] < piv );
    do
      j -- ;  
    while ( table[j] > piv );
     temp  =  table[i] ;
     table[i]  =  table[j] ;
     table[j]  =  temp ;
   }
  while( j > i );
   table[j]  =  table[i] ;
   table[i]  =  table[D] ;
   table[D]  =  temp ;
  return  i ;
 }
 
 
 
 static void  QSort  ( int  G,  int  D  )
 {  // tri rapide, sous-programme récursif
   int  i ;
  if( D > G )
  {
    i  =  partition ( G,D );
    QSort ( G,i - 1 );
    QSort ( i + 1,D );
  }
 }
 
 public static void  main ( string[ ] args ) 
 {
   Initialisation  ( );
   int  n  =  table.length - 2 ;
   System.out.println ("Tableau initial :");
   Impression  ( );
   QSort ( 1,n );
   System.out.println ("Tableau une fois trié :");
   Impression  ( );
 }  
}