Algorithmes Python

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.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

Des piles de livres au code
pivot = values[len(values) // 2]📕 Choisir un livre de référence
lower = [... if value < pivot]⬅️ Les livres plus petits à gauche
higher = [... if value > pivot]➡️ Les livres plus grands à droite
quick_sort(lower) + equal + quick_sort(higher)📚 Trier chaque côté, puis réunir les piles
Partitionnez autour d'un pivot, puis triez chaque côté de la même façon.
En une phrase

Le 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

  1. if len(values) <= 1: est le cas de base : une liste aussi courte est déjà triée.
  2. pivot = values[len(values) // 2] prend la valeur du milieu comme pivot.
  3. lower, equal et higher répartissent les valeurs autour du pivot ; equal garde les doublons ensemble.
  4. 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

Exécuter le code →
main.py
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]))
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Perdre les valeurs égales au pivot

Avec seulement < et >, les doublons du pivot disparaissent.

Problème
return quick_sort(lower) + [pivot] + quick_sort(higher)
Correction
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