Comprendre le tri rapide (quicksort) avec des exemples en JavaScript

Le tri rapide (quicksort) est un algorithme de tri de type « diviser pour régner » : il choisit un élément pivot, partitionne le tableau de sorte que les éléments plus petits se retrouvent à gauche et les plus grands à droite, puis trie récursivement chaque côté sur place.

La plupart d’entre nous le rencontrent pour la première fois devant un tableau blanc, sous le regard d’un examinateur, et c’est généralement au niveau de la boucle de partitionnement que l’assurance commence à s’évaporer. Il s’exécute en O(n log n) en moyenne, trie sans allouer de second tableau, et c’est l’algorithme auquel la plupart des recruteurs pensent lorsqu’ils vous demandent de « trier ceci à la main ».

Cet article couvre trois points : une version lisible pour construire l’intuition, un déroulé pas à pas d’une passe de partitionnement pour que vous voyiez les éléments se déplacer, et l’implémentation sur place que vous écririez réellement en entretien, ainsi que des remarques sur la complexité, le choix du pivot et la stabilité.

Comment fonctionne l’algorithme de tri rapide ?

Le tri rapide trie en découpant à répétition le tableau autour d’un pivot choisi. Une passe de partitionnement réorganise les éléments de sorte que tout ce qui est inférieur au pivot se place avant lui et tout ce qui est supérieur se place après ; le pivot occupe alors sa position finale dans le tableau trié. Appliquez la même étape aux sous-plages gauche et droite, et le tableau entier se trie de lui-même.

Il partage la structure « diviser pour régner » du tri fusion (merge sort), mais les compromis diffèrent. Le tri rapide et le tri fusion ont tous deux une complexité moyenne en O(n log n), mais le tri rapide trie sur place avec O(log n) d’espace auxiliaire alors que le tri fusion nécessite O(n) d’espace supplémentaire ; par ailleurs, le tri fusion est stable là où le tri rapide ne l’est pas. Le tri rapide échange cette garantie de stabilité contre une empreinte mémoire réduite et d’excellentes performances en conditions réelles.

D’abord la version lisible (filter et spread)

Le tri rapide le plus facile à lire partitionne avec filter et reconstruit le tableau avec l’opérateur de décomposition (spread). C’est le moyen le plus rapide de saisir la récursion, et c’est un excellent outil pédagogique, mais il alloue de nouveaux tableaux à chaque appel : il n’est donc pas véritablement sur place et consomme de la mémoire supplémentaire.

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const [pivot, ...rest] = arr;
  const left = rest.filter((x) => x < pivot);
  const right = rest.filter((x) => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort([3, 7, 2, 5, 1, 4, 6, 8]); // [1, 2, 3, 4, 5, 6, 7, 8]

Le cas de base (length <= 1) arrête la récursion, puisqu’un tableau de zéro ou un élément est déjà trié. Chaque appel construit trois nouveaux tableaux : l’utilisation mémoire de cette version croît donc avec l’entrée au lieu de rester constante. Utilisez-la pour expliquer l’idée ; préférez la version sur place ci-dessous lorsque la mémoire ou les attentes en entretien entrent en jeu.

Comment fonctionne le partitionnement ?

Le partitionnement est le moteur du tri rapide : il vaut donc la peine d’observer une passe de près. Le schéma de Lomuto prend le dernier élément comme pivot, parcourt la plage avec un indice de balayage j, et maintient un indice de frontière i marquant l’endroit où doit aller le prochain élément « inférieur au pivot ». Chaque fois que arr[j] est inférieur au pivot, il échange arr[i] et arr[j] puis avance i. À la fin, il place le pivot par échange à la position i.

Déroulons [7, 2, 1, 8, 6, 3, 5, 4] avec le pivot 4 (le dernier élément), en partant de i = 0 :

Le pivot 4 se place à l’indice 3, avec [2,1,3] à sa gauche et [6,7,5,8] à sa droite. Aucun des deux côtés n’est encore trié, mais le pivot est définitivement positionné et les deux côtés constituent désormais des sous-problèmes indépendants.

function partition(arr, lo, hi) {
  const pivot = arr[hi];          // last element as pivot
  let i = lo;                     // boundary for elements < pivot
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // move pivot into place
  return i;
}

Le tri rapide sur place que vous écririez en entretien

Le tri rapide de facture professionnelle conserve la fonction de partitionnement ci-dessus et effectue la récursion sur des plages d’indices (lo, hi) au lieu de construire de nouveaux tableaux. C’est la version à privilégier lorsqu’on vous demande d’implémenter un tri rapide : elle modifie un seul tableau et n’utilise que la pile d’appels comme espace supplémentaire.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

quickSort([7, 2, 1, 8, 6, 3, 5, 4]); // [1, 2, 3, 4, 5, 6, 7, 8]

Chaque appel partitionne sa plage, puis effectue une récursion sur les deux sous-plages situées de part et d’autre du pivot. La garde lo < hi constitue le cas de base : une plage de zéro ou un élément est déjà triée. Si la récursion est exclue (une question de suivi fréquente en entretien), la même logique se convertit en version itérative en empilant des paires lo/hi sur une pile explicite au lieu de la pile d’appels.

Complexité, choix du pivot et stabilité

Le coût du tri rapide est presque entièrement déterminé par le pivot. Avec des découpes équilibrées, chaque niveau de récursion touche chaque élément une fois, sur environ log n niveaux, ce qui donne O(n log n). Lorsque les découpes sont systématiquement déséquilibrées, la profondeur de récursion atteint n et le coût se dégrade en O(n²). Sur place, la pile d’appels représente O(log n) d’espace pour une entrée équilibrée.

Le piège classique : choisir le premier ou le dernier élément comme pivot fait basculer le tri rapide dans son pire cas en O(n²) sur une entrée déjà triée, car chaque partitionnement ne détache qu’un seul élément. On évite ce pire cas sur entrée triée en choisissant l’élément central, en utilisant la médiane de trois, ou en tirant un pivot aléatoire. La médiane de trois ordonne le premier, le central et le dernier élément puis utilise la médiane, ce qui résiste aux entrées adverses triées comme triées en ordre inverse :

function medianOfThree(arr, lo, hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] < arr[lo]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
  if (arr[hi]  < arr[lo]) [arr[lo], arr[hi]]  = [arr[hi], arr[lo]];
  if (arr[hi]  < arr[mid]) [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  // median now sits at mid; move it to hi so Lomuto uses it as the pivot
  [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  return arr[hi];
}

Une propriété qu’aucune stratégie de pivot ne permet de récupérer : le tri rapide n’est pas un tri stable, donc les éléments égaux peuvent être réordonnés par rapport à leurs positions initiales. Cela compte lorsque vous triez des enregistrements selon une clé secondaire et que vous attendez que l’ordre primaire soit préservé.

Le tri natif de JavaScript est-il un tri rapide ?

Non. Bien que l’algorithme de tri rapide soit instable, la méthode native Array.prototype.sort de JavaScript est garantie stable depuis ES2019, la dixième édition du standard du langage. V8 trie les tableaux avec Timsort depuis la v7.0 et Chrome 70 : un tri fusion qui exploite les séquences de données déjà ordonnées et laisse les éléments égaux dans l’ordre où il les a trouvés. Tous les autres moteurs majeurs sont soumis à la même exigence de stabilité par la spécification. Ainsi, « le tri rapide est instable » décrit l’algorithme, et non la méthode native sort dans un navigateur moderne.

Le tri rapide doit sa réputation à une boucle de partitionnement compacte, à son fonctionnement sur place et à sa vitesse moyenne en O(n log n) — à condition de tenir le pivot éloigné des extrémités du tableau. Implémentez la version sur place ci-dessus avec une médiane de trois ou un pivot aléatoire, exécutez-la sur une entrée triée pour confirmer qu’elle ne s’écroule pas, et vous saurez à la fois écrire un tri rapide et expliquer ses compromis à la demande.

FAQ

Quand utiliser le tri rapide plutôt que le tri fusion ?

Utilisez le tri rapide lorsque la mémoire est limitée et que vous souhaitez trier sur place, car il ne nécessite que O(log n) d'espace auxiliaire pour la pile d'appels récursifs, contre O(n) de tableau supplémentaire pour le tri fusion. Les deux ont une complexité moyenne en O(n log n), mais le tri rapide est plus rapide en pratique sur des données typiques. Choisissez le tri fusion lorsque vous avez besoin d'une stabilité garantie ou d'un pire cas garanti en O(n log n), car le tri rapide peut se dégrader en O(n au carré).

Pourquoi le tri rapide atteint-il O(n au carré) sur un tableau déjà trié ?

Un pivot fixe pris au début ou à la fin se dégrade en O(n au carré) sur une entrée triée, car chaque partitionnement place le pivot à une extrémité et produit une sous-plage vide et une plage de n moins 1 éléments. Cela donne n niveaux de récursion au lieu de log n, chacun effectuant un travail linéaire. La solution consiste à choisir l'élément central, à utiliser la médiane de trois, ou à tirer un pivot aléatoire : chacune de ces approches rétablit des découpes équilibrées sur des données triées.

Array.prototype.sort en JavaScript est-il implémenté avec un tri rapide ?

Non. Les moteurs modernes n'utilisent pas le tri rapide pour la méthode native sort. V8 utilise Timsort depuis la v7.0 et Chrome 70 : un tri fusion qui exploite les séquences de données déjà ordonnées et préserve l'ordre des éléments égaux. Depuis ES2019, la spécification ECMAScript exige qu'Array.prototype.sort soit stable, et tous les moteurs majeurs livrent un tri stable. Ainsi, l'algorithme du tri rapide est instable, mais le tri natif n'est pas un tri rapide et il est garanti stable.

Quelle est la différence entre les schémas de partitionnement de Lomuto et de Hoare ?

Lomuto utilise un seul indice de balayage et prend généralement le dernier élément comme pivot, en échangeant les éléments plus petits vers un indice de frontière ; il est plus simple à écrire et à dérouler. Hoare utilise deux pointeurs qui se rapprochent depuis les deux extrémités et effectue en général moins d'échanges, ce qui le rend plus rapide en pratique. Les deux partitionnent sur place et renvoient un point de découpe, mais l'indice renvoyé par Hoare ne place pas le pivot dans sa position finale, contrairement à celui de Lomuto.

Comment convertir un tri rapide récursif en version itérative ?

Remplacez la pile d'appels par une pile explicite de plages d'indices. Empilez la paire initiale lo et hi, puis bouclez tant que la pile n'est pas vide : dépilez une plage, partitionnez-la pour obtenir un indice de pivot p, et réempilez les deux sous-plages, de lo à p moins 1 et de p plus 1 à hi, lorsqu'elles contiennent plus d'un élément. Cela produit le même résultat tout en évitant la récursion, une question de suivi fréquente en entretien.