23. Quick Sort (Tri Rapide) : La Stratégie du Pivot (Partie 1)

Le Quick Sort est l'algorithme de tri le plus largement utilisé en pratique. Comme le Merge Sort, il utilise le paradigme Diviser pour Régner.

Concept : Partitionnement

La clé du Quick Sort est l'opération de Partition. Elle repose sur le choix d'un élément pivot et le réarrangement du tableau de sorte que :

1. Tous les éléments plus petits que le pivot viennent avant lui.
2. Tous les éléments plus grands que le pivot viennent après lui.

Après le partitionnement, l'élément pivot est garanti d'être à sa position triée finale.

Étapes du Quick Sort

1. Choisir le Pivot : Sélectionner un élément (souvent le dernier ou un élément aléatoire).
2. Partitionner : Réorganiser le tableau autour du pivot.
3. Récurrence : Appliquer récursivement le Quick Sort au sous-tableau des éléments inférieurs au pivot et au sous-tableau des éléments supérieurs au pivot.