Après le tri par sélection qui fait l’objet de l’article précédent, j’ai pensé qu’il serait intéressant de parler d’un autre algorithme qui est le tri dit “rapide” aussi appelé tri “pivot”. Cet algorithme a été inventé en 1961 par Charles Antony Richard Hoare, professeur émérite de l’université d’Oxford. Le tri rapide est en pratique l’un des algorithmes de tri les plus efficaces, avec une complexité en temps proportionnelle à n log n. Il est, de ce fait, l’un des algorithmes de tri les plus utilisés.
La méthode consiste à sélectionner un élément du tableau, appelé “pivot”, à sa place définitive, en permutant tous les autres éléments de telle sorte que tous ceux qui sont inférieurs au pivot soient placés à gauche de celui-ci, et les éléments supérieurs à droite. Cette opération s’appelle le partitionnement, on remarque que le partitionnement crée deux sous-tableaux, un tableau des éléments inférieurs et pivot, et un tableau des élément supérieurs. On répète récursivement l’opération de partitionnement sur ces sous-tableaux, jusqu’à ce que l’ensemble des éléments soient trié.
En pseudo-code, voilà comment est écrit l’algorithme de tri rapide:
partitionner(tableau T, entier premier, entier dernier, entier pivot)
échanger T[pivot] et T[dernier]
j := premier
pour i de premier à dernier - 1
si T[i] <= T[dernier] alors
échanger T[i] et T[j]
j := j + 1
échanger T[dernier] et T[j]
renvoyer j
tri_rapide(tableau T, entier premier, entier dernier)
si premier < dernier alors
pivot := choix_pivot(T, premier, dernier)
pivot := partitionner(T, premier, dernier, pivot)
tri_rapide(T, premier, pivot-1)
tri_rapide(T, pivot+1, dernier)
L’animation suivante permet de visualiser le fonctionnement du tri rapide. Les barres blanches représentent les valeurs du tableau. Lorsqu’une barre est rouge, c’est qu’elle est en train d’être comparée par l’algorithme pour rechercher le minimum. Lorsqu’une barre s’affiche en vert, c’est que le programme vérifie sa bonne position dans le tableau.
- Appuyez sur ‘Z’ pour accélérer l’animation
- Appuyez sur ‘S’ pour ralentir l’animation
- Appuyez sur ‘R’ pour redémarrer l’animation