Programmer le tri rapide (quicksort) en Python pas à pas

Le tri rapide est l’algorithme de tri le plus enseigné, le plus implémenté, et celui dont les variantes habitent encore les bibliothèques standards modernes. Inventé par Tony Hoare en 1959, publié en juillet 1961 dans Communications of the ACM sous le numéro Algorithm 64 : Quicksort, il combine deux idées simples : choisir un pivot, et réorganiser le tableau en deux parts — les plus petits que le pivot d’un côté, les plus grands de l’autre. Ce tutoriel implémente quicksort en Python à partir de zéro, en passant par la partition de Lomuto, le choix du pivot aléatoire pour éviter le pire cas, la version itérative, et un test de bout en bout.

Pour la vue d’ensemble des structures de données et des algorithmes, lire d’abord le guide principal Algorithmes et structures de données : repères 2026 pour devs.

Prérequis

• Python 3.10 ou plus récent
• Compréhension des fonctions récursives, des indices de tableau et de la complexité (Big-O)
• Niveau attendu : intermédiaire
• Temps estimé : 60 minutes pour suivre, 2 heures pour expérimenter et instrumenter

Étape 1 — Comprendre le principe en 30 secondes

L’idée du quicksort est plus simple qu’on ne le craint. On choisit un élément du tableau, qu’on appelle le pivot. On réorganise le tableau pour que tous les éléments plus petits que le pivot soient à sa gauche, et tous les plus grands à sa droite. À ce stade, le pivot est à sa place définitive dans le tableau trié, même si tout autour est encore désordonné. On récurse ensuite sur les deux parts — gauche et droite — jusqu’à ce qu’on tombe sur des sous-tableaux de longueur 0 ou 1, qui sont triviaux.

La performance dépend entièrement du choix du pivot. Si le pivot tombe systématiquement sur le minimum ou le maximum, on découpe en deux parts de tailles 0 et n-1 — on retombe sur un comportement quadratique. Si le pivot est à chaque étape proche de la médiane, on coupe en deux parts à peu près égales et on obtient O(n log n) avec d’excellentes constantes. C’est cette tension entre cas moyen brillant et pire cas catastrophique qui rend l’analyse du quicksort intéressante, et qui justifie les variantes (pivot aléatoire, médiane de trois) qu’on verra plus loin.

Étape 2 — Implémenter la partition de Lomuto

La partition est le cœur du quicksort. La version la plus simple à comprendre, et celle qu’on enseigne en général en premier, s’appelle la partition de Lomuto. Elle prend trois paramètres : le tableau, l’indice de début lo et l’indice de fin hi. Elle utilise arr[hi] comme pivot, parcourt les éléments de lo à hi-1, et avance un curseur i chaque fois qu’elle trouve un élément plus petit ou égal au pivot. À la fin, elle place le pivot à sa position finale et renvoie cette position.

def partition(arr, lo, hi):
    """Partition de Lomuto. Pivot = arr[hi]. Renvoie l'index final du pivot."""
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

Le déroulement sur [3, 1, 4, 1, 5, 9, 2, 6] avec lo=0 et hi=7 produit, étape par étape : pivot=6, i démarre à -1. Les valeurs 3, 1, 4, 1, 5 sont toutes ≤ 6, donc i passe successivement à 0, 1, 2, 3, 4 sans modifier l’ordre. La valeur 9 est sautée. La valeur 2 est ≤ 6, i devient 5, on échange arr[5] (qui valait 9) avec arr[6] (qui valait 2), donnant [3, 1, 4, 1, 5, 2, 9, 6]. À la sortie de la boucle, on échange arr[6] et arr[7] : [3, 1, 4, 1, 5, 2, 6, 9]. La fonction renvoie 6, position définitive du pivot. Le 9 est plus grand que 6 et reste à droite, le 2 est plus petit et est passé à gauche — l’invariant tient.

Étape 3 — Récursion sur les deux moitiés

Une fois la partition écrite, le quicksort lui-même tient en quatre lignes. La fonction prend le tableau et les bornes courantes, lance la partition pour placer un pivot, puis se rappelle elle-même sur la part gauche (de lo à p-1) et sur la part droite (de p+1 à hi). Le cas de base est implicite : si lo >= hi, le sous-tableau a 0 ou 1 élément et on ne fait rien, ce qui termine la récursion.

def quicksort(arr, lo=0, hi=None):
    """Tri rapide récursif sur place. O(n log n) en moyenne."""
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

Le défaut hi=None permet d’appeler la fonction sans préciser les bornes la première fois : quicksort(arr) trie tout le tableau. Sur [3, 1, 4, 1, 5, 9, 2, 6], on déroule la partition de l’étape 2 (pivot 6 placé à l’index 6), puis on récurse sur [3, 1, 4, 1, 5, 2] (gauche) et [9] (droite, trivial). La récursion gauche choisit pivot 2, partitionne en [1, 1, 2, 3, 5, 4] avec pivot à l’index 2, puis récurse sur [1, 1] et [3, 5, 4]. Quelques niveaux plus tard, le tableau est entièrement trié : [1, 1, 2, 3, 4, 5, 6, 9].

Étape 4 — Pivot aléatoire pour éviter le pire cas

La version précédente prend toujours le dernier élément comme pivot. Sur un tableau déjà trié, ce choix est désastreux : le pivot est à chaque étape le maximum, la part gauche contient n-1 éléments et la part droite est vide. La récursion fait n niveaux, chacun coûtant n comparaisons, soit O(n²). Sur 100 000 éléments déjà triés, ça veut dire 10 milliards d’opérations — plusieurs heures. Pire, ça peut faire dépasser la limite de récursion par défaut de Python (1000 appels imbriqués) et lever une RecursionError.

import random

def quicksort_random(arr, lo=0, hi=None):
    """Tri rapide avec pivot aléatoire. Espérance O(n log n)
    quelle que soit l'entrée."""
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p_idx = random.randint(lo, hi)
        arr[p_idx], arr[hi] = arr[hi], arr[p_idx]
        p = partition(arr, lo, hi)
        quicksort_random(arr, lo, p - 1)
        quicksort_random(arr, p + 1, hi)

L’astuce est minimaliste : on tire un index aléatoire entre lo et hi, on échange l’élément correspondant avec le dernier (pour réutiliser la partition de Lomuto telle quelle), puis on partitionne. Avec un pivot aléatoire, la probabilité de tomber systématiquement sur le minimum ou le maximum tend vers zéro, et l’espérance de la complexité est en O(n log n) quelle que soit l’entrée. C’est ce que font la plupart des implémentations sérieuses, ou alors elles utilisent la médiane de trois (premier, milieu, dernier), qui donne le même résultat sans appel au générateur aléatoire.

Étape 5 — Version itérative pour éviter la pile d’appels

La version récursive est élégante mais consomme la pile d’appels Python. Sur un tableau de plusieurs millions d’éléments, même avec un bon pivot, la profondeur de récursion est de l’ordre de log₂(n) — environ 20 pour un million, sans risque. Mais sur certaines architectures embarquées ou dans des contextes où la pile est limitée, on préfère une version itérative qui simule la pile manuellement avec une liste.

def quicksort_iter(arr):
    """Tri rapide itératif avec pile explicite."""
    stack = [(0, len(arr) - 1)]
    while stack:
        lo, hi = stack.pop()
        if lo < hi:
            p_idx = random.randint(lo, hi)
            arr[p_idx], arr[hi] = arr[hi], arr[p_idx]
            p = partition(arr, lo, hi)
            # Empile la plus grande moitié en premier pour limiter la pile
            if p - lo > hi - p:
                stack.append((lo, p - 1))
                stack.append((p + 1, hi))
            else:
                stack.append((p + 1, hi))
                stack.append((lo, p - 1))

L’astuce du dépile-en-premier-la-petite-moitié garde la pile bornée à O(log n) même au pire cas. Cette optimisation est due à Sedgewick et figure dans toutes les implémentations professionnelles. Sans elle, un quicksort itératif sur un tableau dégénéré peut allouer une pile de taille O(n), ce qui ruine l’avantage par rapport à la récursion. Lancez la version itérative sur le même tableau de test que la version récursive : le résultat doit être strictement identique, parce que les deux explorent l’arbre de récursion dans un ordre différent mais accomplissent les mêmes opérations sur le tableau.

Étape 6 — Comparaison avec la fonction sorted intégrée

Pour mesurer ce que vaut votre quicksort, comparez-le à sorted() qui utilise Powersort (variante de Timsort) depuis Python 3.11. La comparaison demande un peu de méthode : prendre des tableaux de tailles variées, désordonnés aléatoirement, et chronométrer chaque tri sur les mêmes données. timeit ou time.perf_counter font l’affaire.

import time, random

def benchmark(n):
    base = [random.randint(0, n) for _ in range(n)]
    a = base.copy()
    b = base.copy()

    t0 = time.perf_counter()
    quicksort_random(a)
    t1 = time.perf_counter()

    t2 = time.perf_counter()
    b.sort()
    t3 = time.perf_counter()

    print(f"n={n:>7}  quicksort: {t1-t0:.4f}s  sorted (Powersort): {t3-t2:.4f}s")
    assert a == b

for n in (1_000, 10_000, 100_000):
    benchmark(n)

Sur une machine moderne, vous verrez votre quicksort prendre quelques dixièmes de seconde sur 100 000 éléments, et sorted() faire le même travail en quelques millisecondes — un facteur 50 à 100 d’écart. La différence vient de l’implémentation en C, des optimisations spécifiques aux séquences déjà ordonnées (Powersort détecte les runs) et de l’absence du coût de l’interpréteur Python par appel de fonction. C’est l’argument central pour ne jamais réécrire un tri en production : la stdlib gagnera toujours.

Étape 7 — Vérification

Un test de correction couvre les cas nominaux et plusieurs cas limites : tableau vide, tableau d’un élément, tableau déjà trié, tableau trié à l’envers, tableau avec doublons. Si toutes les assertions passent, l’implémentation est probablement correcte. Notez qu’on compare au résultat de sorted(), qui sert d’oracle de référence.

if __name__ == "__main__":
    cases = [
        [],
        [42],
        [1, 2, 3, 4, 5],
        [5, 4, 3, 2, 1],
        [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5],
        [random.randint(0, 1000) for _ in range(500)],
    ]
    for case in cases:
        a = case.copy()
        b = case.copy()
        quicksort_random(a)
        b.sort()
        assert a == b, f"échec sur {case}"

        c = case.copy()
        quicksort_iter(c)
        assert c == b, f"version itérative incorrecte sur {case}"

    print("Tous les tests passent.")

Lancez python quicksort.py et vous devez voir Tous les tests passent.. Si une assertion échoue, le message indique le tableau qui pose problème, ce qui suffit en général à isoler le bug. Les bugs classiques au démarrage sont : oubli de mettre à jour i + 1 dans le swap final de la partition, comparaison stricte là où il faut ≤ (sinon on boucle sur les doublons), ou inversion lo / hi dans un appel récursif.

Erreurs fréquentes

Erreur	Cause	Solution
RecursionError sur des tableaux moyens	Tableau déjà trié + pivot toujours arr[hi] → profondeur O(n)	Utiliser un pivot aléatoire ou la médiane de trois
Boucle infinie ou résultat non trié sur un tableau avec doublons	Comparaison < au lieu de <= dans la partition	Bien utiliser arr[j] <= pivot dans Lomuto
Tri lent sur des séquences déjà ordonnées	Quicksort n’exploite pas l’ordre existant comme Timsort/Powersort le font	Pour des données souvent presque triées, préférer sorted()
Stack overflow sur de très grands tableaux	Récursion à profondeur O(log n) avec n > 10⁹	Passer en version itérative avec pile explicite
Modifications inattendues du tableau d’entrée	Quicksort trie sur place	Si vous avez besoin de garder l’original, copier avec arr.copy() avant l’appel

Variantes utiles : Hoare, médiane de trois, introsort

La partition de Hoare, la version originale du papier de 1961, utilise deux indices qui se rejoignent au milieu et fait moins d’échanges que Lomuto sur les entrées avec beaucoup de doublons. Elle est légèrement plus performante mais plus délicate à implémenter correctement — les bornes d’arrêt sont sensibles. La médiane de trois remplace le pivot aléatoire par la médiane du premier, du milieu et du dernier élément ; ça donne en pratique un excellent pivot et évite l’appel au générateur aléatoire, qui n’est pas gratuit. C’est la stratégie utilisée par les implémentations C++ historiques de std::sort.

L’introsort, introduit par Musser en 1997 et utilisé par std::sort en C++ depuis longtemps, démarre en quicksort puis bascule en heapsort dès que la profondeur de récursion dépasse 2 log₂(n). Le quicksort fournit la rapidité moyenne, et le heapsort garantit le pire cas en O(n log n). C’est cet hybride qui rend les implémentations modernes robustes face aux entrées adverses et aux tableaux pathologiques. Python, avec Powersort, suit une logique différente (mergesort adaptatif) mais arrive à des garanties similaires par d’autres moyens.

Analyse mathématique : pourquoi O(n log n) en moyenne ?

L’argument informel suit l’arbre de récursion. Si le pivot tombe à chaque étape sur la médiane parfaite, on découpe en deux moitiés égales. La profondeur de l’arbre est log₂(n) et chaque niveau effectue n comparaisons (cumulé sur tous les sous-tableaux). Le travail total est donc n × log₂(n). En pratique, le pivot ne tombe jamais exactement sur la médiane, mais l’analyse probabiliste montre qu’avec un pivot aléatoire, l’espérance du nombre de comparaisons est de l’ordre de 2n ln(n) ≈ 1,39 × n log₂(n). Le facteur constant est petit, ce qui explique pourquoi quicksort bat de nombreux concurrents en pratique malgré la même classe asymptotique.

Le pire cas mérite qu’on s’y attarde. Si le pivot est systématiquement le plus grand ou le plus petit, l’arbre dégénère en peigne : un côté toujours vide, l’autre avec n-1 éléments. La profondeur devient n et le travail O(n²). Sur 10 000 éléments, c’est environ 100 millions d’opérations — une demi-seconde. Sur 100 000, c’est plusieurs minutes. C’est précisément ce que le pivot aléatoire ou la médiane de trois empêchent en distribuant les choix : un attaquant ne peut plus deviner à l’avance la séquence des pivots et fabriquer une entrée pathologique.

Stabilité et tri sur place

Un tri est dit stable s’il préserve l’ordre relatif des éléments égaux. Le quicksort tel que présenté ici n’est pas stable : deux éléments de même valeur peuvent se retrouver dans un ordre différent à la sortie, parce que les échanges de la partition ne respectent pas leur position d’origine. Cette propriété compte quand on trie selon plusieurs critères successifs (par nom, puis par date), où l’on souhaite que les enregistrements de même nom restent dans l’ordre fourni. sorted() en Python est stable, ce qui permet d’enchaîner plusieurs tris sans surprise.

Le quicksort présenté est aussi en place : il ne consomme que O(log n) d’espace supplémentaire sur la pile de récursion, sans allouer de tableau auxiliaire. Le tri fusion, par exemple, est stable mais nécessite O(n) de mémoire temporaire, ce qui peut peser sur des tableaux énormes. Cette tension stable-en-place est constante en algorithmique : on choisit selon le besoin dominant. Pour un service web qui trie des milliers de petites listes, la stabilité prime ; pour un batch sur un disque qui trie des milliards d’entiers, l’occupation mémoire prime.

Tutoriels suivants

• Implémenter le parcours BFS sur un graphe en Python — on quitte le tri pour les graphes, en gardant l’idée du parcours systématique d’une structure.
• Coder une table de hachage en Python étape par étape — structure complémentaire pour des recherches par clé en O(1) plutôt que par ordre.
• Implémenter une liste chaînée en Python étape par étape — à lire pour les bases sur la manipulation de pointeurs et les invariants.

Pour aller plus loin

• Retour au guide principal : Algorithmes et structures de données : repères 2026 pour devs
• CACM Vol. 4 (1961) — Algorithm 64 : Quicksort, par C.A.R. Hoare (article original)
• Wikipedia — Quicksort (analyse complète, variantes Lomuto et Hoare)
• Documentation officielle Python — module random
• Wikipedia — Introsort (Musser 1997, hybride quicksort + heapsort)
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (chapitre 7)
• Robert Sedgewick — Algorithms (4e édition, chapitre 2)