Qu'est-ce que l'algorithme de tri rapide (QuickSort) ?

Le tri rapide, ou QuickSort, est un algorithme de tri fondé sur la méthode « diviser pour régner ». Son principe consiste à choisir un élément de la collection comme pivot, puis à réorganiser les autres éléments en fonction de leur comparaison avec ce pivot. Les éléments plus petits sont placés d’un côté et les éléments plus grands de l’autre, avant que le même procédé soit appliqué aux deux parties obtenues. Cette stratégie permet généralement de trier efficacement un grand nombre de données.

Le choix du pivot et le partitionnement

La première étape de QuickSort est la sélection d’un pivot. Celui-ci peut être choisi de plusieurs façons, par exemple parmi les premiers ou les derniers éléments, de manière aléatoire, ou à l’aide d’une règle destinée à obtenir une partition plus équilibrée. L’algorithme parcourt ensuite la partie à trier et réorganise ses éléments afin de placer ceux qui sont inférieurs au pivot d’un côté et ceux qui lui sont supérieurs de l’autre. Selon la variante utilisée, les éléments égaux au pivot peuvent être traités avec l’une ou l’autre des parties. Le partitionnement ne trie donc pas encore chaque groupe, mais il place le pivot dans une position cohérente par rapport aux éléments qui l’entourent.

Une application récursive

Après le partitionnement, QuickSort applique récursivement la même méthode à la partie située avant le pivot et à celle située après lui. Chaque sous-ensemble est ainsi divisé à son tour jusqu’à ce qu’il ne contienne plus qu’un élément, ou aucun : il est alors considéré comme trié. Par exemple, dans une liste contenant 8, 3, 6, 2 et 7, le choix de 6 comme pivot permet de séparer les valeurs inférieures, 8, 3 et 2, des valeurs supérieures, 7 et 8 selon l’ordre de traitement retenu ; l’algorithme poursuit ensuite le tri de chaque groupe. La collection peut être réorganisée directement dans le tableau, sans créer nécessairement deux nouvelles listes.

Des performances dépendantes de l’équilibre

La rapidité de QuickSort dépend fortement de la manière dont le pivot divise les éléments. Lorsque les deux sous-ensembles sont relativement équilibrés, sa complexité temporelle moyenne est de O(n log n), où n désigne le nombre d’éléments à trier. En revanche, si le pivot est régulièrement le plus petit ou le plus grand élément, une partie ne contient presque aucun élément tandis que l’autre conserve presque toute la liste. Le nombre de comparaisons peut alors atteindre une complexité de O(n²). Le choix du pivot, notamment par une sélection aléatoire ou une stratégie adaptée, sert à limiter la probabilité de ces partitions très déséquilibrées, sans supprimer le pire cas théorique.

Une famille de variantes

QuickSort peut être conçu pour fonctionner « en place », en réorganisant les éléments dans la collection initiale et en utilisant principalement la mémoire nécessaire aux appels récursifs. D’autres implémentations créent explicitement des sous-listes, ce qui modifie leur consommation de mémoire. Il ne faut donc pas attribuer à toutes les fonctions de tri des bibliothèques le recours à QuickSort : une bibliothèque peut employer une autre méthode ou une combinaison de techniques. Ce qui définit l’algorithme reste son schéma général : choisir un pivot, partitionner les éléments selon ce pivot, puis trier récursivement les deux sous-ensembles.