QUICKSORT (TRI RAPIDE) : principe et utilisation de cet algorithme de tri

Le Quicksort est l’un des meilleurs algorithmes de tri utilisés sur des structures de données de grande taille comme des listes et des tableaux. Découvrez ci-dessous comment fonctionne cet algorithme, quels sont ses différents cas d’utilisation, ainsi que ses performances.

Le tri rapide ou tri pivot est un algorithme de tri inventé en 1961 par Tony Hoare alors étudiant en visite à l’université d’Etat de Moscou.

Parmi les algorithmes de tri les plus connus et les plus utilisés au monde, le tri rapide en fait partie. Le tri rapide (ou Quicksort en anglais) est une technique de tri utilisée pour ranger les éléments d’une structure de données dans un ordre bien précis (croissant ou décroissant). Généralement employé sur des tableaux, il peut aussi être employé sur des listes. Cet algorithme de tri repose essentiellement sur l’approche DPR (Diviser Pour Régner) qui consiste à utiliser deux ou plusieurs tableaux de tailles strictement inférieures à n pour résoudre un problème de tri portant sur un tableau de taille n. 

Le tri rapide consiste à choisir d’emblée un élément du tableau à trier qu’on appelle pivot, parfois de manière aléatoire ou de manière spécifique (généralement le premier élément ou le dernier élément du tableau d’entrée). Ensuite il faut partitionner le tableau d’entrée autour du pivot en plaçant le pivot dans sa position correspondante dans le tableau trié c’est-à-dire sa position définitive : ceci est assuré par une fonction de partitionnement. L’algorithme de partitionnement est un algorithme itératif qui parcourt entièrement le tableau à trier afin de placer tous les éléments plus petits que le pivot à gauche de celui-ci et tous les éléments plus grands que le pivot à droite de ce dernier.

Comment fonctionne précisément la fonction de partitionnement ?

De manière itérative, la fonction de partitionnement parcourt le tableau et compare chaque élément au pivot afin de placer tous les éléments plus petits du côté gauche et tous les éléments plus grands du côté droit. À l’issue de la fonction, on obtient l’indice retourné par la partition et, selon le schéma utilisé, le pivot peut déjà se trouver à sa position finale dans le tableau trié. Le choix du pivot est crucial (premier, dernier, aléatoire, médiane de trois) car il conditionne l’équilibrage des sous-tableaux et donc les performances globales du tri rapide.

• Objectif: réorganiser en place pour séparer les valeurs < pivot, = pivot et > pivot selon le schéma choisi.
• Coût: linéaire en la taille du segment traité.
• Résultat: un ou deux indices qui délimitent les sous‑tableaux pour les appels récursifs.

Hoare : comment ça marche ?

Le schéma de Hoare choisit un pivot (souvent l’élément de gauche) et utilise deux indices qui avancent l’un vers l’autre: i depuis la gauche jusqu’à trouver un élément ≥ pivot, j depuis la droite jusqu’à trouver un élément ≤ pivot. Tant que i est strictement inférieur à j, on échange arr[i] et arr[j] puis on continue. L’algorithme s’arrête quand i ≥ j et retourne j. Invariant utile: à l’arrêt, tout élément en position ≤ j est ≤ pivot, tout élément en position ≥ j+1 est ≥ pivot. Le pivot n’est pas nécessairement à sa place définitive, mais la séparation est correcte. Avantage majeur: très peu d’échanges et un comportement pratique souvent meilleur que Lomuto.

Exemple bref: pour un segment [l, r], si le pivot vaut 10, on avance i tant que arr[i] < 10, on recule j tant que arr[j] > 10, puis on échange arr[i] et arr[j] tant que i < j. À la fin, on trie récursivement [l, j] et [j+1, r].

Lomuto : quelles étapes ?

Le schéma de Lomuto sélectionne en général le dernier élément comme pivot. On maintient un index i pour la « zone des petits ». On parcourt j de gauche à droite: si arr[j] ≤ pivot, on incrémente i puis on échange arr[i] et arr[j]. En fin de parcours, on place le pivot entre les deux zones en échangeant arr[i+1] et arr[r]. Le pivot est alors à sa position finale et l’on retourne i+1. Ce schéma est simple à lire et à coder, mais il effectue souvent plus d’échanges et peut moins bien se comporter en présence de nombreux doublons.

Partition 3-voies : quand l’employer ?

Lorsque de très nombreuses valeurs sont égales au pivot, la partition 3‑voies, inspirée du « Dutch National Flag », évite la dégradation en séparant en une seule passe trois zones: < pivot, = pivot, > pivot. On utilise trois indices: lt (fin de la zone <), i (exploration) et gt (début de la zone >). Tant que i ≤ gt: si arr[i] < pivot, on échange arr[lt] et arr[i] puis on avance lt et i; si arr[i] > pivot, on échange arr[i] et arr[gt] puis on recule gt; sinon, arr[i] = pivot, on avance seulement i. On ne trie ensuite que les zones < pivot et > pivot. Ce schéma est recommandé pour des clés à faible cardinalité ou des jeux de données avec de nombreux doublons.

Quel schéma choisir ?

Schéma	Idée clé	Pivot à la bonne place en sortie	Échanges	Doublons	Simplicité	À privilégier quand…
Hoare	Deux pointeurs qui se croisent	Non garanti	Peu	Correct, mais pas optimal	Moyenne	Recherche d’efficacité pratique et de peu d’échanges
Lomuto	Un seul passage, une zone « petits »	Oui	Plutôt plus	Peut se dégrader	Très simple	Code pédagogique, clarté prioritaire
3‑voies	Sépare <, =, > pivot	Zone centrale triée par définition	Maîtrisés	Excellente gestion	Un peu plus verbeux	Nombreux doublons ou faible cardinalité des clés

En pratique, Hoare est souvent le meilleur compromis échanges/performances. Lomuto reste la porte d’entrée idéale pour apprendre. La 3‑voies s’impose lorsque beaucoup d’éléments sont égaux au pivot. Dans tous les cas, un bon choix de pivot (par exemple médiane de trois) améliore la robustesse, en Data & IA notamment.

Pseudo‑code des partitions

1) Hoare

2) Lomuto

3) Partition 3‑voies

Pas‑à‑pas sur un petit tableau

Exemple avec Lomuto et pivot dernier élément, sur array = [9, 12, 1, 5, 6, 13, 8, 2, 4].

• Initialisation: pivot = 4, i = −1.
• j = 0: 9 > 4, rien.
• j = 1: 12 > 4, rien.
• j = 2: 1 ≤ 4, i = 0, échange arr[0]↔arr[2] → [1, 12, 9, 5, 6, 13, 8, 2, 4].
• j = 3: 5 > 4, rien. j = 4: 6 > 4, rien. j = 5: 13 > 4, rien. j = 6: 8 > 4, rien.
• j = 7: 2 ≤ 4, i = 1, échange arr[1]↔arr[7] → [1, 2, 9, 5, 6, 13, 8, 12, 4].
• Fin de boucle: échange pivot avec arr[i+1] → [1, 2, 4, 5, 6, 13, 8, 12, 9]. L’indice retourné vaut 2 et le pivot 4 est à sa position finale.

On appliquera ensuite le tri rapide récursivement aux sous‑tableaux de part et d’autre du pivot, comme rappelé plus haut.

Quel pivot choisir et pourquoi cela compte ?

Le choix du pivot conditionne directement la qualité de la partition et donc la profondeur de récursion du tri rapide. Comme rappelé plus haut, le tri rapide consiste à choisir un pivot puis à placer tous les éléments plus petits à gauche et plus grands à droite, avant d’appliquer récursivement l’algorithme sur les sous-tableaux.

Si le pivot sépare mal les données, on obtient des partitions très déséquilibrées, la profondeur de l’arbre de récursion peut atteindre n et la complexité grimpe vers O(n^2). À l’inverse, un pivot qui coupe approximativement en deux entraîne une profondeur proche de log n et une complexité moyenne en O(n log n). D’où l’importance d’une stratégie de sélection adaptée au jeu de données et à l’implémentation.

Premier/dernier/au hasard : quels effets ?

Problème : choisir systématiquement le premier ou le dernier élément comme pivot fonctionne mais expose aux pires cas lorsque le tableau est déjà trié ou presque trié. La partition devient alors très déséquilibrée, ce qui reproduit un comportement quadratique similaire à un tri par sélection.

Explication : choisir un pivot aléatoire casse ces motifs défavorables. Sans changer l’algorithme de partition, la randomisation réduit fortement la probabilité d’une longue série de partitions déséquilibrées et préserve en pratique la complexité attendue en O(n log n), même si des entrées arrivent déjà triées.

Médiane de trois : un bon compromis ?

Amélioration pratique : au lieu de prendre un pivot brut, on échantillonne trois valeurs (par exemple première, médiane d’indice, et dernière) et on choisit leur médiane comme pivot. Comme évoqué plus haut dans l’article, cette idée vise à éviter qu’un mauvais pivot ne dégénère la récursion. Le surcoût est constant et très faible, alors que la probabilité d’obtenir une coupure raisonnablement équilibrée augmente nettement.

Quand l’utiliser : c’est un excellent défaut pour des tableaux en mémoire, surtout si les données arrivent souvent déjà triées, presque triées ou avec une tendance monotone. La médiane de trois améliore la robustesse sans complexifier l’implémentation.

Médiane des médians : utile en pratique ?

Option théorique : l’algorithme de médiane des médians permet de sélectionner un pivot en temps linéaire garantissant des partitions suffisamment équilibrées. Intégré à Quicksort, il élimine le pire cas O(n^2) et donne une borne garantie O(n log n) quelle que soit l’entrée.

Conséquences : cette garantie s’accompagne d’un surcoût constant non négligeable par rapport aux stratégies plus simples. En pratique, sur des données classiques, la médiane des médians est souvent moins rapide que la randomisation ou la médiane de trois, et on la réserve plutôt à des scénarios défensifs ou académiques.

Comment éviter les pires cas ?

• Randomisation du pivot : choisir un pivot au hasard à chaque partition pour neutraliser les entrées pathologiques répétées.
• Échantillonnage : médiane de trois, voire de cinq, pour améliorer la probabilité d’un découpage équilibré avec un coût minime.
• Introspection : surveiller la profondeur de récursion et basculer vers un tri garanti (par exemple un tri par tas) si un seuil est dépassé, afin d’assurer une complexité O(n log n) dans le pire cas.

En synthèse, commencez simple : un pivot aléatoire ou la médiane de trois suffit généralement pour atteindre des performances stables en O(n log n) sur des données réelles, tout en gardant une implémentation compacte et rapide.

Que faire après avoir obtenu la position finale du pivot à l’issue de la fonction de partitionnement ?

Après avoir obtenu la position finale du pivot et permuté les indices, il faut appliquer la fonction de tri rapide sur les deux sous‑tableaux obtenus de part et d’autre du pivot. C’est‑à‑dire le sous‑tableau de gauche repéré par Tableau[début, indice(pivot)−1] et le sous‑tableau de droite repéré par Tableau[indice(pivot)+1, fin].

Il va ensuite falloir choisir deux pivots correspondant aux pivots des sous‑tableaux de gauche et de droite, puis appliquer un appel récursif de la fonction de tri rapide sur ces deux sous‑tableaux. Les appels récursifs s’arrêtent lorsque le sous‑tableau a une taille 0 ou 1, en pratique lorsque début ≥ fin.

• But immédiat: trier indépendamment les deux zones, tout en maîtrisant la profondeur d’appels récursifs et l’usage de la pile d’exécution.
• Astuce de robustesse: préférer des stratégies qui limitent la profondeur maximale, notamment l’élimination de la récursion de queue et le tri prioritaire du plus petit sous‑tableau.

Quels appels récursifs et quelles conditions d’arrêt ?

1. Partitionner le segment Tableau[début, fin] et récupérer p = indice(pivot).
2. Définir les bornes:
   • sous‑tableau gauche: [début, p−1]
   • sous‑tableau droit: [p+1, fin]
3. Conditions d’arrêt: si début ≥ fin, ne rien faire, le segment est déjà trié.
4. Ordre des appels classique: quicksort(début, p−1) puis quicksort(p+1, fin). Pour réduire la profondeur, voir plus bas la variante qui trie d’abord le plus petit sous‑tableau.

Comment éliminer la récursion de queue ?

Après la partition, l’un des deux appels récursifs est en position de queue. On peut donc le remplacer par une boucle, et ne conserver qu’un seul appel récursif sur le plus petit des deux sous‑tableaux. Le plus grand segment est traité de manière itérative en mettant à jour les bornes dans la même fonction. Cette optimisation conserve la complexité moyenne en O(n log n) et réduit fortement la profondeur de pile.

En ne récurrant que sur la plus petite moitié et en itérant sur l’autre, la profondeur maximale d’appels devient proportionnelle à log n, ce qui limite les risques de débordement de pile sur de grands tableaux.

Pourquoi une version itérative avec pile explicite ?

Une implémentation totalement itérative remplace les appels récursifs par une pile explicite d’intervalles à trier. On empile des paires ⟨début, fin⟩, on dépile, on partitionne, puis on ré‑empile les segments restants. Avantages: contrôle précis de l’usage mémoire, absence de dépendance aux limites de pile du langage, comportement prévisible sur des entrées adversariales. En pratique, on empile d’abord le plus grand sous‑tableau et on traite immédiatement le plus petit afin de maintenir la pile courte.

Pourquoi trier d’abord le plus petit sous‑tableau ?

Conséquence directe: la profondeur maximale de récursion est bornée par O(log n) même lorsque les partitions sont déséquilibrées. On évite ainsi des appels emboîtés profonds, donc un risque de stack overflow sur des jeux de données déjà triés ou pathologiques.

Explication: à chaque étape, l’appel récursif porte sur le sous‑tableau le plus court, ce qui réduit rapidement la taille des segments manipulés par la pile d’appels. Le sous‑tableau le plus long est traité en boucle ou via une pile explicite, ce qui stabilise la consommation mémoire tout en conservant l’efficacité du tri en place.

Illustration du tri rapide

Considérons pour illustrer l’array ci-dessous où le pivot a été choisi comme l’élément le plus à droite c’est-à-dire array[longueur(array)-1] = 4 :

Idée générale du tri rapide, en une vue : on choisit un pivot, on partitionne le tableau autour de ce pivot, puis on applique récursivement la même stratégie aux sous-tableaux gauche et droit jusqu’à ce qu’ils soient de taille 0 ou 1.

• Choix du pivot (souvent premier ou dernier élément, ou aléatoire, ou médiane de trois).
• Partition : éléments < pivot à gauche, éléments > pivot à droite, le pivot se place à sa position finale.
• Récursion sur les deux sous-tableaux de part et d’autre du pivot.
• Arrêt lorsque le sous-tableau a 0 ou 1 élément.

Exemple simple pas‑à‑pas

1. Pivot choisi : 4 (dernier élément).
2. Partition(array, 0, len(array)-1) place le pivot à sa position finale :

   Tableau partitionné : 1 2 4 5 6 13 8 12 9

3. Deux sous-tableaux se forment de part et d’autre du pivot 4 :

   array1 = [1, 2]
   array2 = [5, 6, 13, 8, 12, 9]

4. Appels récursifs de quicksort sur array1 et array2, avec un nouveau pivot à chaque fois, jusqu’à ce que chaque sous-tableau soit de taille ≤ 1.
5. Résultat final :

   Sorted Array : 1 2 4 5 6 8 9 12 13

Que se passe‑t‑il avec beaucoup de doublons ?

Avec une partition classique à 2 voies, de nombreux éléments égaux au pivot circulent inutilement entre gauche et droite, ce qui multiplie les échanges et peut créer des sous-tableaux déséquilibrés. Exemple concret avec un pivot 3 :

La partition 3‑voies (variante « drapeau national ») sépare en trois régions : < pivot, = pivot, > pivot. Les éléments égaux au pivot restent groupés, et la récursion ne s’applique que sur les zones < pivot et > pivot. Cela réduit fortement le nombre de comparaisons et d’échanges lorsque les doublons sont massifs, et donne souvent des profondeurs de récursion plus faibles que la partition 2‑voies dans ces cas.

Que se passe‑t‑il avec un mauvais pivot ?

Si le pivot est systématiquement un minimum ou un maximum (par exemple dernier élément sur un tableau déjà trié), la partition crée un sous-tableau vide et un sous-tableau de taille n-1. On obtient alors beaucoup d’appels récursifs et une complexité quadratique O(n^2), avec une pile d’appels de taille O(n). À l’inverse, lorsque le pivot coupe le tableau en parts proches de moitié, on observe une complexité moyenne en O(n log n).

Pour limiter la dégradation, on utilise des stratégies de pivot plus robustes : pivot aléatoire pour éviter les structures adverses, ou médiane de trois (parmi début, milieu, fin) afin d’obtenir plus souvent des partitions équilibrées. Le schéma de partitionnement choisi (Lomuto, Hoare, 3‑voies) peut aussi influer sur le nombre d’échanges et l’équilibre des sous-tableaux, selon la distribution des données.

Démonstration de la complexité du tri rapide dans le cas moyen

En partant de l’équation de récurrence du cas moyen, on montre que le tri rapide a une complexité quasi linéaire. Intuition utile : si le pivot scinde le tableau en deux sous-problèmes de tailles proches, on résout deux problèmes de taille n/2 avec une reconstruction linéaire due au partitionnement, ce qui mène à une complexité en O(n log n).

Quel est le coût moyen ?

Données / preuves. Le coût moyen vérifie la récurrence T(n) = E_k[T(k) + T(n − 1 − k)] + c·n, où k est la position du pivot après partition et c·n est le coût linéaire du parcours de partition. L’espérance sur k conduit à T(n) = Θ(n log n). En nombre d’opérations, cela signifie un ordre de grandeur de Θ(n log n) comparaisons et un nombre d’échanges de même ordre, avec des constantes pratiques faibles car les partitions s’effectuent en place.

Intuition. Chaque niveau de récursion effectue au total un travail linéaire car chaque élément est comparé au pivot à ce niveau. Le nombre moyen de niveaux est proportionnel à log n, d’où un total d’environ n log n opérations. Lorsque la coupure est exactement équilibrée, on retrouve la récurrence T(n) = 2T(n/2) + c·n, qui calcule également à O(n log n).

Quel est le pire cas et quand survient‑il ?

Problème. Le pire cas apparaît lorsque le pivot est systématiquement extrême, ce qui produit des partitions très déséquilibrées. Cela se produit par exemple si l’on choisit toujours le premier ou le dernier élément comme pivot sur un tableau déjà trié ou trié à l’envers.

Exemple. Avec un tableau déjà trié croissant et un pivot pris comme dernier élément, la première partition donne des sous-tableaux de tailles n − 1 et 0, puis n − 2 et 0, etc. La récurrence devient T(n) = T(n − 1) + c·n, et la somme n + (n − 1) + … + 1 donne un temps en O(n²).

Quelle est la complexité spatiale ?

Explication. Le partitionnement classique du tri rapide s’effectue en place, il n’utilise donc qu’un espace auxiliaire O(1) pour les échanges. En revanche, la récursivité consomme de l’espace de pile.

Données / preuves. La profondeur de récursion attendue est O(log n) lorsque les partitions restent globalement équilibrées, ce qui mène à une complexité spatiale moyenne O(log n). Dans le pire cas dégénéré évoqué plus haut, la profondeur peut atteindre O(n), donc un espace de pile O(n).

Pourquoi la randomisation aide‑t‑elle ?

Explication. Choisir le pivot de manière aléatoire rompt les corrélations défavorables entre l’ordre d’entrée et la stratégie de pivot. Le rang du pivot devient, en moyenne, uniforme, ce qui garantit une espérance de temps en O(n log n) et une profondeur de pile attendue O(log n), quel que soit l’ordre initial des données.

Conséquences. La randomisation rend le pire cas très improbable sur des entrées non adversariales et stabilise les performances. En pratique, des heuristiques comme la « médiane de trois » issues d’échantillons du tableau approchent un pivot central et réduisent sensiblement le risque de partitions très déséquilibrées.

Comment implémenter QuickSort en pratique ?

Pour passer de la théorie à la pratique, on applique l’approche DPR (Diviser Pour Régner) décrite plus haut : choisir un pivot, partitionner le tableau en plaçant les éléments plus petits à gauche et les plus grands à droite, puis répéter récursivement sur chaque sous‑tableau jusqu’à ce qu’il ne reste plus rien à trier. Un bon choix de pivot (aléatoire ou médiane de trois) évite les partitions très déséquilibrées.

• Choisir un pivot (souvent le dernier élément pour un premier essai).
• Partitionner le tableau autour du pivot, qui rejoint sa position finale.
• Appliquer QuickSort aux sous‑tableaux gauche et droit.
• Arrêt quand le sous‑tableau est vide ou de taille 1.

Pseudo‑code minimal

Ci‑dessous, un squelette simple avec une partition de type Lomuto (lisible et courante). On peut remplacer le choix du pivot par un pivot aléatoire ou une médiane de trois valeurs pour réduire le risque de pire cas.

1. quicksort(A, lo, hi)
   Si lo ≥ hi : retourner
   p = partition(A, lo, hi)
   quicksort(A, lo, p – 1)
   quicksort(A, p + 1, hi)
2. partition(A, lo, hi) (Lomuto)
   pivot ← A[hi]
   i ← lo – 1
   Pour j de lo à hi – 1 :
       si A[j] ≤ pivot : i ← i+1, échanger A[i], A[j]
   Échanger A[i+1], A[hi]
   Retourner i+1

Exemples de code (Python/C++)

Implémentations idiomatiques en place, sans créer de copies inutiles.

Remarque : la variante de partition Hoare est plus rapide en pratique dans certains contextes, mais elle renvoie un indice de coupure différent et nécessite un soin supplémentaire sur les bornes. La version Lomuto reste un bon point de départ pédagogique.

Quels tests couvrir (cas limites) ?

• Tableau vide et tableau à 1 élément.
• Beaucoup de doublons (toutes les valeurs égales, ou peu de valeurs distinctes).
• Déjà trié et trié en ordre strictement décroissant.
• Données aléatoires de tailles variées.
• Mélange de négatifs, positifs et zéros, et quelques valeurs extrêmes.

Quelles erreurs fréquentes éviter ?

• Off‑by‑one sur les bornes : mauvaise gestion de lo, hi, ou du retour de partition (oublier p – 1 et p + 1).
• Boucles infinies : indices qui ne progressent pas ou pivot non déplacé à la fin de partition.
• Partition incorrecte : oublier d’échanger le pivot à la fin, ou ne pas respecter la condition ≤ pivot côté gauche.
• Copie inutile des sous‑tableaux : créer des listes temporaires dégrade temps et mémoire, privilégier l’algorithme en place.
• Profondeur de récursion excessive : pivot systématique en extrémité sur données déjà triées. Atténuer via pivot aléatoire ou médiane de trois.
• Attente de stabilité : QuickSort n’est pas stable par défaut, ne pas s’appuyer sur l’ordre relatif initial des doublons.

Quelles optimisations pratiques améliorent QuickSort ?

Au‑delà de l’idée Diviser pour régner, les gains de performance de QuickSort proviennent surtout de la sélection du pivot, du schéma de partitionnement, d’un basculement adapté vers un tri simple sur petits sous‑tableaux et d’une bonne localité mémoire. Le choix du pivot est crucial, car si le pivot ne divise pas suffisamment l’entrée, on se rapproche du pire cas en O(n²). Les bonnes implémentations combinent plusieurs heuristiques simples et éprouvées.

Pourquoi un cutoff vers insertion sort ?

Sur les très petits sous‑tableaux, le coût constant de l’appel récursif et des comparaisons l’emporte sur l’intérêt d’une partition complète. Insertion sort a un surcoût constant très faible, parcourt la mémoire de façon séquentielle, et profite mieux des prédictions de branche pour des données presque triées. Il est donc courant d’arrêter QuickSort lorsque la taille du sous‑tableau devient inférieure à un seuil k, puis de terminer par un passage d’insertion sort sur ces segments.

En pratique, k se règle empiriquement selon l’architecture, le type de données et le comparateur. Une plage de valeurs raisonnable se situe souvent entre 8 et 32 éléments. Vous pouvez mesurer le temps total en variant k pour choisir le meilleur compromis sur votre charge réelle.

Médiane de trois et échantillonnage : quand ?

Une idée communément utilisée consiste à prendre comme pivot la médiane de trois valeurs afin d’éviter un mauvais pivot extrême. Sur données réelles, cette heuristique améliore sensiblement la stabilité des partitions sans coût notable.

• Données presque triées ou presque décroissantes : médiane de trois parmi premier, milieu, dernier.
• Données sans structure apparente : pivot aléatoire ou médiane de cinq éléments réduits (échantillon léger) pour limiter les divisions très déséquilibrées.
• Données avec extrêmes fréquents : éviter systématiquement premier ou dernier élément seul comme pivot.
• Budget comparaisons serré : rester sur médiane de trois, qui offre un bon rapport qualité/prix.

Quand préférer la partition 3‑voies ?

Lorsque de nombreux éléments sont égaux au pivot, une partition binaire classique effectue des échanges inutiles et propage des segments d’éléments égaux à travers plusieurs niveaux de récursion. La partition en 3 voies (<, =, >) regroupe en une seule passe tous les éléments égaux, ce qui réduit la profondeur de récursion effective et le nombre total d’échanges.

Cas concret : tri d’identifiants ou de clés discrètes contenant de longues séries de doublons, ou tri de grands tableaux d’entiers avec faible cardinalité. La 3‑voies réduit alors significativement le temps CPU et le trafic mémoire.

Quand basculer vers introsort ?

QuickSort a un pire cas quadratique. Introsort démarre comme un QuickSort optimisé, surveille la profondeur de récursion, puis bascule vers un tri avec garantie de pire cas (généralement heapsort) dès que la profondeur dépasse un seuil proportionnel à log2(n). On obtient ainsi des performances proches de QuickSort en moyenne, tout en garantissant O(n log n) dans le pire cas.

Comparaison rapide : QuickSort optimisé reste légèrement plus simple et parfois plus rapide sur des jeux de données faciles, mais Introsort est préféré lorsqu’on veut une latence maximale bornée sans surprises.

Comment améliorer la localité mémoire ?

• Trier d’abord le plus petit sous‑tableau et convertir l’autre appel récursif en boucle (élimination de la récursion terminale) afin de réduire la profondeur de pile et de conserver un working set compact.
• Privilégier un partitionnement en place avec parcours linéaire. Le schéma de Hoare effectue souvent moins d’échanges que Lomuto, ce qui limite les écritures.
• Éviter les copies temporaires de larges segments. Le tri en place est plus « cache friendly » et limite les accès mémoire aléatoires.
• Regrouper les comparaisons et réduire les branches difficiles à prédire, par exemple en hoistant le pivot et en minimisant les tests dans la boucle critique.
• Utiliser un cutoff vers insertion sort sur les petits segments, qui parcourt séquentiellement la mémoire et profite des caches.

En synthèse : combinez médiane de trois ou échantillonnage léger pour le pivot, partition 3‑voies en présence de doublons, cutoff vers insertion sort pour les petits segments, et bascule vers introsort pour borner le pire cas. Vous obtiendrez ainsi un tri rapide et régulier sur des données variées.

Pourquoi le tri rapide est-il si important ?

Le tri rapide (Quicksort) est un pilier des tris en mémoire car il applique l’approche Diviser Pour Régner, choisit un pivot, partitionne, puis trie récursivement les sous‑tableaux. Dans les cas courant et favorable, sa complexité est quasi linéaire en O(n log n), ce qui en fait un excellent choix sur de grands tableaux et listes.

Par rapport à d’autres méthodes répandues comme mergesort et heapsort, Quicksort est apprécié pour son tri en place, sa très bonne localité mémoire et ses constantes faibles en pratique. Mergesort offre la stabilité et une garantie O(n log n) dans le pire cas au prix d’espace supplémentaire, tandis que heapsort garantit O(n log n) en pire cas et O(1) espace auxiliaire, mais avec des constantes moins favorables et une localité plus faible.

Quels avantages concrets ?

• Vitesse en pratique : dans le meilleur cas et en cas moyen, la complexité est en O(n log n), avec des constantes souvent très compétitives sur de grands volumes.
• Tri en place : l’algorithme opère directement dans le tableau, sans créer de copies volumineuses, ce qui limite l’empreinte mémoire.
• Bonne localité cache : le partitionnement travaille sur des zones contiguës, ce qui profite au cache et accélère les accès mémoire.
• Implémentations optimisées : des variantes comme la sélection aléatoire du pivot ou la médiane de trois réduisent la probabilité d’un mauvais pivot. Beaucoup d’implémentations basculent vers l’insertion sort sur de très petites partitions pour gagner du temps.
• Polyvalence : la même idée sous‑jacente sert à Quickselect pour trouver le k‑ième plus petit élément, utile en analyse de données.

Dans l’original, nous avons vu que « dans le meilleur des cas et dans le cas moyen, on observe une complexité quasi linéaire en O(n log n) ». Cet atout, conjugué au tri en place assuré par la fonction de partitionnement, explique sa popularité en production.

Quelles limites et quid de la stabilité ?

Non stable par défaut : Quicksort ne préserve pas l’ordre relatif des éléments égaux. Si vous triez par un champ secondaire après un tri par champ principal, cet ordre peut être perdu. Contournements possibles : utiliser une version stable du tri pour ce cas d’usage, décorer les éléments avec un indice initial, ou opter pour un algorithme stable.

Pire cas O(n²) : lorsque le pivot est systématiquement mauvais (par exemple sur des données déjà ou presque triées avec un pivot extrême), la profondeur de récursion peut grimper et le temps explose. Les variantes avec pivot aléatoire, médiane de trois ou la stratégie hybride introspective (qui bascule vers un tri garanti en pire cas) sont utilisées pour mitiger ce risque.

Profondeur de pile : la pile attendue est O(log n) avec des partitions équilibrées, mais elle peut atteindre O(n) dans le pire cas. Les mises en œuvre soignées limitent la profondeur via queue‑call elimination et tri du plus petit sous‑tableau en priorité.

Quand préférer mergesort ou heapsort ?

Critère	Quicksort	Mergesort	Heapsort
Cas moyen	O(n log n), très rapide en pratique	O(n log n)	O(n log n)
Pire cas	O(n2) si pivot défavorable	O(n log n)	O(n log n)
Stabilité	Non stable par défaut	Stable	Non stable
Mémoire auxiliaire	O(1) en place (hors pile)	O(n) typiquement en tableaux	O(1) en place
Localité/cache	Excellente	Bonne mais copies possibles	Moins bonne
Usage typique	Tri général rapide	Quand la stabilité est requise	Quand une garantie de pire cas et O(1) mémoire est prioritaire

En synthèse : choisissez mergesort si vous avez besoin de stabilité ou de garanties fortes en pire cas, au prix d’un espace supplémentaire. Choisissez heapsort si l’espace doit rester constant et que vous voulez la garantie O(n log n), en acceptant des constantes souvent moins favorables. Choisissez quicksort pour des tris en mémoire très rapides quand la stabilité n’est pas une contrainte.

Quelles applications typiques ?

• Fonctions de tri des bibliothèques standard : largement utilisé ou comme composant d’algorithmes hybrides dans les tris de bibliothèques (par exemple, implémentations inspirées de Quicksort ou à pivot double pour certains types primitifs).
• Bases de données : opérations de tri en mémoire pour ORDER BY, DISTINCT, groupements ou jointures nécessitant un pré‑tri.
• Traitements de données et science des données : prétraitements avant deux‑pointeurs, balayages, agrégations ou fusions.
• Quickselect : identification rapide du k‑ième élément (statistiques d’ordre) sur de grands jeux de données.
• Géométrie et graphisme : tri de points par coordonnée, préparation de structures pour des algorithmes de type enveloppe convexe.
• Compression et pipelines techniques : étapes de pré‑classement d’éléments avant encodage ou regroupement.

Ces usages s’appuient sur les qualités soulignées plus haut : en place, localité mémoire et performances proches de O(n log n) dans les scénarios usuels, telles que présentées dans l’article original.

Peut-on paralléliser QuickSort ?

Oui, car QuickSort repose sur l’approche DPR (Diviser Pour Régner) : une fois le tableau partitionné autour du pivot, les deux sous-tableaux de gauche et de droite sont indépendants. Il est donc naturel d’exécuter leurs appels récursifs en parallèle. En pratique, on lance le tri des deux sous-tableaux dans des tâches ou threads, puis on attend leur achèvement.

Concrètement, on conserve une partition souvent séquentielle et l’on parallélise les appels récursifs. Pour limiter les déséquilibres, le choix du pivot reste crucial, par exemple avec une médiane de trois valeurs tirées dans le tableau, ce qui évite de scinder en un très petit et un très grand sous-tableau.

Quand le paralléliser ?

La parallélisation est surtout utile pour de très grandes entrées et tant que la taille des sous-problèmes dépasse un certain seuil de granularité. On cherche à amortir le coût de création et de planification des tâches par rapport au travail utile de partitionnement et de tri.

• Grandes tailles d’entrée, lorsque le tri monopolise plusieurs cœurs pendant un temps significatif.
• Sous-tableaux de taille au moins égale à un seuil cutoff mesuré sur votre machine : au-dessus, on crée des tâches, en dessous, on reste séquentiel.
• Environnement multi-cœurs avec un pool de threads disponible, pour éviter la création/déstruction répétée de threads.
• Données sans ordre pathologique : privilégier un pivot aléatoire ou une médiane de trois pour améliorer l’équilibre de charge.

Quelles précautions prendre ?

• Synchronisation minimale : lancer deux tâches pour les sous-tableaux, puis join au niveau de l’appel courant. Éviter tout état partagé, chaque tâche travaille sur une plage d’indices disjointe.
• Limiter la surcharge de threads : utiliser un pool ou un planificateur de tâches, et borner la parallélisation au nombre de cœurs matériels. Ne pas créer un thread par appel récursif.
• Équilibre de charge : soigner le choix du pivot (aléatoire, médiane de trois) afin d’éviter des sous-tableaux très déséquilibrés qui laissent des cœurs inactifs.
• Seuil de granularité : définir un cutoff sous lequel on exécute séquentiellement, afin d’éviter que les très petits sous-tableaux ne génèrent plus d’overhead que de gain.
• Profondeur et pile : trier d’abord le plus petit sous-tableau et/ou utiliser une version itérative pour limiter la profondeur de récursion et la pression sur la pile.
• Localité et faux partages : travailler en place sur des plages contiguës, éviter que des threads n’écrivent dans des zones adjacentes en alternance.

En respectant ces principes, on obtient des accélérations proches du nombre de cœurs disponibles, sans s’attendre à une accélération parfaite, la partition restant souvent partiellement séquentielle et la création de tâches ayant un coût.