Le tri rapide

Le tri rapide - aussi appelé "tri de Hoare" (du nom de son inventeur Tony Hoare) ou "tri par segmentation" ou "tri des bijoutiers" ou, en anglais "quicksort" - est certainement l’algorithme de tri interne le plus efficace.

Le principe de ce tri est d’ordonner le vecteur T.(0)..T.(n) en cherchant dans celui-ci une clé pivot autour de laquelle réorganiser ses éléments. Il est souhaitable que le pivot soit aussi proche que possible de la clé relative à l’enregistrement central du vecteur, afin qu’il y ait à peu près autant d’éléments le précédant que le suivant, soit environ la moitié des éléments du tableau. Dans la pratique, comme dans la démo ci-dessous, on prend souvent le dernier élément du tableau.

On permute ceux-ci de façon à ce que pour un indice j particulier tous les éléments dont la clé est inférieure à pivot se trouvent dans T.(0)...T.(j) et tous ceux dont la clé est supérieure se trouvent dans T.(j+1)...T.(n). On place ensuite le pivot à la position j.

On applique ensuite le tri récursivement à, sur la partie dont les éléments sont inférieurs au pivot et sur la partie dont les éléments sont supérieurs au pivot.

L'animation ci-après détaille le fonctionnement du tri rapide. La partie traitée est surlignée en rose et l'élément pivot encadré en bleu. La ligne verticale bleue indique le "mur", la séparation entre les éléments plus petits que le pivot et ceux plus grands.

Démonstration du tri à rapide

  1. Procedure tri_rapide (tableau [1:n], gauche, droit )
  2. DEBUT
  3.   (* mur marque la separation entre les elements plus petits et ceux plus grands que pivot*)
  4.   mur ← gauche;
  5.   (* On prend comme pivot l element le plus a droite *)
  6.   pivot ← tableau[droit];  
  7.   placer a gauche de mur tout les elements plus petits
  8.   placer a droite de mur tout les element plus grands
  9.   (* On place correctement le pivot *)
  10.   placer le pivot a la place de mur
  11.   (* On poursuit par recursivite *)
  12.   SI (gauche<mur-1) ALORS tri_rapide(tableau,gauche,mur-1);
  13.   SI (mur+1<droit) ALORS tri_rapide(tableau,mur,droit);
  14. FIN;
  1. let rec tri_rapide = function
  2.   | [] -> []
  3.   | pivot::queue -> (* le pivot est le premier element de la liste *)
  4.       let plus_petit, plus_grand = List.partition ((>) pivot) queue in
  5.       (tri_rapide plus_petit) @ (pivot :: (tri_rapide  plus_grand));;
  1. PROCEDURE tri_rapide (var tableau : tab;  gauche, droit : integer );
  2. Var
  3.   mur,courant : integer;
  4.   tmp, pivot : integer;    
  5. BEGIN
  6.   (* mur marque la separation entre les elements plus petits et ceux plus grands que pivot*)
  7.   mur := gauche;
  8.   courant := gauche;
  9.   (* On prend comme pivot l element le plus a droite *)
  10.   pivot := tableau[droit];
  11.   REPEAT
  12.     IF (tableau[courant] <= pivot) then
  13.     BEGIN
  14.         IF mur <> courant THEN
  15.         BEGIN
  16.             tmp:=tableau[courant];
  17.             tableau[courant]:=tableau[mur];
  18.             tableau[mur]:=tmp;
  19.         END;
  20.         mur := mur + 1;
  21.     END;
  22.     courant := courant + 1;
  23.   UNTIL courant>droit;
  24.   (* On poursuit par recursivite *)
  25.   IF (gauche<mur-1) THEN tri_rapide(tableau,gauche,mur-1);
  26.   IF (mur+1<droit) THEN tri_rapide(tableau,mur,droit);
  27. END;
  1. def tri_rapide(tableau):
  2.     if not tableau:
  3.         return []
  4.     else:
  5.         pivot = tableau[-1]
  6.         plus_petit = [x for x in tableau     if x <  pivot]
  7.         plus_grand = [x for x in tableau[:-1] if x >= pivot]
  8.         return tri_rapide(plus_petit) + [pivot] + tri_rapide(plus_grand)
  1. void tri_rapide (int *tableau, int taille) {
  2.     int mur, courant, pivot, tmp;
  3.     if (taille < 2) return;
  4.     // On prend comme pivot l element le plus a droite
  5.     pivot = tableau[taille - 1];
  6.     mur  = courant = 0;
  7.     while (courant<taille) {
  8.         if (tableau[courant] <= pivot) {
  9.             if (mur != courant) {
  10.                 tmp=tableau[courant];
  11.                 tableau[courant]=tableau[mur];
  12.                 tableau[mur]=tmp;              
  13.             }
  14.             mur ++;
  15.         }
  16.         courant ++;
  17.     }
  18.     tri_rapide(tableau, mur - 1);
  19.     tri_rapide(tableau + mur - 1, taille - mur + 1);
  20. }

Dans le tri rapide, le choix du pivot est essentiel. Dans l’implémentation ci-dessus, on se contente de prendre l’élément situé gauche de la partie à diviser. Mais d’autres stratégies sont possibles.

Si on regarde le pire des cas, on se rend compte du problème que pause cet algorithme. Si le tableau à trier est organisé de telle manière que, à chaque itération, une des deux parties ne contient qu'un seul élement, alors sa complexité est polynomiale. Que l'on choisisse un pivot au milieu, à la fin ou au début de la partie à traiter ne change rien : il existera toujours un cas pour lequel ce tri est particulièrement inefficace.

On peut utiliser cette méthode pour résoudre le problème page précédente. Bien sûr, il s'agit là d'une démonstration. Personne de sensé ne coderait un tri rapide de cette manière.



 


Dans le pire des cas, c'est à dire si, à chaque niveau de la récursivité le découpage conduit à trier un sous-tableau de 1 élement et un sous-tableau contenant tout le reste, la complexité du tri rapide est en Θ(n2).

Par contre, dans le cas moyen, cet algorithme a une complexité en Θ(nlog n)

Le choix du pivot est déterminant pour l'efficacité de ce tri. Plusieurs options sont possibles :

  1. Choisir le premier élément du tableau
  2. Choisir le dernier élément du tableau
  3. Choisir un élément au hasard
  4. Choisir l'élément au milieu du tableau
  5. Trouver le pivot optimal en recherchant la médiane

Ces différentes options peuvent être testées avec l'application ci-dessous. Choisir la médiane comme pivot est bien entendu la solution optimale... sauf que, la recherche de cette médiane est elle-même coûteuse.

Recherche du pivot optimal pour le tri rapide
Pivot :
Taille donnéesPasseNombre comparaisonsNombre échangesTotal
000
Taille donnéesPasseNombre comparaisonsNombre échangesTotal
000
Taille donnéesPasseNombre comparaisonsNombre échangesTotal
000
Taille donnéesPasseNombre comparaisonsNombre échangesTotal
000
Taille donnéesPasseNombre comparaisonsNombre échangesTotal
000