Overview
Le tri rapide choisit un pivot, partitionne le tableau en éléments plus petits/plus grands, puis trie chaque partie récursivement.
Analogy
Comme organiser des livres par taille : choisir un livre de référence, mettre les plus petits à gauche et les plus grands à droite, puis répéter.
Step-by-step
- Choisir un pivot (premier, dernier ou aléatoire)
- Partitionner les éléments < pivot à gauche, > pivot à droite
- Appliquer récursivement à chaque partition
- Cas de base : 0 ou 1 élément
Visual
[3,6,8,10,1,2,1]
pivot=1: [1,1] + 1 + [3,6,8,10,2]
→ continue récursivement
Common mistakes
- Mauvais choix de pivot cause O(n²) sur données triées
- Pas de cas de base pour 0/1 élément
Practice questions
- Implémente le tri rapide avec un pivot aléatoire
- Trace les appels de partition
Time
O(n log n) moyen, O(n²) pire cas