Le principe du tri rapide
Le tri rapide choisit un élément pivot, partitionne le tableau autour de ce pivot, puis applique récursivement l’algorithme aux sous-tableaux gauche et droit. Lorsque le pivot est toujours le premier élément, la logique reste simple mais peut devenir défavorable sur certains jeux de données.
Étapes du partitionnement
- Choisir le premier élément comme pivot.
- Placer les éléments inférieurs ou égaux au pivot à gauche.
- Placer les éléments supérieurs au pivot à droite.
- Positionner le pivot à sa place finale.
- Répéter le processus sur les deux sous-tableaux.
Exemple
Pour le tableau [7, 2, 1, 6, 8, 5, 3, 4], le pivot initial est 7. Après partitionnement, les éléments plus petits se retrouvent à gauche et les plus grands à droite. Le pivot 7 atteint sa position finale, puis le tri continue sur les deux parties.
Ce que la visualisation peut montrer
- La position du pivot.
- Les déplacements des pointeurs.
- Les échanges entre éléments.
- La formation des sous-tableaux.
- Les éléments déjà triés.
- L’avancement étape par étape.
Le problème du pivot initial
Si le tableau est déjà trié, choisir toujours le premier élément comme pivot conduit à des partitions très déséquilibrées. La complexité peut alors atteindre O(n²). La visualisation aide à comprendre ce comportement et à comparer avec d’autres stratégies, comme le choix aléatoire du pivot.