Quicksort est un tri diviser-pour-régner qui choisit un pivot, partitionne les éléments en ceux plus petits et plus grands, puis trie récursivement chaque côté. En moyenne O(n log n), pire cas O(n²).
Le partitionnement place le pivot à sa position finale triée ; tout ce qui est à gauche est plus petit, tout ce qui est à droite est plus grand. On récurse sur les deux côtés.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(Le partitionnement sur place est utilisé en pratique pour économiser de la mémoire.)
| Cas | Temps | Cause |
|---|---|---|
| Meilleur/Moyen | O(n log n) | partitions équilibrées |
| Pire | O(n²) | déjà trié avec mauvais pivot |
Le quicksort sur place utilise O(log n) d'espace pile.
Généralement le plus rapide en pratique grâce à la localité du cache et au faible surcoût, et il est sur place. Le pire cas O(n²) est évité avec un pivot aléatoire ou médiane-de-trois. Il n'est pas stable.
Quicksort est le tri par défaut dans nombreuses bibliothèques standard en raison de sa vitesse moyenne excellente et de son faible usage mémoire.
Comprendre pourquoi le choix du pivot provoque le pire cas O(n²) enseigne une leçon clé : le cas moyen et le pire cas peuvent diverger fortement.
C'est un sujet d'entretien favori précisément pour cette nuance.