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.
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 :
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.
Taille données | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|
0 | 0 | 0 |
Taille données | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|
0 | 0 | 0 |
Taille données | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|
0 | 0 | 0 |
Taille données | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|
0 | 0 | 0 |
Taille données | Passe | Nombre comparaisons | Nombre échanges | Total |
---|---|---|---|---|
0 | 0 | 0 |