Course d'algorithmes de tri

suivez pas à pas deux algorithmes qui s'affrontent sur la même entrée — comparaisons, échanges, complexité

Chargement de la simulation interactive...

le Big-O ne dit pas tout 🖖

Le tri à bulles effectue exactement n(n−1)/2 comparaisons dans le pire des cas — environ 2 000 pour n=64. Chaque passage doit parcourir toute la région restante non triée, sans sortie anticipée. Le partitionnement du tri rapide place le pivot à sa position finale et divise le problème en deux sous-problèmes ; chaque niveau de récursion effectue un travail O(n) sur O(log n) niveaux, soit O(n log n) au total. Le piège : si le pivot tombe toujours à une extrémité — par exemple une entrée triée avec le dernier élément comme pivot — le partitionnement dégénère en n sous-problèmes de taille n−1, n−2, ... totalisant O(n²). Le pivot d'élément médian utilisé ici évite ce piège, ce qui explique pourquoi une entrée inversée reste rapide. Les valeurs peu uniques constituent le cas intéressant : lorsque de nombreux éléments sont égaux au pivot, échanger des valeurs identiques gaspille du travail et peut se rapprocher du quadratique. Le Big-O indique la classe de croissance ; les constantes, la sensibilité à l'entrée et le comportement du cache déterminent l'algorithme réellement le plus adapté.

Pourquoi compter les étapes, pas les secondes 🖖

Cette course évalue chaque algorithme en comptant les comparaisons et les échanges, pas au chronomètre. Le temps réel dépend de votre processeur, du navigateur et de ce qui tourne par ailleurs, si bien que le même code peut sembler rapide ou lent selon la machine. Compter les opérations donne une mesure nette et reproductible du travail réellement effectué : la même entrée produit toujours les mêmes totaux, ce qui vous permet de comparer les algorithmes eux-mêmes et non le matériel.

Quicksort est né en traduisant le russe 🖖

Tony Hoare a inventé Quicksort en 1959, alors qu'il était étudiant invité à Moscou et travaillait sur un projet de traduction automatique. Pour chercher une phrase russe dans le dictionnaire, il devait d'abord ranger ses mots par ordre alphabétique — et la méthode habituelle était désespérément lente. Sa solution, le partitionnement autour d'un pivot, est devenue l'un des algorithmes les plus utilisés au monde. Les barres qui s'affrontent ici viennent d'un problème de langue, pas d'informatique.

Problème entièrement résolu

Prédiction exacte du nombre d'échanges du tri à bulles sur 64 éléments inversés 7 étapes
Exécutez la course avec le préréglage inversé — 64 éléments, du plus grand au plus petit. Prédisez exactement le nombre d'échanges du tri à bulles, et non son ordre de croissance ; puis expliquez ce qui empêche tout algorithme d'échange de voisins de faire mieux.
1. Une inversion est une paire située dans le mauvais ordre relatif. Une entrée inversée représente le cas extrême : pour tout i < j, l'élément situé en amont est le plus grand, si bien que chaque paire est inversée et que le décompte correspond à la totalité des paires. Obtenez ce nombre avant que quoi que ce soit ne se déplace — il s'avère constituer l'intégralité du problème.
  
  $I = # {(i, j) : i < j, a_{i} > a_{j}} = (2 64) = \frac{64 \times 63}{2} = 2, 016$
2. Le tri à bulles n'échange que des voisins adjacents, et seulement lorsqu'ils ne sont pas dans l'ordre. Un tel échange corrige cette seule paire sans en perturber aucune autre, car les deux éléments qui se déplacent conservent la même relation avec tout ce qui leur est extérieur. Un échange, une inversion — jamais deux, jamais aucune.
  
  $a_{k} > a_{k + 1} ⟶ I \mapsto I - 1$
3. Être trié signifie comporter zéro inversion. Partir de 2 016 et en retirer exactement une par échange ne laisse aucune marge de manœuvre : le nombre d'échanges est imposé. Le panneau affiche 2 016 échanges, et il s'agit d'une égalité stricte plutôt que d'une borne de pire cas.
  
  $S = I_{0} - 0 = 2, 016$
4. Les comparaisons constituent un décompte distinct qui se trouve coincider ici. La passe i balaye j = 0 … 62 − i, la somme est donc 63 + 62 + ⋯ + 1 — le même nombre 2 016 qu'affiche la ligne pire cas tri à bulles n(n−1)/2. Des décomptes égaux signifient que chaque comparaison a trouvé une inversion, ce qui est le sens de « pire cas » ici. Le compteur sous le titre de chaque panneau compte une étape par comparaison plus une par échange, de sorte qu'il indique étape 0 / 4 032 avant de commencer, et le bouton › consomme exactement une de ces étapes par clic. Le O(n²) à côté du titre est une étiquette, non un décompte.
  
  $C = i = 0 \sum 62 (63 - i) = 63 + 62 + \dots + 1 = \frac{63 \times 64}{2} = 2, 016 = \frac{n ( n - 1 )}{2}, C + S = 4, 032$
5. Généralisons maintenant l'étape 2, car c'est ce que le tri rapide exploite. Échanger deux éléments distants de d positions laisse inchangée au total chaque paire formée avec un élément situé à l'extérieur de l'intervalle : un tel élément est à nouveau comparé à l'autre extrémité, les deux comparaisons échangent leurs rôles, et sa contribution demeure inchangée. Ce qui peut varier, c'est la paire elle-même, ainsi que les 2(d − 1) paires que chaque extrémité forme avec les d − 1 éléments situés entre elles. Au maximum 2d − 1 inversions peuvent être éliminées par échange, et poser d = 1 redonne l'inversion unique de l'étape 2.
  
  $1 + 2 (d - 1) = 2 d - 1 (d = 1 \Rightarrow 1)$
6. La première partition du tri rapide prend l'élément du milieu comme pivot, a[31] = 33, et échange (0, 63), (1, 62), … , (31, 32) — soit 32 échanges à des distances de 63, 61, … , 1. L'étape 5 plafonne leur effet combiné à 2 016 inversions, et cette unique passe laisse le tableau entièrement trié, de sorte qu'exactement 2 016 inversions ont été éliminées. Le plafond est atteint avec égalité : chacun des 32 échanges a atteint son propre maximum.
  
  $p = a_{31} = 33, d = 63, 61, \dots, 1 : m = 1 \sum 32 (2 (2 m - 1) - 1) = m = 1 \sum 32 (4 m - 3) = 2, 112 - 96 = 2, 016$
7. Les deux algorithmes ne rivalisent donc pas d'ingéniosité, mais de portée. Les 334 comparaisons et 64 échanges affichés pour le tri rapide totalisent 398 sur son compteur — et seuls 32 de ces échanges déplacent effectivement quelque chose, les 32 autres correspondant à l'échange du pivot avec lui-même dans des sections déjà ordonnées. Ses 334 se situent également en dessous de la référence affichée de 384 pour n·log₂n, car l'élément central d'une suite inversée est sa médiane, de sorte que chaque découpage est équilibré.
  
  $334 + 64 = 398, 64 lo g_{2} 64 = 384, \frac{2 , 016}{32} = 63$
Réponse

2 016 échanges et 2 016 comparaisons — les 4 032 étapes du compteur. Et 2 016 n'est pas un fait propre au tri à bulles : c'est un plancher pour toute une famille. Tout algorithme limité à l'échange d'éléments adjacents — tri par insertion, tri cocktail, tri du gnome, ou un algorithme que personne n'a encore écrit — supprime au maximum une inversion par échange d'après l'étape 2, de sorte que tous nécessitent au moins 2 016 échanges sur cette entrée et tous sont en Ω(n²) sur des données inversées en raison du modèle dans lequel ils opèrent, et non parce qu'ils sont maladroits. Le tri rapide échappe à ce plancher car il lui est permis de déplacer un élément de 63 positions d'un coup : 2 016 inversions éliminées par 32 échanges réels représentent 63 inversions par échange, et l'étape 5 indique que c'est le maximum qu'un unique échange sur cette distance aurait pu accomplir. Le panneau ne calcule ni le nombre d'inversions ni la borne inférieure qu'il implique.

$S \geq I_{0} = (2 64) = 2, 016 (d = 1), \frac{I _{0}}{32} = 63$

Parcours

Compter le travail, pas les secondes

Mène à recursion-tree

Références (1)

Insight block 3 — quicksort as its author published it: C. A. R. Hoare, "Quicksort." The Computer Journal 5(1), 10–16, 1962. The algorithm first appeared the year before as C. A. R. Hoare, "Algorithm 64: Quicksort", Communications of the ACM 4(7), 321, 1961.

Par l’équipe 42Math · Mis à jour 2026-05-27

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

presque trié - La distribution des données d'entrée modifie l'efficacité relative des algorithmes.
inversé - Le tri à bulles effectue 2 016 comparaisons et 2 016 échanges : chaque comparaison trouve sa paire dans le désordre, puisque l'inversion de 64 éléments retourne les 2 016 paires d'un seul coup. Le tri rapide s'en acquitte en 334 comparaisons et 64 échanges, en dessous de sa propre référence n·log₂n de 384, car l'élément central d'un tableau inversé correspond très exactement à la médiane lors de chaque partition.
peu de valeurs uniques - Quatre-vingts éléments tirés de seulement huit valeurs distinctes. Le tri rapide nécessite 534 comparaisons face à sa référence n·log₂n de 506, le seul des trois préréglages où il dépasse sa propre courbe : les éléments égaux au pivot sont échangés en pure perte. Le tri à bulles conserve ses 3 160 comparaisons fixes et n'effectue que 1 330 échanges, car un grand nombre de paires adjacentes sont déjà identiques.