Course d'algorithmes de tri

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é.

Cette course évalue chaque algorithme en comptant les comparaisons et les échanges, pas au chronomètre. Le temps réel dépend de ton 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 te permet de comparer les algorithmes eux-mêmes et non le matériel.

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.