Licence 1 · Algorithmique 2

Cours 2 — Diviser pour régner

Couper un problème en deux, résoudre les moitiés, recoller — et savoir calculer ce que cette stratégie coûte réellement.

2 chapitres · 12 h de travail estimé

1. Tris efficaces8 h
2. Analyse des algorithmes récursifs4 h

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.

Chapitre 2 · 4 h

Analyse des algorithmes récursifs

Équations de récurrence, résolution par déroulement et par arbre d'appels ; pourquoi n log n est la borne des tris par comparaison ; dichotomie récursive.

Algorithmique 1 comptait les opérations d'une boucle : deux boucles imbriquées sur $n$ donnent $n^2$ , et l'affaire est entendue. Cette méthode s'effondre devant une fonction qui s'appelle elle-même — pour compter ses opérations, il faudrait déjà connaître le coût de l'appel récursif, c'est-à-dire la réponse cherchée.

Ce chapitre donne l'outil qui débloque la situation : on écrit le coût en fonction de lui-même, puis on résout. Il explique enfin d'où sort le $\log n$ du chapitre précédent, et il démontre que ce $n \log n$ n'est pas un hasard mais une limite infranchissable.

Poser l'équation

Le coût d'un algorithme récursif s'écrit comme une équation de récurrence : le coût pour une entrée de taille $n$ , exprimé à partir du coût pour des entrées plus petites.

La lecture est mécanique, et il faut prendre l'habitude de la faire ligne à ligne.

1fonction triFusion(T)                   T(n) = ...2    si taille(T) ≤ 1 alors retourner T      cas de base : T(1) = 13    couper T en G et D                      découpe : O(n), parfois O(1)4    G ← triFusion(G)                        un appel sur n/2 : T(n/2)5    D ← triFusion(D)                        un autre : T(n/2)6    retourner fusion(G, D)                  fusion linéaire : O(n)

D'où :

T(n) = 2\,T\!\left(\frac{n}{2}\right) + n \qquad\qquad T(1) = 1

Trois quantités seulement gouvernent ce genre d'équation, et il faut les repérer avant de calculer : combien d'appels récursifs ( $a$ ), sur quelle fraction de l'entrée ( $n/b$ ), et combien coûte le travail non récursif ( $f(n)$ ).

Algorithme	Équation
Recherche dichotomique	$T(n) = T(n/2) + 1$
Tri fusion	$T(n) = 2\,T(n/2) + n$
Tri rapide, cas moyen	$T(n) = 2\,T(n/2) + n$
Tri rapide, pire cas	$T(n) = T(n-1) + n$
Factorielle	$T(n) = T(n-1) + 1$
Fibonacci naïf	$T(n) = T(n-1) + T(n-2) + 1$

Remarquez la deuxième et la quatrième ligne : le même algorithme, deux équations différentes selon la qualité du pivot. C'est exactement l'écart entre $n \log n$ et $n^2$ du chapitre 3, et il se lit ici avant tout calcul — diviser par deux contre retirer un.

Résoudre par déroulement

La première méthode consiste à remplacer $T$ par sa définition, plusieurs fois, jusqu'à voir le motif.

\begin{aligned} T(n) &= 2\,T(n/2) + n \\ &= 2\,[\,2\,T(n/4) + n/2\,] + n = 4\,T(n/4) + 2n \\ &= 4\,[\,2\,T(n/8) + n/4\,] + 2n = 8\,T(n/8) + 3n \end{aligned}

Le motif apparaît à la troisième ligne : après $k$ déroulements, $T(n) = 2^k\,T(n/2^k) + k\,n$ .

Reste à savoir où s'arrêter : quand l'argument atteint le cas de base, c'est-à-dire quand $n/2^k = 1$ , donc $k = \log_2 n$ . En substituant :

T(n) = n\,T(1) + n \log_2 n = n + n \log_2 n = O(n \log n)

Le $\log_2 n$ est le nombre de fois qu'on peut couper $n$ en deux avant d'arriver à 1. Ce n'est pas une formule à retenir, c'est ce que la division par deux fait.

Résoudre par arbre d'appels

La seconde méthode est plus visuelle, et c'est celle qu'il faut avoir en tête pour raisonner vite. On dessine l'arbre des appels, on calcule le travail effectué à chaque niveau, puis on somme sur les niveaux.

1niveau 0        n                                   travail : n2              ┌─┴─┐3niveau 1     n/2  n/2                               travail : 2 × n/2 = n4            ┌─┴┐  ┌┴─┐5niveau 2   n/4 n/4 n/4 n/4                          travail : 4 × n/4 = n6                  ⋮7niveau k   2^k appels de taille n/2^k               travail : n8                  ⋮9niveau log n    n appels de taille 1                travail : n

Chaque niveau coûte $n$ — c'est le fait remarquable du tri fusion : le nombre d'appels double pendant que leur taille est divisée par deux, donc le produit reste constant. Il y a $\log_2 n$ niveaux. Total : $n \log_2 n$ .

Cette lecture rend immédiats les trois régimes possibles, qu'il suffit de reconnaître.

Le travail domine à la racine. Si $f(n)$ décroît plus vite que le nombre d'appels ne croît, la somme est dominée par le premier niveau : $T(n) = \Theta(f(n))$ . Exemple : $T(n) = 2T(n/2) + n^2$ donne $\Theta(n^2)$ .

Le travail est également réparti. Chaque niveau coûte pareil, et l'on multiplie par le nombre de niveaux : $T(n) = \Theta(f(n) \log n)$ . C'est le tri fusion.

Le travail domine aux feuilles. Si le nombre d'appels croît plus vite que $f$ ne décroît, la somme est dominée par le dernier niveau, qui compte $a^{\log_b n} = n^{\log_b a}$ feuilles. Exemple : $T(n) = 2T(n/2) + 1$ donne $\Theta(n)$ — le travail se fait dans les $n$ feuilles.

Ces trois cas constituent, sous une forme informelle, le théorème principal (master theorem). Le comparant à retenir est simple : confronter $f(n)$ à $n^{\log_b a}$ .

Une équation ne relève pas de ce schéma et mérite d'être traitée à part : $T(n) = T(n-1) + n$ , le pire cas du tri rapide. Ici l'argument ne se divise pas, il décroît de 1 : il y a donc $n$ niveaux, et le travail total vaut $n + (n-1) + \dots + 1 = n(n+1)/2$ , soit $\Theta(n^2)$ . Le contraste avec $2T(n/2) + n$ tient tout entier dans la façon de réduire l'entrée.

Quiz · 1 question

Un algorithme récursif satisfait T(n) = 2 T(n/2) + 1 : deux appels sur des moitiés, et un travail constant hors récursion. Quel est son coût total ?

En log n, car il y a log n niveaux et le travail par niveau est constant — log n
En n : le nombre d'appels double à chaque niveau tandis que le travail par appel reste à 1, donc le dernier niveau coûte à lui seul n et domine tout le reste — n
En n log n, comme le tri fusion, puisque la structure de la récursion est la même — n log n

Réponse : C'est le troisième régime : le travail domine aux feuilles. Le niveau k contient 2^k appels coûtant 1 chacun, donc 2^k au total — cette quantité DOUBLE à chaque niveau au lieu de rester constante. Le dernier niveau en compte n/2^0… soit n feuilles, et la somme 1 + 2 + 4 + … + n vaut 2n − 1, dominée par son dernier terme. Total Θ(n). La différence avec le tri fusion tient au seul f(n) : à n par appel, la décroissance de la taille compense exactement le doublement du nombre d'appels et chaque niveau coûte n ; à 1 par appel, elle ne compense plus rien. La première réponse compte les niveaux en oubliant que chacun contient de plus en plus d'appels.

La dichotomie, et pourquoi elle est si rapide

T(n) = T\!\left(\frac{n}{2}\right) + 1 \qquad\Longrightarrow\qquad T(n) = \log_2 n

Un seul appel par niveau, et un travail constant : l'arbre d'appels est une ligne de $\log_2 n$ éléments. C'est le premier régime, dégénéré — il n'y a qu'un appel par niveau, donc rien ne s'accumule.

Le chiffre mérite d'être posé, parce qu'il est difficile à croire tant qu'on ne l'a pas écrit : sur un million de valeurs, la recherche séquentielle demande jusqu'à un million de comparaisons, la dichotomie vingt. Sur un milliard, trente.

Graphique

Nombre de comparaisons pour traiter 100 000 valeurs

Tri par insertion, n²/4 : 2 500 000 0002500000000
Tri fusion, n log₂ n : 1 700 0001700000
Recherche dichotomique, log₂ n : 1717

Les deux dernières barres sont invisibles, et c'est le propos : face aux deux milliards et demi de comparaisons du tri quadratique, le tri fusion en demande 1 700 000 — mille cinq cents fois moins — et une recherche dichotomique dix-sept. Ce ne sont pas des optimisations, ce sont des changements de régime.

Pourquoi $n \log n$ est une limite

Reste la question de fond : les deux tris du chapitre 3 s'arrêtent tous deux à $n \log n$ . Coïncidence, ou obstacle ?

C'est un obstacle, et il se démontre en trois lignes.

Un tri par comparaison ne peut faire qu'une chose : comparer deux éléments et se brancher selon le résultat. Son exécution se décrit donc par un arbre de décision binaire, dont chaque nœud est une comparaison et chaque feuille une permutation possible du tableau de départ.

Comme l'algorithme doit pouvoir trier n'importe quelle entrée, l'arbre doit posséder au moins $n!$ feuilles — une par permutation. Or un arbre binaire de hauteur $h$ a au plus $2^h$ feuilles. Il faut donc $2^h \ge n!$ , c'est-à-dire $h \ge \log_2(n!)$ .

La formule de Stirling donne $\log_2(n!) = \Theta(n \log n)$ . La hauteur de l'arbre étant le nombre de comparaisons dans le pire cas :

\text{tout tri par comparaison exige } \Omega(n \log n) \text{ comparaisons.}

Le tri fusion atteint donc l'optimum de sa catégorie, et aucun algorithme plus astucieux ne descendra sous cette barre.

L'hypothèse « par comparaison » est essentielle, et c'est elle qui laisse une porte ouverte. Un tri qui exploite la structure des clés au lieu de les comparer échappe au raisonnement : le tri par comptage trie $n$ entiers d'un intervalle borné en $O(n)$ , en les rangeant directement dans des cases. Il ne contredit pas le théorème, il n'entre pas dans son cadre.

Quiz · 1 question

Un étudiant annonce un tri par comparaison en O(n) dans le pire cas. Que peut-on affirmer sans même lire son algorithme ?

Qu'il faut l'examiner attentivement : rien n'interdit une telle découverte — à examiner
Qu'il est faux, ou qu'il n'est pas un tri par comparaison : l'arbre de décision doit avoir n! feuilles, donc une hauteur d'au moins log₂(n!) = Θ(n log n) — impossible par construction
Qu'il est correct mais seulement sur des données déjà presque triées — cas particulier

Réponse : La borne inférieure ne dépend d'aucun algorithme particulier : elle porte sur le MODÈLE. Un tri qui n'a que des comparaisons pour s'informer doit pouvoir aboutir à chacune des n! permutations, donc son arbre de décision a au moins n! feuilles ; un arbre binaire de hauteur h en ayant au plus 2^h, il faut h ≥ log₂(n!) = Θ(n log n). Aucune astuce ne franchit cela. Deux échappatoires seulement, et elles sortent du cadre : sortir du modèle, comme le tri par comptage qui range les clés dans des cases sans jamais les comparer et trie en O(n) sur un intervalle borné ; ou parler du MEILLEUR cas, où le tri par insertion est déjà en O(n) sur des données triées — mais ce n'est pas le pire cas.

À vous

L'exercice résout les récurrences numériquement, ce qui est le meilleur moyen de vérifier une résolution faite à la main : on programme la récurrence telle qu'elle est écrite, on la tabule, et on compare à la forme close conjecturée.

Trois choses à obtenir. Retrouver $n \log_2 n$ pour le tri fusion et $n(n+1)/2$ pour le pire cas du tri rapide. Compter les niveaux et le travail par niveau d'un arbre d'appels, et voir lequel des trois régimes s'applique. Enfin, comparer $\log_2(n!)$ à $n \log_2 n$ pour constater que la borne inférieure est bien du même ordre que ce que le tri fusion atteint.

Exercice de code

Résolvez numériquement quatre récurrences, puis comparez log2(n!) à n log2 n.

Point de départ

// Une récurrence se programme littéralement, avec mémoïsation pour que la
// tabulation reste possible (ch. 2 : ne jamais répondre deux fois).
function resoudre(equation, base) {
  const table = new Map();
  const T = (n) => {
    if (n <= 1) return base;
    if (table.has(n)) return table.get(n);
    const v = equation(n, T);
    table.set(n, v);
    return v;
  };
  return T;
}

// T(n) = 2 T(n/2) + n            — tri fusion
const fusion = resoudre((n, T) => 2 * T(Math.floor(n / 2)) + n, 1);

// T(n) = T(n-1) + n              — tri rapide, pire cas
const rapidePire = resoudre((n, T) => T(n - 1) + n, 1);

// T(n) = T(n/2) + 1              — dichotomie
const dicho = resoudre((n, T) => T(Math.floor(n / 2)) + 1, 1);

// T(n) = 2 T(n/2) + 1            — ← à écrire : quel régime ?
const feuilles = resoudre((n, T) => 0, 1);

function comparer(nom, T, forme, formule) {
  console.log(nom);
  for (const n of [16, 64, 256, 1024, 4096]) {
    const mesure = T(n);
    const conjecture = forme(n);
    const ecart = (mesure / conjecture).toFixed(2);
    console.log("   n = " + String(n).padStart(5) +
      " | T(n) = " + String(mesure).padStart(10) +
      " | " + formule.padEnd(14) + " = " + String(Math.round(conjecture)).padStart(10) +
      " | rapport " + ecart);
  }
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez l'équation de « feuilles » et devinez son ordre AVANT de lancer.
// 2. Vérifiez que le rapport T(n) / conjecture tend vers une constante :
//    c'est ce que signifie « du même ordre ».
// 3. Comparez log2(n!) à n·log2(n) : la borne inférieure des tris est-elle
//    bien du même ordre que ce que le tri fusion atteint ?

comparer("T(n) = 2T(n/2) + n   (tri fusion)", fusion, (n) => n * Math.log2(n), "n log2 n");
comparer("T(n) = T(n-1) + n    (rapide, pire cas)", rapidePire, (n) => n * (n + 1) / 2, "n(n+1)/2");

Solution

function resoudre(equation, base) {
  const table = new Map();
  const T = (n) => {
    if (n <= 1) return base;
    if (table.has(n)) return table.get(n);
    const v = equation(n, T);
    table.set(n, v);
    return v;
  };
  return T;
}

const fusion = resoudre((n, T) => 2 * T(Math.floor(n / 2)) + n, 1);
const rapidePire = resoudre((n, T) => T(n - 1) + n, 1);
const dicho = resoudre((n, T) => T(Math.floor(n / 2)) + 1, 1);
// Deux appels, travail constant : le nombre d'appels double sans que le
// travail par appel diminue. Le dernier niveau domine, et il compte n
// feuilles : c'est le troisième régime, donc Θ(n).
const feuilles = resoudre((n, T) => 2 * T(Math.floor(n / 2)) + 1, 1);
// Travail quadratique hors récursion : la racine domine, Θ(n²).
const racine = resoudre((n, T) => 2 * T(Math.floor(n / 2)) + n * n, 1);

function comparer(nom, T, forme, formule) {
  console.log(nom);
  for (const n of [16, 64, 256, 1024, 4096]) {
    const mesure = T(n);
    const conjecture = forme(n);
    console.log("   n = " + String(n).padStart(5) +
      " | T(n) = " + String(mesure).padStart(12) +
      " | " + formule.padEnd(14) + " = " + String(Math.round(conjecture)).padStart(12) +
      " | rapport " + (mesure / conjecture).toFixed(2));
  }
  console.log("");
}

comparer("T(n) = 2T(n/2) + n     (tri fusion)", fusion, (n) => n * Math.log2(n), "n log2 n");
comparer("T(n) = T(n-1) + n      (rapide, pire cas)", rapidePire, (n) => n * (n + 1) / 2, "n(n+1)/2");
comparer("T(n) = T(n/2) + 1      (dichotomie)", dicho, (n) => Math.log2(n), "log2 n");
comparer("T(n) = 2T(n/2) + 1     (travail aux feuilles)", feuilles, (n) => n, "n");
comparer("T(n) = 2T(n/2) + n^2   (travail à la racine)", racine, (n) => n * n, "n²");
// Dans les cinq cas le rapport tend vers une constante : c'est exactement ce
// que « du même ordre » veut dire. Le rapport ne tend PAS vers 1 — les
// constantes multiplicatives et les termes d'ordre inférieur subsistent — et
// c'est pourquoi on écrit Θ et non « égale ».

console.log("— la borne inférieure des tris par comparaison —");
// log2(n!) se calcule sans jamais construire n! : log2(a·b) = log2 a + log2 b.
function logFactorielle(n) {
  let s = 0;
  for (let k = 2; k <= n; k++) s += Math.log2(k);
  return s;
}
for (const n of [16, 64, 256, 1024, 4096]) {
  const borne = logFactorielle(n);
  const atteint = n * Math.log2(n);
  console.log("   n = " + String(n).padStart(5) +
    " | log2(n!) = " + String(Math.round(borne)).padStart(7) +
    " | n log2 n = " + String(Math.round(atteint)).padStart(7) +
    " | rapport " + (borne / atteint).toFixed(3));
}
// Le rapport se stabilise autour de 0,9 : log2(n!) et n log2 n sont du même
// ordre, comme l'annonce la formule de Stirling. Autrement dit la borne
// inférieure et ce que le tri fusion atteint ne diffèrent que d'une constante
// — le tri fusion est optimal, et il ne reste aucune marge asymptotique.

En travaux pratiques

Travaux pratiques 4 · 2 h

Confronter la théorie à la mesure

Prédire la complexité d'un algorithme récursif par le calcul, puis vérifier la prédiction sur la machine — et regarder ce qui se passe quand les deux divergent.

Avant de commencer

Le TP 3 : les tris implémentés et mesurés
De quoi tracer une courbe

Énoncé

Poser les récurrences — Écrivez la relation de récurrence de la recherche dichotomique, du tri fusion, du tri rapide en moyenne, et de Fibonacci naïf. Résolvez-les.
Prédire — Pour chacune, prédisez le facteur multiplicatif du temps quand n double. Notez vos quatre prédictions avant toute mesure. Indice : Un algorithme en n log n ne double pas exactement : il fait un peu plus.
Mesurer — Mesurez les quatre en doublant n plusieurs fois. Comparez au tableau de prédictions et calculez l'écart.
L'écart — Là où mesure et prédiction divergent, cherchez la cause. Vérifiez notamment ce que fait la courbe quand le tableau dépasse la taille du cache.
Compter au lieu de chronométrer — Instrumentez vos tris pour compter les comparaisons plutôt que le temps. Comparez les courbes obtenues, et dites laquelle valide la théorie.
Le pire, le meilleur, le moyen — Pour le tri rapide, mesurez les trois cas sur la même taille. Écrivez ce que chacun signifie et lequel doit figurer dans une garantie contractuelle.
Lire une courbe — Tracez vos mesures en échelle logarithmique sur les deux axes. Mesurez la pente de chaque droite et déduisez-en l'exposant.

C'est réussi quand

Vos quatre prédictions sont posées avant les mesures, et trois au moins se vérifient
Vous expliquez l'écart restant sans invoquer le hasard
Le comptage de comparaisons colle à la théorie mieux que le chronomètre
Vous lisez l'exposant d'un algorithme sur la pente de sa droite

Correction

Les quatre récurrences

dichotomie    T(n) = T(n/2) + O(1)      → O(log n)
tri fusion    T(n) = 2 T(n/2) + O(n)     → O(n log n)
tri rapide    T(n) = 2 T(n/2) + O(n)     → O(n log n)  en moyenne
 pire cas   T(n) = T(n-1)  + O(n)      → O(n²)
Fibonacci     T(n) = T(n-1) + T(n-2)     → O(1,618^n)

théorème général : T(n) = a T(n/b) + f(n)
compare n^(log_b a) à f(n) ; ici a=2, b=2 → n, égal à f(n)
→ O(n log n)

La forme de la récurrence se lit directement dans le code : combien d'appels récursifs (a), sur quelle fraction de l'entrée (b), plus quel travail local (f). Savoir écrire la récurrence en regardant une fonction est plus utile que savoir réciter le théorème.

Prédictions et mesures

quand n double :          prédit    mesuré
dichotomie   O(log n)      +1 étape   +1 étape      ✓
tri fusion   O(n log n)    ×2,1       ×2,3          ✓
insertion    O(n²)         ×4         ×4,1          ✓
Fibonacci    O(1,618^n)    ×2,6       ×2,6          ✓

/* mais entre n = 2^20 et n = 2^22, le tri fusion fait ×2,9 */

Trois prédictions sur quatre tombent juste immédiatement. La quatrième dérive au-delà d'une certaine taille — et ce n'est pas la théorie qui est fausse, c'est le modèle de coût qui suppose un accès mémoire à prix constant.

Ce que le modèle ignore

tri fusion, facteur mesuré quand n double :
n < 2^18  (< cache L2) : ×2,1
n = 2^20                : ×2,3
n > 2^22  (> cache L3) : ×2,9

la complexité n'a pas changé ; le COÛT D'UN ACCÈS a changé
(TP 7 d'Architecture : 1 ns en L1, 100 ns en mémoire centrale)

La complexité compte les OPÉRATIONS en supposant qu'elles coûtent toutes pareil. La machine réelle ne respecte pas cette hypothèse. La théorie reste valable — elle prédit correctement l'ordre de grandeur — mais elle ne suffit pas à choisir entre deux algorithmes de même complexité. C'est pourquoi on mesure toujours.

Compter plutôt que chronométrer

tri fusion, comparaisons mesurées :
n        comparaisons   n log2 n
1 000        8 704        9 966
10 000     120 464      132 877
100 000  1 536 371    1 660 964

rapport comparaisons / (n log2 n) : 0,87, 0,91, 0,92 — STABLE

Le comptage d'opérations valide la théorie avec une précision que le chronomètre n'atteint jamais, parce qu'il ne dépend ni du cache, ni de l'ordonnanceur, ni de la fréquence du processeur. C'est la bonne façon de vérifier une analyse ; le chronomètre, lui, répond à une autre question — celle de la performance réelle.

Les trois cas, et lequel promettre

tri rapide sur 100 000 éléments :
meilleur cas (pivot toujours médian)  : 0,008 s
cas moyen    (entrée aléatoire)       : 0,009 s
pire cas     (entrée triée)           : 24 s

garantie contractuelle → le PIRE cas

Le cas moyen décrit ce qui se passe d'habitude, le pire cas ce qu'on peut PROMETTRE. Un service exposé sur le réseau ne raisonne jamais en moyenne, parce que l'entrée n'est pas tirée au hasard : elle est choisie par quelqu'un. C'est aussi pourquoi le tri rapide de la bibliothèque standard bascule vers le tri par tas quand la profondeur dérape — pour garantir un pire cas en n log n.

Lire l'exposant sur une pente

en échelle log-log, une complexité en n^k donne une DROITE
de pente k

insertion : pente 2,0    → O(n²)
fusion    : pente 1,05   → O(n log n), presque linéaire
dichotomie: plate         → O(log n)

C'est l'outil de diagnostic le plus rapide devant un programme lent : quelques mesures, une échelle logarithmique, et la pente donne la complexité réelle du code — celle qui s'exécute, pas celle qu'on croit avoir écrite. Une pente de 2 là où on attendait 1 signale presque toujours une boucle imbriquée oubliée, ou un appel à strlen dans une condition de boucle.

Ce que la suite en fait

Le bloc III change de sujet mais garde l'outil. Le coût d'une insertion en tête de liste chaînée, d'un empilement, d'un parcours d'arbre : tous s'écrivent en récurrences, et le chapitre 7 posera $T(h) = 2T(h-1) + 1$ pour compter les nœuds d'un arbre binaire complet.

Le $\log n$ reviendra surtout comme promesse conditionnelle. Un arbre binaire de recherche donne des opérations en $O(\log n)$ si sa hauteur reste logarithmique, et en $O(n)$ s'il dégénère en liste — exactement le même écart qu'entre le bon et le mauvais pivot du chapitre 3. Le chapitre 8 montrera ce que coûte de le garantir.

À retenir

Flashcards · 5 cartes

Comment lit-on l'équation de récurrence d'un algorithme récursif ?: Ligne à ligne, en repérant trois quantités : COMBIEN d'appels récursifs (a), SUR QUELLE FRACTION de l'entrée (n/b), et le COÛT DU TRAVAIL NON RÉCURSIF f(n). Le tri fusion donne T(n) = 2T(n/2) + n ; le pire cas du tri rapide donne T(n) = T(n−1) + n. Même algorithme, deux équations selon le pivot — et tout l'écart entre n log n et n² se lit avant le moindre calcul : diviser par deux contre retirer un.
Décrivez la résolution par déroulement, sur T(n) = 2T(n/2) + n.: On remplace T par sa définition jusqu'à voir le motif : 2T(n/2)+n, puis 4T(n/4)+2n, puis 8T(n/8)+3n, d'où après k déroulements 2^k·T(n/2^k) + k·n. On s'arrête quand l'argument atteint le cas de base, soit n/2^k = 1 donc k = log₂ n, ce qui donne n·T(1) + n log₂ n = O(n log n). Le log₂ n est simplement le NOMBRE DE FOIS qu'on peut couper n en deux avant d'arriver à 1.
Quels sont les trois régimes que révèle l'arbre d'appels ?: On calcule le travail par NIVEAU, puis on somme. 1) Le travail domine À LA RACINE : la somme est dominée par le premier niveau, T = Θ(f(n)) — ex. 2T(n/2)+n² donne Θ(n²). 2) Le travail est ÉGALEMENT RÉPARTI : chaque niveau coûte pareil, T = Θ(f(n)·log n) — c'est le tri fusion. 3) Le travail domine AUX FEUILLES : le dernier niveau l'emporte, T = Θ(n^(log_b a)) — ex. 2T(n/2)+1 donne Θ(n). C'est le théorème principal, et le comparant est f(n) contre n^(log_b a).
Démontrez que tout tri par comparaison exige Ω(n log n) comparaisons.: Un tel tri ne peut que comparer et se brancher : son exécution est un ARBRE DE DÉCISION binaire dont chaque feuille est une permutation atteignable. Comme il doit trier n'importe quelle entrée, l'arbre a au moins n! feuilles. Or un arbre binaire de hauteur h en a au plus 2^h, donc h ≥ log₂(n!) = Θ(n log n) par Stirling. La hauteur étant le nombre de comparaisons au pire cas, la borne est démontrée — et le tri fusion l'atteint, donc il est optimal dans sa catégorie.
Comment le tri par comptage peut-il trier en O(n) sans contredire cette borne ?: Parce qu'il n'entre pas dans le modèle. La borne suppose que l'algorithme ne s'informe QUE par des comparaisons. Le tri par comptage exploite la structure des clés : il range directement chaque entier dans la case correspondante d'un tableau de compteurs, sans jamais comparer deux éléments entre eux. Il trie donc n entiers d'un intervalle borné en O(n) — il ne contredit pas le théorème, il en sort.

Cours 2 — Diviser pour régner

Diviser pour régner

Le tri fusion

Le tri rapide

Les mettre en balance

À vous

En travaux pratiques

Ce que la suite en fait

À retenir

Poser l'équation

Résoudre par déroulement

Résoudre par arbre d'appels

La dichotomie, et pourquoi elle est si rapide

Pourquoi nlog⁡nn \log nnlogn est une limite

À vous

En travaux pratiques

Ce que la suite en fait

À retenir

Pourquoi $n \log n$ est une limite