Tri rapide.
Analyse
- partitionnement : Les éléments sont positionnés avant ou après un élément-pivot arbitraire
(étape en O(n) et en place mais non stable).
- pour chacun des sous-ensembles avant et après le pivot, on répète #1
Conception
Diviser pour rêgner.
Notes
- Complexité moyenne optimale de O(n log(n)) mais quadratique (O (n2)) au pire (pour l'éviter même si
peu probable, utiliser la variante Introsort)
- Moins bon sur données presque triées que le tri par insertion ou smoothsort.
- En place