Algorithmique 2 · C2 Diviser pour régner · Chapitre 1 · 8 h

Tris efficaces

Tri fusion — découpe, fusion, stabilité — et tri rapide — partitionnement, choix du pivot, pire cas ; comparaison expérimentale avec les tris élémentaires.

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.

Animation · 8 étapes

Partitionner autour du pivot 3 — l'étape unique du tri rapide

Départ : le pivot est la dernière case — La frontière i vaut −1 : aucune valeur n'est encore reconnue inférieure au pivot. L'invariant à tenir est simple — tout ce qui est à gauche de i, strictement, est inférieur ou égal à 3.
7 est plus grand que 3 : on ne touche à rien — La frontière ne bouge pas. Une valeur supérieure au pivot reste où elle est ; elle sera déplacée plus tard, par l'échange d'une valeur inférieure venue de sa droite.
2 est inférieur : la frontière avance et on échange — i passe de −1 à 0, et on échange T[0] et T[1]. Le 2 prend la place du 7, qui recule d'un cran. C'est le geste central : chaque valeur inférieure trouvée agrandit la zone de gauche d'une case.
9 est plus grand : rien — Deux valeurs supérieures se sont accumulées juste après la frontière. Elles forment la zone « supérieure au pivot », qui grandit elle aussi, mais par le seul avancement de j.
4 est plus grand : rien — Le parcours continue. Une seule comparaison par case, jamais deux : c'est ce qui donne le coût linéaire de la partition, et donc le n log n du tri complet.
1 est inférieur : la frontière avance et on échange — i passe à 1, et T[1] échange avec T[4] : le 1 rejoint la zone de gauche, le 7 part à sa place. Remarquez que cet échange DÉSORDONNE la zone de droite — le tri rapide n'est pas stable, contrairement au tri fusion.
8 est plus grand : rien — Fin du parcours. La frontière s'est arrêtée à 1 : deux valeurs sont inférieures ou égales au pivot, les quatre suivantes lui sont supérieures.
Échange final : le pivot rejoint sa place — On échange le pivot avec la case juste après la frontière. Le 3 est désormais à sa place DÉFINITIVE : tout ce qui le précède lui est inférieur, tout ce qui le suit lui est supérieur. On n'y touchera plus, et il ne reste qu'à recommencer sur les deux moitiés — c'est là qu'intervient la récursion.

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.

Quiz · 1 question

Un tri rapide qui prend toujours le dernier élément comme pivot met un temps quadratique sur un tableau DÉJÀ TRIÉ. Pourquoi, et que faire ?

Parce qu'un tableau trié n'a pas besoin d'être trié : il faut détecter ce cas et sortir immédiatement — cas particulier à détecter
Parce que le pivot est alors le maximum : la partition ne coupe pas en deux mais retire un seul élément, la profondeur devient n et le coût n². Remède : pivot aléatoire ou médiane de trois — partition dégénérée
Parce que les comparaisons sur des données triées sont plus lentes au niveau du processeur — effet matériel

Réponse : Sur un tableau croissant, le dernier élément est le maximum : tout le reste lui est inférieur, la partition produit une zone de n−1 éléments et une zone vide. On n'a pas divisé, on a retiré un élément — exactement le schéma du tri par sélection, donc n²/2 comparaisons et une profondeur de récursion de n, avec le débordement de pile qui menace. Le point important est que ce cas n'a rien d'exotique : les données déjà triées ou presque sont extrêmement fréquentes. D'où les parades systématiques : pivot tiré au hasard (le pire cas devient improbable, pas impossible), médiane de trois (bon marché et efficace en pratique), ou bascule vers le tri par tas au-delà d'une profondeur donnée, ce que fait introsort.

Les mettre en balance

	Insertion	Fusion	Rapide
Meilleur cas	$O(n)$	$O(n \log n)$	$O(n \log n)$
Cas moyen	$O(n^2)$	$O(n \log n)$	$O(n \log n)$
Pire cas	$O(n^2)$	$O(n \log n)$	$O(n^2)$
Mémoire	$O(1)$	$O(n)$	$O(\log n)$
Stable	oui	oui	non
Sur place	oui	non	oui

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.

Quiz · 1 question

Vous devez trier 50 millions d'enregistrements sur un serveur dont la mémoire libre dépasse à peine la taille des données, et le tri doit être stable. Quel algorithme ?

Le tri fusion, seul des trois à être à la fois stable et garanti n log n dans tous les cas — fusion
Le tri rapide, plus rapide en pratique et qui trie sur place — rapide
Le tri par insertion, dont la mémoire constante est le seul critère qui compte ici — insertion

Réponse : Deux contraintes tranchent. La STABILITÉ élimine le tri rapide, dont les échanges de partitionnement déplacent les éléments égaux les uns par rapport aux autres. Et la GARANTIE dans le pire cas compte sur un traitement de cette taille : un tri rapide malchanceux — ou nourri de données presque triées avec un mauvais pivot — passerait de quelques minutes à plusieurs heures. Le O(n) de mémoire supplémentaire du tri fusion est le vrai prix à payer, et il est ici problématique : c'est précisément pourquoi, sur des volumes qui dépassent la mémoire, on emploie un TRI EXTERNE, variante du tri fusion qui trie des blocs tenant en mémoire puis les fusionne depuis le disque — la fusion étant justement l'opération qui ne demande de garder qu'une valeur par flux. Le tri par insertion sur 50 millions d'éléments demanderait des années.

À 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.

Exercice de code

Instrumentez tri fusion et tri rapide, provoquez le pire cas, puis faites-le disparaître.

Point de départ

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);

Solution

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; }

function fusion(G, D) {
  const sortie = [];
  let i = 0, j = 0;
  while (i < G.length && j < D.length) {
    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, seuil = 1) {
  profondeur++; maxProfondeur = Math.max(maxProfondeur, profondeur);
  if (T.length <= seuil) { profondeur--; return insertion([...T]); }
  const milieu = Math.floor(T.length / 2);
  const r = fusion(triFusion(T.slice(0, milieu), seuil), triFusion(T.slice(milieu), seuil));
  profondeur--;
  return r;
}

function insertion(T) {
  for (let i = 1; i < T.length; i++) {
    const x = T[i];
    let j = i - 1;
    while (j >= 0 && compare(T[j], x) > 0) { T[j + 1] = T[j]; deplacements++; j--; }
    T[j + 1] = x;
  }
  return T;
}

function partitionner(T, debut, fin, choisirPivot) {
  const p = choisirPivot(T, debut, fin);
  [T[p], T[fin]] = [T[fin], T[p]];
  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 pivotMedian = (T, debut, fin) => {
  // Médiane de trois : premier, milieu, dernier. Bon marché, et supprime le
  // pire cas sur les données triées ou inversées, qui sont les plus fréquentes.
  const m = Math.floor((debut + fin) / 2);
  const a = T[debut], b = T[m], c = T[fin];
  if ((a <= b && b <= c) || (c <= b && b <= a)) return m;
  if ((b <= a && a <= c) || (c <= a && a <= b)) return debut;
  return fin;
};
const pivotAleatoire = (T, debut, fin) => debut + Math.floor(Math.random() * (fin - debut + 1));

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

console.log("— 1. la fusion est linéaire —");
raz();
fusion(trie.slice(0, N / 2), trie.slice(N / 2));
console.log("   fusion de deux moitiés de " + N / 2 + " : " + comparaisons +
            " comparaisons pour " + N + " éléments");

console.log("");
console.log("— 2. sur un tableau DÉJÀ TRIÉ, n = " + N + " (n log n ≈ " + attendu + ") —");
for (const [nom, T, pivot] of [
  ["fusion", trie, null],
  ["rapide, pivot fixe", trie, pivotDernier],
  ["rapide, médiane de 3", trie, pivotMedian],
  ["rapide, pivot aléatoire", trie, pivotAleatoire],
]) {
  raz();
  if (pivot === null) triFusion([...T]); else triRapide([...T], 0, N - 1, pivot);
  console.log("   " + nom.padEnd(26) + String(comparaisons).padStart(7) + " comparaisons | profondeur " +
              String(maxProfondeur).padStart(4) +
              (comparaisons > 10 * attendu ? "   << quadratique !" : ""));
}
// Le pivot fixe sur données triées produit ~n²/2 = 125 000 comparaisons et une
// profondeur de 500 : la partition n'a jamais coupé en deux, elle a retiré un
// élément à la fois. Deux lignes de changement dans le choix du pivot, et l'on
// retombe à ~4500 comparaisons et une profondeur de 20.

console.log("");
console.log("— 3. seuil de bascule vers l'insertion (données aléatoires) —");
for (const seuil of [1, 4, 8, 16, 32, 64]) {
  raz();
  triFusion([...melange], seuil);
  console.log("   seuil " + String(seuil).padStart(3) + " : " +
              String(comparaisons).padStart(6) + " comparaisons, " +
              String(deplacements).padStart(6) + " déplacements, profondeur " + maxProfondeur);
}
// La profondeur de récursion chute avec le seuil, et le nombre de
// comparaisons passe par un minimum : au-delà, le n² de l'insertion reprend
// le dessus. C'est exactement le réglage que font les bibliothèques réelles.

En travaux pratiques

Travaux pratiques 3 · 4 h

Écrire les tris, puis les faire échouer

Implémenter le tri fusion et le tri rapide, mesurer l'écart avec un tri quadratique, et provoquer délibérément le pire cas du tri rapide.

Avant de commencer

Les TP 1 et 2
Un générateur de tableaux aléatoires, et de quoi chronométrer

Énoncé

Le point de comparaison — Écrivez le tri par insertion. Mesurez-le sur des tableaux aléatoires de 1000, 10 000 et 100 000 éléments. Vérifiez que le temps est bien multiplié par cent quand la taille est multipliée par dix.
Le tri fusion — Écrivez la fusion de deux moitiés triées, puis le tri complet. Testez d'abord la fusion seule, sur des cas construits à la main. Indice : Écrire et tester la fusion isolément fait gagner une heure sur le débogage du tri complet.
Le tri rapide — Écrivez le partitionnement, puis le tri. Testez le partitionnement seul : après appel, tout ce qui est à gauche du pivot doit lui être inférieur.
Comparer — Mesurez les trois sur 10 000, 100 000 et un million d'éléments aléatoires. Tracez les courbes et identifiez celle qui n'est pas droite en échelle logarithmique.
Provoquer le pire cas — Faites échouer votre tri rapide : trouvez l'entrée qui le rend quadratique, avec votre choix de pivot. Mesurez, et faites-le déborder de la pile.
Le réparer — Corrigez avec un pivot médian de trois, puis avec un pivot aléatoire. Refaites l'essai précédent et mesurez.
La stabilité — Triez des paires par leur premier champ et observez ce qui arrive au second. Déterminez expérimentalement lequel de vos deux tris est stable.
Le seuil — Ajoutez au tri fusion un basculement vers l'insertion sous une certaine taille. Cherchez le seuil optimal par mesure, et expliquez pourquoi il n'est pas 2.

C'est réussi quand

Vos trois tris trient, vérifié par un contrôle automatique sur mille tableaux aléatoires
Vous exhibez une entrée qui rend votre tri rapide quadratique
Le pivot aléatoire rend cette même entrée inoffensive
Votre seuil mesuré se situe entre 10 et 50, et vous savez pourquoi

Correction

Le tri fusion — tris.c

void fusionner(int *t, int g, int m, int d, int *tmp) {
  int i = g, j = m + 1, k = g;
  while (i <= m && j <= d)
      tmp[k++] = (t[i] <= t[j]) ? t[i++] : t[j++];   /* <= : STABILITÉ */
  while (i <= m) tmp[k++] = t[i++];
  while (j <= d) tmp[k++] = t[j++];
  for (int x = g; x <= d; x++) t[x] = tmp[x];
}

void tri_fusion(int *t, int g, int d, int *tmp) {
  if (g >= d) return;
  int m = g + (d - g) / 2;        /* pas (g+d)/2 : DÉBORDEMENT */
  tri_fusion(t, g, m, tmp);
  tri_fusion(t, m + 1, d, tmp);
  fusionner(t, g, m, d, tmp);
}

Deux détails qui comptent. Le calcul du milieu par g + (d−g)/2 évite le débordement de (g+d) sur de grands indices — bogue resté vingt ans dans la recherche dichotomique de la bibliothèque Java. Et le <= plutôt que < est ce qui rend le tri STABLE : à égalité, l'élément de gauche passe d'abord.

Le tri rapide

int partitionner(int *t, int g, int d) {
  int pivot = t[d], i = g - 1;
  for (int j = g; j < d; j++)
      if (t[j] <= pivot) { i++; echanger(&t[i], &t[j]); }
  echanger(&t[i+1], &t[d]);
  return i + 1;
}

void tri_rapide(int *t, int g, int d) {
  if (g >= d) return;
  int p = partitionner(t, g, d);
  tri_rapide(t, g, p - 1);
  tri_rapide(t, p + 1, d);
}

Le tri rapide trie SUR PLACE — aucun tableau auxiliaire, contrairement à la fusion qui en demande un de taille n. C'est son principal avantage pratique, avec une meilleure localité mémoire, et c'est ce qui le rend souvent plus rapide que la fusion malgré une complexité moyenne identique.

Les mesures

n          insertion   fusion   rapide
10 000       0,082 s   0,001 s  0,001 s
100 000      8,3 s     0,012 s  0,009 s
1 000 000    ~14 min   0,14 s   0,10 s

insertion : ×100 quand n ×10   → O(n²)
fusion    : ×11,7              → O(n log n)

Le facteur entre les colonnes n'est pas constant : il CROÎT avec n. C'est la signature d'une différence de complexité, et c'est ce qu'il faut savoir lire dans un tableau de mesures. À un million d'éléments, l'écart est de quatre ordres de grandeur ; à cent, il est nul — ce qui justifie l'étape 8.

Le pire cas, et sa cause

pivot = dernier élément, entrée DÉJÀ TRIÉE :

partition 1 : pivot = max → 0 à gauche, n-1 à droite
partition 2 : idem
→ profondeur n, et non log n

100 000 éléments triés : 24 s (contre 0,009 s en aléatoire)
1 000 000 éléments triés : Segmentation fault (pile épuisée)

Le cas le plus fréquent en pratique — des données déjà triées — est précisément le pire cas de l'implémentation naïve. Ce n'est pas une curiosité théorique : c'est une faille exploitable, appelée attaque par complexité algorithmique, où l'attaquant fournit l'entrée qui déclenche le quadratique.

Les deux réparations

/* médian de trois : protège des entrées triées, pas d'un adversaire */
int m = g + (d-g)/2;
if (t[g] > t[m]) echanger(&t[g], &t[m]);
if (t[m] > t[d]) echanger(&t[m], &t[d]);
if (t[g] > t[m]) echanger(&t[g], &t[m]);
echanger(&t[m], &t[d]);

/* pivot aléatoire : aucune entrée n'est systématiquement mauvaise */
echanger(&t[g + rand() % (d - g + 1)], &t[d]);

entrée triée, 1 000 000 : 0,11 s dans les deux cas

Le hasard ne rend pas le pire cas impossible — il le rend IMPRÉVISIBLE, donc inatteignable par un adversaire. C'est une idée qui dépasse le tri : rendre le comportement indépendant de l'entrée en introduisant une source d'aléa, comme le font aussi les tables de hachage face aux collisions provoquées.

La stabilité et le seuil

fusion : STABLE   (grâce au <=)
rapide : NON STABLE (les échanges du partitionnement croisent
                   des éléments égaux distants)

seuil mesuré : entre 16 et 32 selon la machine
sous ce seuil, l'insertion est PLUS RAPIDE que la fusion —
moins d'appels, aucune allocation, et tout tient en cache

La complexité asymptotique ne décrit que le comportement à l'infini : à n = 20, le facteur constant domine, et le tri quadratique gagne. Toutes les bibliothèques standard font ce basculement — c'est le principe de l'introsort de la STL, qui combine tri rapide, tri par tas en cas de dégénérescence, et insertion sous le seuil.

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

Flashcards · 5 cartes

Quels sont les trois temps de la stratégie « diviser pour régner » ?: DIVISER en sous-problèmes de même nature, plus petits. RÉGNER en les résolvant récursivement, les cas assez petits étant traités directement. COMBINER les solutions partielles. L'intérêt vient de ce que le coût quadratique se divise par deux à chaque découpe : trier deux moitiés coûte 2 × (n/2)² = n²/2. Encore faut-il que la recombinaison soit bon marché.
Où le tri fusion place-t-il son effort, et quelles sont ses trois propriétés ?: Sa division est triviale (couper en deux) et tout l'effort est dans la FUSION, qui est linéaire parce qu'elle fusionne deux listes DÉJÀ triées : on compare les deux têtes, on prend la plus petite, on avance. Propriétés : n log n DANS TOUS LES CAS (la découpe est parfaite par construction, donc pas de pire cas) ; STABLE si l'égalité prend l'élément de gauche ; et O(n) de mémoire supplémentaire — son seul vrai défaut.
Où le tri rapide place-t-il son effort, et quel est son pire cas ?: Tout l'effort est dans le PARTITIONNEMENT : on choisit un pivot, on met les inférieurs à gauche et les supérieurs à droite, le pivot est à sa place définitive, et il n'y a RIEN à combiner. Il trie sur place (O(log n) pour la pile) et il est n log n en moyenne. Pire cas n² quand le pivot tombe à une extrémité : la partition retire un seul élément au lieu de couper en deux. Prendre le dernier élément comme pivot déclenche ce cas sur un tableau DÉJÀ TRIÉ — d'où pivot aléatoire ou médiane de trois.
Pourquoi le tri rapide est-il 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, aucune allocation — et surtout ses accès sont SÉQUENTIELS, ce qui exploite le cache du processeur. Le tri fusion écrit dans un tableau auxiliaire et paie des défauts de cache. La complexité asymptotique ne dit rien de ces deux facteurs, et c'est pourquoi on mesure.
Que font les bibliothèques réelles, et qu'en conclure ?: Elles sont HYBRIDES. Le sort de la bibliothèque C++ est un introsort : tri rapide, bascule vers le tri par tas si la profondeur dérape, tri par insertion en bas de récursion (car l'insertion bat tout le monde sous une quinzaine d'éléments, ses constantes étant minuscules). Java et Python emploient Timsort, une fusion qui détecte les portions déjà triées. Conclusion : les algorithmes du cours sont des briques, pas des produits finis.