Le tri rapide (quick sort) en Python
Dans cette leçon, vous allez implémenter le tri rapide en partageant la liste autour d'un élément pivot.
Introduction
Le problème
Le tri rapide (quicksort) est l'une des méthodes de tri les plus utilisées, car il est rapide en moyenne et simple à écrire. Il montre une autre façon de découper un problème : au lieu de couper au milieu, couper autour d'une valeur choisie.
Imaginez-le ainsi
Le tri rapide, c'est comme trier des livres par hauteur autour d'un livre choisi. Mettez chaque livre plus petit sur la pile de gauche, chaque livre plus grand sur la pile de droite et les livres de même hauteur au milieu. Triez ensuite les piles de gauche et de droite de la même façon, puis rassemblez le tout.
pivot = values[len(values) // 2]📕 Choisir un livre de référencelower = [... if value < pivot]⬅️ Les livres plus petits à gauchehigher = [... if value > pivot]➡️ Les livres plus grands à droitequick_sort(lower) + equal + quick_sort(higher)📚 Trier chaque côté, puis réunir les pilesLe tri rapide choisit un pivot et sépare les autres éléments en deux groupes : les plus petits et les plus grands que lui. Il trie chaque groupe récursivement, puis réunit le tout. Il s'exécute en temps O(n log n) en moyenne.
Points clés
if len(values) <= 1:est le cas de base : une liste aussi courte est déjà triée.pivot = values[len(values) // 2]prend la valeur du milieu comme pivot.lower,equalethigherrépartissent les valeurs autour du pivot ;equalgarde les doublons ensemble.quick_sort(lower) + equal + quick_sort(higher)trie les deux côtés et réunit les trois listes.
Quand l’utiliser ?
- Apprendre le partitionnement et la récursivité.
- Le tri généraliste sur place dans les langages et bibliothèques (avec un choix de pivot soigné).
- Les problèmes de sélection comme trouver la médiane (quickselect utilise le même partitionnement).
Quand s'en passer
- Le code Python de tous les jours :
sorted()est plus rapide et stable. - Quand il faut une garantie dans le pire cas : avec de mauvais pivots, le tri rapide tombe en
O(n²), ce qui n'arrive jamais au tri fusion.
Visualisation de Le tri rapide (quick sort) en Python
O(n log n)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
Résultat de l’exécution
[1, 5, 7, 8, 9, 10]
Explication du code
Cette version facile à lire choisit l'élément du milieu comme pivot et crée trois listes, lower, equal et higher, avec des compréhensions de liste. Le résultat est l'assemblage de quick_sort(lower), equal et quick_sort(higher). La complexité moyenne est O(n log n), mais avec un pivot mal choisi, l'algorithme peut tomber à O(n²).
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Perdre les valeurs égales au pivot
Avec seulement < et >, les doublons du pivot disparaissent.
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
Tous les défis