Sorting Race — pariez sur l'algorithme le plus rapide
Deux algorithmes de tri courent sur le même tableau. Pariez sur le gagnant : la meilleure complexité perd plus souvent qu'on ne croit. Gratuit.
Six courses. Même tableau, deux algorithmes : choisissez celui qui finira le premier.
Comment jouer
- Deux tris, un tableau. Misez sur celui qui finira le premier, puis regardez.
- Gagne celui qui utilise le moins d'opérations — comparaisons plus déplacements —, pas celui qui a la meilleure complexité théorique.
- Lisez la taille et la forme. En dessous d'une vingtaine de barres, les tris simples gagnent ; sur un tableau presque trié, l'insertion bat tout.
- Un bon choix rapporte 50, un mauvais coûte 50. Six courses, et vous démarrez avec 100.
Comment ça marche
Deux algorithmes de tri courent sur le tableau identique, dessiné en barres, et vous pariez sur celui qui finira le premier. Chaque manche oppose un tri en O(n log n) à un tri en O(n²) : il y a donc toujours un favori évident, et le favori évident se trompe environ une fois sur deux. Ce qui décide vraiment, c'est la taille du tableau et sa forme : le tri par insertion termine un tableau presque trié avec un vingtième des opérations qu'il faut à un tri rapide naïf, et en dessous d'une vingtaine d'éléments les facteurs constants l'emportent sur l'asymptotique — c'est précisément pour cela que les vraies bibliothèques de tri basculent sur l'insertion à cette taille. Le gagnant est déterminé par le nombre d'opérations, pas par un chronomètre : le résultat est donc le même sur n'importe quelle machine. Tout tourne sur votre appareil, rien n'est envoyé nulle part, et il n'y a aucun compte à créer.
Opérations signifie comparaisons plus déplacements de données, un échange comptant pour un, sur des implémentations de manuel. Les tris des vraies bibliothèques sont hybrides et gagneraient presque toutes les courses — c'est justement ce que l'on montre ici.
Questions fréquentes
Le meilleur algorithme n'est-il pas toujours le plus rapide ?
Pas à ces tailles. La notation O décrit comment le coût croît, pas ce qu'il vaut, et masque entièrement la constante. Mesuré sur 400 parties : parier sur la meilleure complexité théorique donne 3,19 bonnes réponses sur 6, contre 3,00 en pariant toujours du même côté. Deux règles — un tableau presque trié et un petit tableau favorisent tous deux le tri simple — en donnent environ 4,8 sur 6.
Comment le gagnant est-il déterminé ?
En comptant les comparaisons et les déplacements, calculés avant tout affichage. L'animation rejoue ce compte au même rythme des deux côtés : celui qui demande moins d'opérations termine donc en premier à l'écran pour la raison même qui le fait gagner. Un visualiseur faisant tourner deux boucles en temps réel donnerait une réponse différente sur une machine rapide et sur une lente.
Pourquoi le tri rapide s'effondre-t-il parfois ?
Il prend le dernier élément comme pivot, la version naïve. Sur un tableau déjà ou presque trié, c'est le pire choix possible : les partitions dégénèrent et il fait un travail quadratique précisément sur l'entrée que le tri par insertion traite le plus vite. Les vraies implémentations prennent une médiane de trois ou un pivot aléatoire justement pour l'éviter.
Que signifient les formes du tableau ?
Aléatoire est mélangé. Presque trié est en ordre à quelques échanges voisins près. Inversé est exactement à l'envers. Peu de valeurs n'en contient que quatre distinctes, et c'est là que la partition d'un tri rapide naïf s'écroule. Dents de scie répète plusieurs fois la même rampe.