Trier, partie 2 : tri fusion et tri rapide

Trier un million de valeurs en comparant toutes les paires demande environ 500 milliards de comparaisons ; le tri fusion en demande environ 20 millions.

Découper le problème, résoudre les moitiés

Les méthodes de l'unité précédente travaillent sur toute la liste à la fois et le paient d'environ n² comparaisons. Les deux méthodes de cette unité suivent un autre plan, appelé « diviser pour régner ». On découpe la liste en parties plus petites, on trie chaque partie avec la même méthode, puis on combine les parties triées. Le découpage continue jusqu'à ce qu'une partie ait une seule valeur ou aucune, et une liste d'une seule valeur est déjà triée. Comme la méthode s'appelle elle-même sur des listes plus petites, elle est récursive (l'unité 6 étudie la récursivité en détail).

Le tri fusion : le travail est dans la fusion

Le tri fusion coupe la liste en deux, trie la moitié gauche, trie la moitié droite, puis fusionne les deux moitiés triées en une seule. L'astuce est dans la fusion. On peut combiner deux listes triées en ne regardant que leurs valeurs de tête. On compare les deux têtes, on écrit la plus petite et on passe à la suivante. On recommence jusqu'à ce qu'une liste soit vide, puis on recopie ce qui reste de l'autre. Fusionner [1, 4, 7] et [2, 3, 8] donne 1 (1 contre 2), 2 (4 contre 2), 3 (4 contre 3), 4 (4 contre 8), 7 (7 contre 8), puis 8 est recopié : 5 comparaisons pour 6 valeurs. Une fusion de deux listes totalisant n valeurs ne demande jamais plus de n − 1 comparaisons.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // déjà triée
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

Pourquoi est-ce rapide ? Imagine les découpages comme des niveaux. Une liste de 8 valeurs se coupe en 2 listes de 4, puis en 4 listes de 2, puis en 8 listes de 1 : trois niveaux, car on peut couper 8 en deux 3 fois. À chaque niveau, toutes les fusions réunies touchent chaque valeur une fois : un niveau coûte donc au plus environ n comparaisons. Avec log₂ n niveaux, le total vaut environ n log₂ n. Pour un million de valeurs, cela fait environ 20 millions de comparaisons, contre environ 500 milliards pour les méthodes qui comparent paire par paire. Coupée en [38, 27, 43, 3] et [9, 82, 10], comme dans le labo, la liste [38, 27, 43, 3, 9, 82, 10] demande 14 comparaisons ; le code ci-dessus la coupe en 3 et 4 et en demande 13.

Le prix à payer, c'est la mémoire. Fusionner exige un endroit où écrire le résultat : le tri fusion utilise donc une seconde liste aussi grande que l'entrée. Le tri fusion est aussi stable : les valeurs égales gardent leur ordre d'origine, car la fusion prend dans la liste de gauche quand les têtes sont égales. Cela compte quand on trie un tableau selon une colonne puis une autre, par exemple par ville puis par nom.

Le tri rapide : partager autour d'un pivot

Le tri rapide (quicksort) divise la liste d'une autre façon. Il choisit une valeur, le pivot, et réorganise la liste pour que tout ce qui est plus petit que le pivot vienne avant lui et tout le reste après. Cette étape s'appelle le partitionnement. Le pivot est alors à sa place définitive, et les deux côtés peuvent être triés séparément avec la même méthode. Il n'y a rien à fusionner ensuite, car chaque valeur de gauche est déjà plus petite que chaque valeur de droite.

Le labo utilise une version de manuel courante qui prend la dernière valeur de chaque partie comme pivot. Sur [5, 1, 4, 2, 8], le pivot 8 est comparé aux quatre autres valeurs, toutes plus petites : 8 reste donc à la fin. La partie suivante, [5, 1, 4, 2], utilise le pivot 2 : seul 1 est plus petit, donc après deux échanges la liste est [1, 2, 4, 5, 8]. Une comparaison de plus règle [4, 5]. Total : 8 comparaisons et 2 échanges.

Quand le pivot tombe près du milieu, chaque partage coupe le problème en deux et le tri rapide demande environ n log₂ n comparaisons, comme le tri fusion. Il fonctionne aussi à l'intérieur de la liste d'origine, sans seconde copie. Mais un mauvais pivot fait mal. Si la liste est déjà triée et que le pivot est toujours la dernière valeur, chaque partage ne détache qu'une seule valeur, et le tri rapide retombe à environ n²/2 comparaisons : 10 pour [1, 2, 3, 4, 5], autant que le tri par sélection. Les vraies bibliothèques évitent cela en choisissant le pivot plus soigneusement, par exemple au hasard ou comme la médiane de trois valeurs prises en exemple.