Tris efficaces

En 1959, un étudiant britannique de vingt-quatre ans en séjour à Moscou travaille sur un projet de traduction automatique. Il doit trier les mots d'une phrase pour les chercher dans un dictionnaire, et le tri par insertion qu'il a sous la main est trop lent. Tony Hoare invente alors une idée qui tient en une phrase : choisir un mot au hasard, mettre à gauche tous ceux qui le précèdent dans l'alphabet, à droite tous les autres, et recommencer sur chaque moitié.

Le tri rapide était né, et avec lui la stratégie qui donne son nom à ce bloc.

Algorithmique 1 s'était arrêtée sur un constat : le tri par sélection et le tri par insertion coûtent $O(n^2)$, ce qui interdit de trier un million de valeurs. Ce chapitre franchit la barrière, et le suivant expliquera pourquoi elle se franchit exactement à $n \log n$.

Diviser pour régner

La stratégie se décompose en trois temps, toujours les mêmes.

Diviser le problème en sous-problèmes de même nature, plus petits. Régner en les résolvant récursivement — les sous-problèmes assez petits étant traités directement, c'est le cas de base du chapitre 1. Combiner les solutions partielles en une solution complète.

L'intérêt tient à une propriété du coût quadratique. Trier $n$ valeurs coûte $n^2$ ; trier deux moitiés coûte $2 \times (n/2)^2 = n^2/2$. Couper en deux divise déjà le travail par deux, et la récursion répète l'opération jusqu'en bas. Encore faut-il que la recombinaison soit bon marché — c'est là que les deux tris de ce chapitre diffèrent.

Le tri fusion

Il place tout l'effort dans la combinaison, et sa division est triviale.

1fonction triFusion(T)2    si taille(T) ≤ 1 alors retourner T          ← cas de base3    couper T en deux moitiés G et D             ← diviser (trivial)4    G ← triFusion(G)                            ← régner5    D ← triFusion(D)6    retourner fusion(G, D)                      ← combiner (le vrai travail)

Toute la subtilité est dans fusion, et elle repose sur une observation : fusionner deux listes DÉJÀ TRIÉES est linéaire. On compare les deux têtes, on prend la plus petite, on avance d'un cran dans la liste concernée, on recommence. Chaque élément est examiné une seule fois.

1G = [2, 5, 8]    D = [1, 4, 9]2     ↑                ↑          1 < 2  →  on prend 1        [1]3     ↑                   ↑       2 < 4  →  on prend 2        [1, 2]4        ↑                ↑       4 < 5  →  on prend 4        [1, 2, 4]5        ↑                   ↑    5 < 9  →  on prend 5        [1, 2, 4, 5]6           ↑                ↑    8 < 9  →  on prend 8        [1, 2, 4, 5, 8]7                            ↑    G épuisée → on recopie      [1, 2, 4, 5, 8, 9]

Trois propriétés en découlent, et ce sont les arguments du tri fusion.

Son coût est $O(n \log n)$ dans tous les cas, sans exception. La découpe en deux est parfaite par construction, donc la profondeur est toujours $\log_2 n$ et chaque niveau coûte $n$. Il n'y a pas de pire cas.

Il est stable : deux éléments de même clé conservent leur ordre initial, à condition qu'en cas d'égalité la fusion prenne l'élément de gauche. Cela compte dès qu'on trie sur plusieurs critères successifs — trier par prénom puis par nom donne le classement attendu seulement si le second tri est stable.

Il consomme $O(n)$ de mémoire supplémentaire : la fusion ne se fait pas sur place. C'est son seul vrai défaut, et il est rédhibitoire sur des données très volumineuses ou en mémoire contrainte.

Le tri rapide

Il fait l'inverse : tout l'effort est dans la division, et la combinaison est vide.

L'opération centrale est le partitionnement. On choisit un pivot, puis on réorganise le tableau pour que tout ce qui lui est inférieur le précède et tout ce qui lui est supérieur le suive. Le pivot est alors à sa place définitive, et il ne reste qu'à recommencer sur les deux zones — sans rien recoller à la fin.

1fonction triRapide(T, debut, fin)2    si debut ≥ fin alors retourner              ← cas de base3    p ← partitionner(T, debut, fin)             ← diviser (le vrai travail)4    triRapide(T, debut, p − 1)                  ← régner5    triRapide(T, p + 1, fin)6                                                ← combiner : rien à faire

Ses propriétés sont l'exact miroir de celles du tri fusion.

Il trie sur place : $O(\log n)$ de mémoire, uniquement pour la pile d'appels. C'est son avantage décisif.

Il est $O(n \log n)$ en moyenne, et $O(n^2)$ dans le pire cas. Ce pire cas survient quand le pivot tombe systématiquement à une extrémité : la partition ne coupe alors pas en deux mais retire un seul élément, la profondeur devient $n$, et l'on retrouve un tri quadratique — avec en prime un risque de débordement de pile.

Et le pire cas n'est pas rare : prendre le premier ou le dernier élément comme pivot le déclenche sur un tableau déjà trié, ce qui est le cas d'usage le plus fréquent en pratique. Trois parades existent : prendre le pivot au hasard, prendre la médiane de trois valeurs (premier, milieu, dernier), ou basculer sur un autre tri au-delà d'une profondeur donnée.

Enfin, il n'est pas stable : les échanges du partitionnement déplacent des éléments égaux les uns par rapport aux autres, comme l'animation le montre au cinquième pas.

Les mettre en balance

Le tableau appelle trois commentaires que la seule lecture des complexités ne donne pas.

Le tri rapide est le plus rapide en pratique, malgré son pire cas. Ses constantes cachées sont petites — une comparaison et parfois un échange par élément et par niveau, sans allocation — et ses accès sont séquentiels, ce qui exploite parfaitement le cache du chapitre 7 d'architecture. Le tri fusion, lui, écrit dans un tableau auxiliaire et paie des défauts de cache.

Le tri par insertion reste le meilleur sur les petits tableaux, disons sous une quinzaine d'éléments : son $O(n^2)$ porte sur des constantes minuscules, là où la récursion coûte des appels. C'est pourquoi toutes les implémentations sérieuses basculent sur lui en bas de récursion — un détail qui apporte 10 à 20 % de gain.

Les bibliothèques réelles sont hybrides. Le sort de la bibliothèque standard C++ est un introsort : tri rapide, avec bascule vers le tri par tas si la profondeur dérape, et tri par insertion en bas. Java et Python utilisent Timsort, une fusion qui détecte les portions déjà triées. Aucun n'est un algorithme « pur » du cours — et c'est la vraie leçon du chapitre : les algorithmes de base sont des briques, pas des produits finis.

À vous

L'exercice implémente les deux tris, puis les instrumente : nombre de comparaisons, nombre de déplacements, profondeur de récursion atteinte.

Trois expériences à mener, dans cet ordre. Vérifier que la fusion est bien linéaire, en comptant les comparaisons d'une fusion isolée. Provoquer le pire cas du tri rapide sur un tableau trié, puis le faire disparaître avec un pivot aléatoire — le contraste sur le compteur est spectaculaire. Enfin, mesurer le gain du basculement vers le tri par insertion sous un seuil, et chercher le seuil optimal.

let comparaisons = 0, deplacements = 0, profondeur = 0, maxProfondeur = 0;
function raz() { comparaisons = 0; deplacements = 0; profondeur = 0; maxProfondeur = 0; }
function compare(a, b) { comparaisons++; return a - b; }

// ── Tri fusion ────────────────────────────────────────────────────────────
function fusion(G, D) {
  const sortie = [];
  let i = 0, j = 0;
  while (i < G.length && j < D.length) {
    // À égalité on prend l'élément de GAUCHE : c'est ce qui rend le tri stable.
    if (compare(G[i], D[j]) <= 0) sortie.push(G[i++]);
    else sortie.push(D[j++]);
    deplacements++;
  }
  while (i < G.length) { sortie.push(G[i++]); deplacements++; }
  while (j < D.length) { sortie.push(D[j++]); deplacements++; }
  return sortie;
}

function triFusion(T) {
  profondeur++; maxProfondeur = Math.max(maxProfondeur, profondeur);
  if (T.length <= 1) { profondeur--; return T; }
  const milieu = Math.floor(T.length / 2);
  const r = fusion(triFusion(T.slice(0, milieu)), triFusion(T.slice(milieu)));
  profondeur--;
  return r;
}

// ── Tri rapide ────────────────────────────────────────────────────────────
function partitionner(T, debut, fin, choisirPivot) {
  const p = choisirPivot(T, debut, fin);
  [T[p], T[fin]] = [T[fin], T[p]];          // le pivot va au bout
  const pivot = T[fin];
  let i = debut - 1;
  for (let j = debut; j < fin; j++) {
    if (compare(T[j], pivot) <= 0) {
      i++;
      [T[i], T[j]] = [T[j], T[i]];
      deplacements++;
    }
  }
  [T[i + 1], T[fin]] = [T[fin], T[i + 1]];
  deplacements++;
  return i + 1;
}

function triRapide(T, debut, fin, choisirPivot) {
  profondeur++; maxProfondeur = Math.max(maxProfondeur, profondeur);
  if (debut < fin) {
    const p = partitionner(T, debut, fin, choisirPivot);
    triRapide(T, debut, p - 1, choisirPivot);
    triRapide(T, p + 1, fin, choisirPivot);
  }
  profondeur--;
  return T;
}

const pivotDernier = (T, debut, fin) => fin;
const pivotAleatoire = (T, debut, fin) => debut + Math.floor(Math.random() * (fin - debut + 1));

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Vérifiez que la fusion est LINÉAIRE : comptez les comparaisons d'une
//    fusion isolée de deux moitiés de n/2, et comparez à n.
// 2. Lancez le tri rapide à pivot fixe sur un tableau DÉJÀ TRIÉ de 500
//    valeurs, puis à pivot aléatoire. Comparez comparaisons et profondeur.
// 3. Ajoutez une bascule vers le tri par insertion sous un seuil, et cherchez
//    le seuil qui minimise le nombre de déplacements.

const N = 500;
const trie = Array.from({ length: N }, (_, i) => i);
const melange = [...trie].sort(() => Math.random() - 0.5);

raz(); triFusion([...melange]);
console.log("fusion, aléatoire  : " + comparaisons + " comparaisons, profondeur " + maxProfondeur);

En travaux pratiques

Ce que la suite en fait

Le chapitre 4 répond à la question laissée ouverte : d'où sort le $\log n$ ? On y posera l'équation $T(n) = 2\,T(n/2) + n$, on la résoudra de deux façons, et l'on démontrera que aucun tri par comparaison ne peut faire mieux que $n \log n$ — ce qui explique pourquoi les deux algorithmes de ce chapitre s'arrêtent exactement là.

Le tri rapide reviendra au chapitre 8 : sa bascule de sécurité vers le tri par tas suppose de connaître le tas, et le tri par tas est le troisième $n \log n$ du semestre — celui qui est à la fois garanti et sur place, au prix d'accès non séquentiels.

À retenir