06.10.2026 · Signal Titans Editorial
Tony Hoare ne connaissait pas les algorithmes de tri standards. Il a donc inventé Quicksort.
En 1959, Tony Hoare étudiait la traduction automatique à Moscou lorsqu’il rencontra un problème très concret : le dictionnaire anglais utilisé par le programme était stocké sur une longue bande magnétique.
Lire la bande du début à la fin prenait plusieurs minutes.
Si le programme cherchait un mot, rembobinait, puis cherchait le suivant, la traduction devenait extrêmement lente.
Hoare posa donc une question plus simple.
Et si les mots de la phrase étaient triés dans le même ordre alphabétique que le dictionnaire ?
La bande n’aurait alors besoin que d’un seul passage.
Il restait un problème.
Hoare ne connaissait pas les algorithmes de tri classiques.
Il en inventa donc un.
Cet algorithme devint Quicksort.
Le vrai problème n’était pas « comment trier ? »
Le vrai problème était la bande.
Une bande magnétique n’est pas une mémoire à accès aléatoire moderne. Pour atteindre une entrée plus loin, il faut physiquement parcourir ce qui vient avant. Revenir en arrière coûte cher.
Le dictionnaire était déjà stocké par ordre alphabétique.
Si les mots à traduire étaient eux aussi triés, toutes les recherches pouvaient se faire pendant une seule lecture vers l’avant.
Hoare avait donc besoin d’une méthode de tri suffisamment rapide pour que cette idée soit utile.
Il raconta plus tard qu’il n’avait pas étudié les méthodes de tri existantes. L’algorithme venait d’un raisonnement direct sur la structure du problème.
L’idée centrale tient sur une serviette
Choisissez un élément comme pivot.
Mettez les éléments plus petits d’un côté.
Les plus grands de l’autre.
Puis répétez le même processus sur les deux groupes plus petits.
C’est le cœur de Quicksort.
Les détails comptent. Un mauvais pivot peut produire un très mauvais worst case. Une bonne implémentation exige un partitionnement soigneux et des choix d’ingénierie pratiques.
Mais le mouvement conceptuel est minuscule.
Au lieu de rechercher sans cesse le prochain plus petit élément, on divise le problème en deux versions plus simples de lui-même.
Quicksort a transformé une contrainte en structure
La bande était lente d’une manière très précise.
Cette contrainte força Hoare à réfléchir à l’ordre d’accès.
Le résultat ne fut pas une astuce limitée aux bandes magnétiques.
Il devint l’un des algorithmes de tri les plus connus de l’informatique.
Ce motif revient souvent en ingénierie.
Une limite mémoire crée une meilleure structure de données.
Une limite de bande passante crée un meilleur encodage.
Une limite de batterie crée une meilleure planification.
Une étape manuelle pénible crée de l’automatisation.
La contrainte ressemble d’abord à ce qui empêche le progrès.
Parfois, c’est elle qui révèle la forme de la solution.
Ne pas connaître la réponse standard peut parfois aider
La version dangereuse de cette leçon serait de dire que l’ignorance est bonne.
Elle ne l’est pas.
Connaître la littérature existante évite le plus souvent des années de travail inutile.
La leçon plus étroite est différente.
Lorsque vous comprenez profondément le problème sous-jacent, ne pas être enfermé dans l’implémentation habituelle peut parfois faire apparaître une autre structure.
Hoare ne devinait pas au hasard.
Il savait exactement quel coût il voulait supprimer.
Il savait quelle opération rendait la machine lente.
Cette clarté comptait plus qu’un catalogue de techniques de tri.
Les équipes logicielles optimisent encore souvent la mauvaise couche
Une page est lente, donc on réécrit le frontend.
Le vrai goulot d’étranglement est un aller-retour vers la base de données.
Un build est lent, donc on achète des runners plus rapides.
Le vrai problème est l’invalidation des dépendances.
Un workflow IA coûte cher, donc on change de modèle.
Le vrai problème est que le même contexte est traité cinq fois.
Quicksort n’a pas commencé par « inventons un algorithme légendaire ».
Il a commencé par « arrêtons de rembobiner la bande ».
Hoare a consacré le reste de sa carrière à rendre les programmes plus faciles à raisonner
Quicksort ne fut qu’une partie de son travail.
Hoare fit ensuite des contributions fondamentales aux langages de programmation, à la correction des programmes et à la concurrence. Hoare logic donna une manière rigoureuse de raisonner sur ce qu’un programme doit garantir avant et après son exécution. Communicating Sequential Processes influença profondément la théorie des systèmes concurrents.
Il reçut l’ACM Turing Award pour ses contributions fondamentales à la définition et au design des langages de programmation.
Le fil conducteur est clair.
Prendre un processus compliqué.
Trouver la structure en dessous.
Rendre cette structure assez explicite pour que les humains puissent raisonner dessus.
La bonne question se trouve souvent une couche plus bas
« Il nous faut une recherche plus rapide » peut vouloir dire « nous rescannons les mêmes données trop souvent ».
« Il nous faut plus de personnes » peut vouloir dire « trop de travail est répété ».
« Il nous faut un meilleur algorithme » peut vouloir dire « nous n’avons pas encore identifié l’opération réellement coûteuse ».
Chaque système moderne possède sa propre bande magnétique.
Une ressource est lente.
Une transition coûte cher.
Une action répétée domine le temps total.
Qu’est-ce que votre système “rembobine” encore et encore parce que personne n’a remis en question l’ordre du travail ?
Sources
- Computer History Museum — Oral History of Sir Antony Hoare
- Microsoft Research — Tony Hoare
- Microsoft Research — biographie et découverte de Quicksort à Moscou
- Microsoft Research — Tony Hoare speaker biography
- Image à la une — Tony Hoare à l’ETH Zurich en 1994, photo Andreas F. Borchert, CC BY-SA 4.0 via Wikimedia Commons. Adaptée à un cadre 16:9 ; l’œuvre dérivée reste sous CC BY-SA 4.0.
SIGNAL TITANS