04 — Le tri rapide (quicksort) et son pire cas

Ce que tu vas apprendre

• Le principe du tri rapide : pivot et partition
• Pourquoi il est en O(n log n) en moyenne
• Pourquoi son pire cas tombe à O(n²), et quand ça arrive
• Comment le choix du pivot change tout

Prérequis

• 03 — Tri par fusion

Le tri rapide est, comme son nom l'indique, l'un des tris les plus rapides en pratique, et le plus utilisé historiquement. C'est aussi une leçon importante sur la différence entre cas moyen et pire cas. Il est en O(n log n) la plupart du temps, mais peut dégénérer en O(n²) sur certaines entrées. Comprendre quand et pourquoi, c'est comprendre pourquoi on ne se fie pas qu'à la complexité moyenne.

Le principe : pivot et partition

Le tri rapide est aussi un diviser pour régner, mais il fait le travail dans l'autre sens que le tri par fusion. Au lieu de découper bêtement puis de fusionner intelligemment, il découpe intelligemment puis recombine sans rien faire.

1. Choisir un pivot : un élément du tableau.
2. Partitionner : réorganiser le tableau pour que tous les éléments plus petits que le pivot soient à sa gauche, et tous les plus grands à sa droite. Le pivot est alors à sa position finale.
3. Récursion : appliquer le même procédé à la sous-partie gauche et à la sous-partie droite.

Une fois les deux côtés triés, le tableau entier l'est, sans étape de fusion : le placement du pivot a fait le travail de regroupement.

pythondef tri_rapide(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]          # pivot = élément central
    gauche = [x for x in arr if x < pivot]
    milieu = [x for x in arr if x == pivot]
    droite = [x for x in arr if x > pivot]
    return tri_rapide(gauche) + milieu + tri_rapide(droite)

Cette version est lisible mais alloue des tableaux. La version classique partitionne en place, sans copie :

typescriptfunction triRapide(arr: number[], bas = 0, haut = arr.length - 1): number[] {
  if (bas < haut) {
    const p = partition(arr, bas, haut); // place le pivot, renvoie sa position
    triRapide(arr, bas, p - 1);
    triRapide(arr, p + 1, haut);
  }
  return arr;
}

function partition(arr: number[], bas: number, haut: number): number {
  const pivot = arr[haut];   // pivot = dernier élément
  let i = bas - 1;
  for (let j = bas; j < haut; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[haut]] = [arr[haut], arr[i + 1]];
  return i + 1;
}

Pourquoi rapide en moyenne

Si le pivot tombe à peu près au milieu des valeurs, il divise le tableau en deux moitiés équilibrées. On retrouve alors la même structure que le tri par fusion : log n niveaux de découpage, n opérations de partition par niveau, donc O(n log n). En pratique, sur des données aléatoires, c'est ce qui se passe, et le tri rapide est même souvent plus rapide que le tri par fusion grâce au partitionnement en place, qui économise les allocations et exploite bien le cache du processeur.

Le pire cas : O(n²)

Le problème surgit quand le pivot est systématiquement le plus petit ou le plus grand élément. La partition produit alors un côté vide et un côté de taille n - 1. Au lieu de diviser par deux, on retire un seul élément à chaque niveau. Il faut n niveaux, chacun en O(n), soit O(n²).

Quand est-ce que ça arrive ? Avec la version naïve qui prend le dernier élément comme pivot, le pire cas est un tableau déjà trié ou trié à l'envers. C'est cruel : l'entrée la plus favorable pour d'autres tris est la pire pour celui-ci. C'est aussi une faille de sécurité connue : un attaquant qui contrôle l'entrée peut forcer le pire cas et provoquer un déni de service (attaque par complexité algorithmique).

Bien choisir le pivot

Tout l'art du tri rapide tient dans le choix du pivot, pour rendre le pire cas improbable.

• Pivot aléatoire : choisir le pivot au hasard. Le pire cas devient statistiquement négligeable, même sur une entrée triée. C'est la parade la plus simple et la plus robuste.
• Médiane de trois : prendre la médiane du premier, du milieu et du dernier élément. Bon compromis, et c'est ce que font beaucoup d'implémentations réelles.
• Introsort : surveiller la profondeur de récursion et basculer sur un tri par tas (article suivant) si elle dépasse une limite. On garantit ainsi O(n log n) dans le pire cas tout en gardant la vitesse du tri rapide en moyenne. C'est l'algorithme du std::sort du C++.

Le tri rapide est aussi instable par défaut, à cause des échanges à distance pendant la partition. Quand la stabilité compte, on lui préfère le tri par fusion ou Timsort.

L'article suivant présente le tri par tas, qui garantit O(n log n) dans tous les cas en s'appuyant sur une structure de données qu'on reverra : le tas binaire.

Sources

• Videau, M., & Eck, D. (2004). Les algorithmes de tri. Interstices. interstices.info/les-algorithmes-de-tri/
• Hoare, C. A. R. (1962). Quicksort. The Computer Journal, 5(1). (Paper original)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 7 "Quicksort". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 2.3 "Quicksort". Addison-Wesley.
• Crosby, S. A., & Wallach, D. S. (2003). Denial of Service via Algorithmic Complexity Attacks. USENIX Security. (Le pire cas exploité comme attaque)