Probleme – Le tri rapide : pourquoi il gagne en moyenne et perd au pire

1. Le tri.

(* Trie t.[g .. d] en place. Précondition : 0 <= g, d < |t|.
   Complexité : Theta(n log n) en moyenne, Theta(n^2) au pire. *)
let echanger t i j = let x = t.(i) in t.(i) <- t.(j); t.(j) <- x

let rec trier t g d =
  if g < d then begin
    let pivot = t.(d) in
    let i = ref g in
    (* INVARIANT : t.[g .. i-1] <= pivot, et t.[i .. j-1] > pivot. *)
    for j = g to d - 1 do
      if t.(j) <= pivot then begin echanger t !i j; incr i end
    done;
    echanger t !i d;                (* le pivot prend sa place DÉFINITIVE *)
    trier t g (!i - 1);
    trier t (!i + 1) d
  end

Terminaison : variant $d-g$ ; le pivot étant placé définitivement, les deux appels portent sur des intervalles strictement plus courts. Correction : l'invariant garantit qu'après la boucle, tout ce qui est à gauche de $i$ est $\le$ pivot et tout ce qui est à droite est $>$ ; le pivot y est donc à sa place finale, et il suffit de trier les deux côtés.

2. Le pire cas. C'est le tableau déjà trié : le pivot, pris en dernière position, est alors le maximum, la partition ne sépare rien, et l'on récurse sur $n-1$ éléments. D'où $T(n)=T(n-1)+\Theta (n)=\Theta (n^2)$.

Le compte est exactement $n(n-1)/2$ : le tri rapide devient un tri par sélection.

Et le second défaut est pire que le premier : la profondeur de récursion vaut $n$. À $n=10^6$, la pile d'exécution du chapitre chap:recursivite déborde, et le programme ne rend pas un mauvais résultat — il s'arrête. Le pire cas du tri rapide n'est pas une lenteur, c'est un plantage, et il survient sur l'entrée la plus banale qui soit : des données déjà en ordre.

3. La parade : le médian de trois. On prend pour pivot la médiane de $t_g$, $t_{(g+d)/2}$ et $t_d$, et on l'échange en position $d$ avant de partitionner.

let median3 t g d =
  let m = g + (d - g) / 2 in
  let a = t.(g) and b = t.(m) and c = t.(d) in
  if (a <= b && b <= c) || (c <= b && b <= a) then m
  else if (b <= a && a <= c) || (c <= a && a <= b) then g else d

Sur un tableau trié, le médian de trois choisit le vrai milieu : les partitions sont parfaites, la profondeur tombe à ${\log }_{2}n$, et le coût à $n{\log }_{2}n$. Sur des données aléatoires, le gain n'est que de quelques pour cent — c'est normal, un pivot tiré au hasard y est déjà bon.

Mais le médian de trois ne supprime pas le pire cas, il le déplace : il existe des tableaux, construits exprès, qui le mettent en défaut. Les seules parades garanties sont le pivot tiré au hasard (chapitre chap:probabilistes) — dont le pire cas devient improbable au lieu d'impossible — ou le basculement sur un tri par tas au-delà d'une profondeur $2{\log }_{2}n$, ce que font les bibliothèques standard.

4. Pourquoi on l'emploie quand même. À nombre de comparaisons comparable — $10343$ contre $8937$ pour la fusion à $n=1024$ —, le tri rapide gagne sur trois points que le comptage ne montre pas :

• il trie en place, sans le tampon de $\Theta (n)$ ;
• sa partition parcourt le tableau séquentiellement, ce que la mémoire cache du processeur récompense ;
• ses constantes sont plus petites : un échange contre une recopie dans un tampon puis un retour.

La complexité asymptotique départage les algorithmes ; elle ne les classe pas. Le tri par partition-fusion garde l'avantage quand la garantie compte plus que la moyenne, quand les données sont sur disque — la fusion lit séquentiellement, la partition non — et quand la stabilité est requise.