Le tri et la recherche

Un étudiant en informatique apprend les algorithmes de tri au moins trois fois avant d'obtenir son diplôme : en programmation, en structures de données, puis en algorithmique. Pourquoi tant d'attention ? Parce que le tri est la brique de base sur laquelle reposent d'innombrables autres algorithmes. La plupart des grandes idées de conception — diviser pour régner, structures de données, randomisation — apparaissent d'abord dans le contexte du tri. Et historiquement, les ordinateurs ont passé plus de temps à trier qu'à faire quoi que ce soit d'autre : Knuth estimait qu'un quart des cycles des grands systèmes y était consacré.

Ce chapitre insiste moins sur le tri pour lui-même que sur ce qu'il permet : beaucoup de problèmes deviennent faciles une fois les données triées. En ce sens, le tri se comporte davantage comme une structure de données que comme un problème en soi. Nous verrons les algorithmes classiques en O(n log n) — heapsort, mergesort, quicksort — comme autant d'illustrations de paradigmes de conception, puis la borne inférieure du tri par comparaison, les tris linéaires, et enfin la recherche dichotomique et ses variantes.

Le tri comme outil

La morale du chapitre tient en une ligne : il existe des algorithmes de tri en O(n log n), ce qui est un gain massif sur les tris naïfs en O(n²) dès que n grandit.

n	n²/4	n log n
10	25	33
1 000	250 000	9 965
100 000	2 500 000 000	1 660 960

Pour n = 10 000, un algorithme quadratique passe encore ; au-delà de 100 000, il est ridicule. Or de nombreux problèmes se réduisent au tri, ce qui permet de réutiliser nos algorithmes en O(n log n) là où une solution quadratique semblait inévitable.

Voici les applications phares que cite Skiena :

• Recherche : la recherche dichotomique teste l'appartenance d'un élément en O(log n), à condition que les clés soient triées. Le prétraitement par tri est sans doute l'application la plus importante.
• Paire la plus proche : la paire de nombres au plus petit écart se trouve forcément côte à côte une fois les nombres triés. Un balayage linéaire suffit, soit O(n log n) au total.
• Unicité / doublons : cas particulier du précédent (un écart nul). On trie, puis on vérifie chaque paire adjacente.
• Distribution de fréquences / mode : une fois trié, un balayage gauche-droite regroupe les identiques et compte les occurrences.
• Sélection : le k-ième plus grand élément se lit en temps constant à la position k du tableau trié ; la médiane est en position n/2.
• Enveloppe convexe (convex hull) : triés par abscisse, les points s'insèrent de gauche à droite, le tout en temps linéaire après le tri.

Un exemple : deux ensembles sont-ils disjoints ?

Pour décider si deux ensembles de tailles m et n (m ≪ n) sont disjoints, trois variantes du tri-et-recherche existent. Trier le petit ensemble (en O(m log m)) puis faire une recherche dichotomique pour chacun des n éléments du grand donne O((n + m) log m) — meilleur que trier le grand, car log m < log n. C'est linéaire quand m est constant. En pratique, une table de hachage offre un temps linéaire espéré.

Spécifier l'ordre

Trier suppose de répondre à des questions concrètes : ordre croissant ou décroissant ? Trier sur la clé ou le dossier complet (en préservant le lien nom/adresse) ? Que faire des clés égales ? Un tri est dit stable s'il préserve l'ordre relatif d'origine des éléments égaux ; peu d'algorithmes rapides le sont, mais on obtient la stabilité de n'importe quel tri en ajoutant la position initiale comme clé secondaire. La bonne façon de spécifier tout cela est une fonction de comparaison propre à l'application, passée en argument au tri. En TypeScript, c'est exactement la signature de Array.prototype.sort.

Heapsort : trier grâce à une structure de données

Le tri par sélection (selection sort) extrait répétitivement le plus petit élément restant : n itérations, chacune coûtant un balayage linéaire, soit O(n²). L'opération coûteuse est « trouver le minimum ». Or c'est précisément ce que sait faire vite une file de priorité (priority queue). En remplaçant le tableau non trié par un tas (heap), chaque opération passe de O(n) à O(log n), et le tri par sélection devient O(n log n). Le nom heapsort masque cette filiation : ce n'est qu'un tri par sélection muni de la bonne structure.

Le tas implicite

Un tas est un arbre binaire où la clé de chaque nœud domine celles de ses enfants : plus petite dans un min-heap, plus grande dans un max-heap. L'astuce géniale est de représenter cet arbre sans pointeurs, dans un tableau : la racine en position 1, et pour le nœud en position k, ses enfants en 2k et 2k+1, son parent en ⌊k/2⌋. À condition de ne pas laisser de trous (chaque niveau rempli sauf peut-être le dernier), on stocke un tas de n clés dans exactement n cases, et sa hauteur est ⌊log n⌋.

// Min-heap sur un tableau, racine en index 0.
class MinHeap {
  protected q: number[] = [];

  protected parent(i: number): number {
    return (i - 1) >> 1; // floor((i-1)/2)
  }
  private child(i: number): number {
    return 2 * i + 1; // enfant gauche
  }

  // Insertion : O(log n), on fait remonter le nouvel élément.
  insert(x: number): void {
    this.q.push(x);
    this.bubbleUp(this.q.length - 1);
  }

  private bubbleUp(i: number): void {
    while (i > 0 && this.q[this.parent(i)] > this.q[i]) {
      const p = this.parent(i);
      [this.q[i], this.q[p]] = [this.q[p], this.q[i]];
      i = p;
    }
  }
}

Extraire le minimum

Le minimum est en tête du tableau. Pour le retirer, on place la dernière feuille à la racine, puis on la fait descendre (bubble down / heapify) : on l'échange avec le plus petit de ses enfants tant qu'elle le domine. On atteint une feuille en ⌊log n⌋ étapes, donc la suppression est en O(log n). Échanger le minimum avec le dernier élément puis réparer le tas, n fois, donne heapsort.

class MinHeap2 extends MinHeap {
  // Extraction du min : O(log n).
  extractMin(): number {
    const min = this.q[0];
    const last = this.q.pop()!;
    if (this.q.length > 0) {
      this.q[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  private bubbleDown(i: number): void {
    const n = this.q.length;
    for (;;) {
      const l = 2 * i + 1;
      const r = l + 1;
      let min = i;
      if (l < n && this.q[l] < this.q[min]) min = l;
      if (r < n && this.q[r] < this.q[min]) min = r;
      if (min === i) return;
      [this.q[i], this.q[min]] = [this.q[min], this.q[i]];
      i = min;
    }
  }
}

// Heapsort : O(n log n) au pire, en place dans l'esprit.
function heapsort(a: number[]): number[] {
  const h = new MinHeap2();
  for (const x of a) h.insert(x);
  return a.map(() => h.extractMin());
}

Heapsort est excellent : simple à programmer, O(n log n) dans le pire cas, et en place (aucune mémoire supplémentaire au-delà du tableau). D'autres algorithmes sont un peu plus rapides en pratique, mais pour trier des données tenant en mémoire vive, on ne se trompe jamais avec heapsort.

Mergesort : diviser pour régner

Le tri fusion (mergesort) est l'archétype du paradigme diviser pour régner (divide-and-conquer) : on partage le tableau en deux moitiés, on trie chacune récursivement, puis on fusionne (merge) les deux listes triées en une seule. Toute la subtilité est dans la fusion : le plus petit élément global se trouve forcément en tête de l'une des deux listes ; on le retire et on recommence. Fusionner deux listes totalisant n éléments coûte au plus n − 1 comparaisons, soit O(n).

La récursion descend sur log n niveaux, et chaque niveau fait un travail linéaire (chaque élément apparaît dans exactement un sous-problème par niveau). D'où un total de O(n log n) dans le pire cas.

// Mergesort : O(n log n), STABLE. Renvoie un nouveau tableau.
function mergesort(a: number[]): number[] {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const left = mergesort(a.slice(0, mid));
  const right = mergesort(a.slice(mid));
  return merge(left, right);
}

// Fusion linéaire de deux listes triées. <= préserve la stabilité.
function merge(left: number[], right: number[]): number[] {
  const out: number[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

Mergesort possède deux atouts particuliers. D'abord il est stable : la comparaison <= favorise systématiquement l'élément de gauche en cas d'égalité. Ensuite, il n'exige pas d'accès aléatoire aux éléments, ce qui en fait le tri idéal des listes chaînées — on fusionne en réarrangeant les pointeurs, sans mémoire supplémentaire. Son seul vrai défaut sur les tableaux est le besoin d'un tampon auxiliaire : sans lui, la fusion écraserait les éléments avant de les avoir lus.

Quicksort : trier par randomisation

Quicksort choisit un élément pivot p, puis partitionne les autres en deux tas : ceux qui le précèdent dans l'ordre trié, et ceux qui le suivent. Le partitionnement offre deux garanties : le pivot atterrit à sa position définitive, et aucun élément ne franchit la frontière par la suite. On peut donc trier les deux côtés indépendamment, récursivement.

// Quicksort en place, partition de Lomuto. Pivot aléatoire.
function quicksort(s: number[], lo = 0, hi = s.length - 1): void {
  if (lo >= hi) return;
  const p = partition(s, lo, hi);
  quicksort(s, lo, p - 1);
  quicksort(s, p + 1, hi);
}

// Partition linéaire O(n) autour du pivot s[hi].
function partition(s: number[], lo: number, hi: number): number {
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [s[r], s[hi]] = [s[hi], s[r]]; // pivot aléatoire en queue
  const pivot = s[hi];
  let firstHigh = lo;
  for (let i = lo; i < hi; i++) {
    if (s[i] < pivot) {
      [s[i], s[firstHigh]] = [s[firstHigh], s[i]];
      firstHigh++;
    }
  }
  [s[hi], s[firstHigh]] = [s[firstHigh], s[hi]];
  return firstHigh;
}

Le partitionnement est linéaire, et comme mergesort, quicksort fait O(n · h) où h est la hauteur de l'arbre de récursion. Tout dépend donc du pivot. Si l'on tombe à chaque fois sur la médiane, les sous-problèmes sont moitié moindres, h = log n, et l'on retrouve le comportement de mergesort. Mais si le pivot est toujours le plus petit ou le plus grand élément (ce qui arrive sur une entrée déjà triée avec un pivot fixe), on ne retire qu'un élément par niveau : h = n − 1, et le pire cas est Θ(n²), pire que heapsort ou mergesort.

Pourquoi c'est rapide en moyenne

L'intuition : un pivot est « assez bon » s'il tombe dans la moitié centrale des clés (rang n/4 à 3n/4). La moitié des éléments remplit cette condition, donc on tire un bon pivot avec probabilité 1/2 — comme une pièce qui tombe sur pile une fois sur deux. Les mauvais pivots peuvent au pire doubler la hauteur de l'arbre, qui reste donc Θ(log n). Une analyse plus fine donne une hauteur moyenne d'environ 2 ln n, soit seulement 39 % de plus qu'un arbre parfaitement équilibré. D'où un temps moyen en O(n log n).

En pratique, un quicksort bien implémenté est typiquement 2 à 3 fois plus rapide que mergesort ou heapsort, parce que les opérations de sa boucle interne sont plus simples. Le modèle RAM et la notation grand-O sont trop grossiers pour le prouver : entre deux algorithmes en Θ(n log n), ce sont les détails d'implémentation et le cache qui tranchent. La seule façon d'en avoir le cœur net est de mesurer.

Algorithme	Moyenne	Pire cas	En place	Stable
Heapsort	O(n log n)	O(n log n)	Oui	Non
Mergesort	O(n log n)	O(n log n)	Non¹	Oui
Quicksort	O(n log n)	O(n²)	Oui	Non

¹ En place possible via une fusion sophistiquée (algorithme de Kronrod), mais complexe.

La borne inférieure et les tris linéaires

Aucun de ces algorithmes n'est linéaire. Trier exige de regarder tous les éléments, donc tout tri est Ω(n). Peut-on combler l'écart en log n ? Non, pour le tri par comparaison : tout algorithme doit se comporter différemment sur chacune des n! permutations possibles. L'ensemble des exécutions forme un arbre de décision à n! feuilles, dont la hauteur minimale vaut lg(n!) = Θ(n log n). Cette borne s'étend à de nombreuses applications (unicité, mode, enveloppe convexe) — c'est l'une des rares bornes inférieures non triviales de l'algorithmique.

Cette borne ne concerne que les comparaisons. Si l'on connaît la structure des données, on peut faire mieux. Le tri par distribution / par paquets (bucketsort, distribution sort) répartit les éléments dans des paquets — par exemple les noms selon leur première lettre — puis trie chaque paquet et concatène. Quand la distribution est à peu près uniforme, c'est très efficace ; c'est l'idée derrière les tables de hachage. On atteint ainsi le temps linéaire sous hypothèses : counting sort (clés dans un petit intervalle), bucket sort (données uniformes), radix sort (tri des chaînes chiffre par chiffre).

// Counting sort : O(n + k) pour des entiers dans [0, k].
function countingSort(a: number[], k: number): number[] {
  const count = new Array<number>(k + 1).fill(0);
  for (const x of a) count[x]++; // fréquences
  const out: number[] = [];
  for (let v = 0; v <= k; v++) {
    for (let c = 0; c < count[v]; c++) out.push(v);
  }
  return out;
}

La recherche dichotomique et ses variantes

La recherche dichotomique (binary search) localise une clé dans un tableau trié en comparant à l'élément médian et en récursant sur la bonne moitié, soit lg n comparaisons — c'est la stratégie gagnante du jeu des « vingt questions » : un dictionnaire de 200 000 mots se devine en moins de 20 coups.

// Recherche dichotomique : O(log n). -1 si absent.
function binarySearch(s: number[], key: number): number {
  let lo = 0;
  let hi = s.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (s[mid] === key) return mid;
    if (s[mid] > key) hi = mid - 1;
    else lo = mid + 1;
  }
  return -1;
}

Le vrai pouvoir de la recherche dichotomique réside dans ses variantes :

• Compter les occurrences : pour compter combien de fois k apparaît, on ne cherche pas k mais les bornes de son bloc. En supprimant le test d'égalité (toute recherche échoue alors), on converge vers la frontière droite ; en inversant la comparaison, vers la frontière gauche. Deux recherches en O(log n) donnent le compte, quelle que soit la taille du bloc — bien mieux que le balayage en O(log n + s).
• Recherche du point de bascule (one-sided binary search) : pour trouver, dans une suite de 0 suivis de 1 de taille inconnue, le point de transition p, on sonde A[1], A[2], A[4], A[8]… jusqu'au premier 1, puis on dichotomise dans la fenêtre. Coût : au plus 2⌈lg p⌉ comparaisons, indépendamment de la taille du tableau.
• Racines et méthode de bisection : la racine carrée de n se calcule en encadrant l'intervalle [1, n] et en le divisant par deux selon le signe de m² − n. La même bisection trouve la racine d'une fonction continue f en testant le signe de f(m). Robuste et simple, à défaut d'être la plus rapide.

// lower_bound : 1er index où s[i] >= key. O(log n).
function lowerBound(s: number[], key: number): number {
  let lo = 0;
  let hi = s.length; // hi exclusif
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (s[mid] < key) lo = mid + 1;
    else hi = mid;
  }
  return lo; // nombre d'éléments < key
}

// Occurrences de key = upperBound - lowerBound, en O(log n).

À retenir

• Le tri est un outil avant d'être un problème : recherche, doublons, médiane, mode, enveloppe convexe deviennent faciles une fois les données triées. Trier est l'un des premiers réflexes à avoir.
• Trois tris en O(n log n) : heapsort (en place, pire-cas garanti, via le tas), mergesort (stable, idéal pour listes et tri externe, mais tampon requis), quicksort (en place, le plus rapide en pratique).
• Quicksort vit de sa randomisation : O(n log n) en moyenne mais O(n²) au pire ; un pivot aléatoire fait disparaître le pire-cas déterministe.
• Ω(n log n) est indépassable par comparaison (argument des n! permutations) ; counting/bucket/radix sort atteignent le linéaire sous hypothèses sur les données, au prix d'une fragilité face aux distributions inattendues.
• La recherche dichotomique trouve une clé en O(log n) dans un tableau trié, et ses variantes (lower/upper bound, comptage, point de bascule, bisection) résolvent élégamment quantité de problèmes voisins.
• Préférez la bibliothèque : Array.sort et consorts sont à utiliser par défaut ; réimplémenter ces algorithmes ne vaut que pour en maîtriser les paradigmes de conception.