Quicksort
En 1961, Charles Antony Richard Hoare ne se doutait pas, qu'il venait de concevoir l'un des algorithmes les plus durables de l'informatique. Son Quicksort naît dans un contexte particulier où les ordinateurs traitent des volumes de données croissants et les méthodes de tri traditionnelles montrent leurs limites. Alors jeune chercheur britannique, il propose une approche radicalement différente.
L'idée paraît simple au premier regard. On choisit un élément du tableau, le « pivot », puis on réorganise les autres éléments autour de lui : les plus petits d'un côté, les plus grands de l'autre. On répète ensuite l'opération sur chaque moitié jusqu'à obtenir un tableau entièrement trié. Cette méthode de « diviser pour régner » révolutionne l'approche du tri en informatique.
Sa publication de 1962 dans le Computer Journal présente les premiers résultats formels. Il y démontre que son algorithme surpasse nettement les méthodes existantes. Mais l'histoire de Quicksort ne fait que commencer.
Dès 1965, R.S. Scowen repère une faiblesse dans le choix aléatoire du pivot. Il développe Quickersort, qui sélectionne plutôt l'élément médian du tableau. Cette modification change la donne pour les tableaux partiellement triés, qui posaient problème à la version originale de Hoare.
R.C. Singleton franchit une nouvelle étape en 1969 avec sa méthode median of three. Au lieu de se contenter d'un seul élément, il examine trois valeurs : le premier élément, celui du milieu et le dernier. Il choisit ensuite la médiane de ces trois comme pivot. Cette astuce améliore les performances moyennes d'environ 5%, un gain substantiel pour l'époque.
Robert Sedgewick transforme véritablement la compréhension de l'algorithme. Soutenue à Stanford en 1975, sa thèse de doctorat dissèque mathématiquement Quicksort sous tous ses aspects. Ses travaux, publiés par la suite en 1977 dans Acta Informatica, établissent des formules précises pour calculer le temps d'exécution sur des machines réelles. Il ne s'arrête pas à la théorie et introduit le loop unwrapping, une technique qui réduit les coûts de gestion des boucles internes.
L'année suivante, en 1978, Sedgewick propose une nouvelle méthode de partitionnement qui fera office de référence. Deux indices parcourent le tableau en sens inverse, se rapprochant progressivement l'un de l'autre. Cette approche minimise le nombre d'échanges d'éléments, accélérant l'exécution.
Les années 1980 voient naître des variantes plus sophistiquées. Roger L. Wainwright explore en 1985 une approche hybride avec Bsort, qui mélange les techniques de Quicksort et du tri à bulles. Deux ans plus tard, il développe Qsorte, capable de détecter les sous-séquences déjà triées et d'éviter ainsi des partitionnements inutiles.
En 1993, les travaux de Bentley et McIlroy ont pour objectif de créer une version optimisée pour la bibliothèque standard du langage C. Ils conçoivent un algorithme adaptatif qui change de stratégie selon la taille du tableau. Leur innovation la plus remarquable reste le partitionnement fat en trois parties, spécialement conçu pour traiter efficacement les tableaux contenant de nombreux éléments identiques.
À la fin du XXe siècle et au début du XXIe, les chercheurs adaptent Quicksort aux chaînes de caractères, aux architectures parallèles et aux grandes bases de données. L'algorithme s'installe dans pratiquement toutes les bibliothèques standard des langages de programmation modernes.
Au-delà de ses performances, Quicksort marque les esprits par sa structure élégante. Il sert de cas d'école pour enseigner les techniques de division-conquête et l'analyse probabiliste des algorithmes. Les étudiants en informatique du monde entier décortiquent son fonctionnement, apprennent à calculer sa complexité et comprennent pourquoi il fonctionne si bien en moyenne.
L'évolution de Quicksort reflète celle de l'algorithmique dans son ensemble. Les premiers travaux se concentraient sur la complexité théorique, cherchant à prouver mathématiquement l'efficacité des méthodes. Progressivement, l'attention s'est déplacée vers les performances pratiques.
Plus de soixante ans après sa naissance, Quicksort garde toute sa pertinence. Sa rapidité moyenne, sa faible consommation mémoire et sa fiabilité en font le choix par défaut de nombreux systèmes informatiques. Les processeurs modernes, les nouvelles architectures et les volumes de données toujours croissants continuent d'inspirer les chercheurs qui adaptent encore cet algorithme vénérable.