Math
Course des tris
Trois tris parcourent le même tableau à la même vitesse en COMPARAISONS, et le premier arrivé est celui qui a posé le moins de questions. C'est le désordre qui décide, pas la taille : sur une entrée déjà triée, l'insertion prend 63 comparaisons et le tri rapide 2016.
Ce qui se passe
Trois couloirs, un tableau et un budget de travail commun : les trois tris avancent du même nombre de comparaisons - ou de déplacements, si vous changez d'unité -, donc le premier arrivé est celui qui a eu besoin du moins de cette unité, pas celui qui est dessiné plus vite. Chaque couloir parle la même langue : les deux clés comparées sont cerclées d'or, une clé qui vient d'être écrite clignote en vert, un pivot porte un repère rouge, le segment traité est entre crochets, les éléments à leur place définitive reçoivent un pied vert, et la clé que tient le tri par insertion flotte au-dessus de l'emplacement où elle tombera. Prédisez le vainqueur avant « Partez », ou faites avancer la course unité par unité. Essayez les entrées : sur un tableau trié l'insertion finit presque aussitôt tandis que le tri rapide avec le dernier élément comme pivot atteint son pire cas ; l'ordre inverse est le pire cas de l'insertion ; avec des clés répétées la couleur est la position dans l'entrée, et la fusion garde les clés égales dans l'ordre tandis que le tri rapide les mélange. Chaque couloir montre aussi le temps réel de l'exécution sur cet ordinateur - une troisième grandeur, jamais l'unité de la course.
Équations du module
Équations n éléments, et la course se mesure en COMPARAISONS - la quantité dont parlent les formules le tri par insertion DÉPLACE un élément exactement autant de fois que le tableau compte d'inversions : une identité sur CHAQUE permutation, vérifiée sur les n! pour n <= 8 comparaisons de l'insertion = inversions + (n − 1) − (minima des préfixes en i >= 1) ; moyenne = n(n−1)/4 + n − H_n EXACTEMENT : n = 8 -> 19.282142857142858 ; n = 64 -> 1067.2561090962943 tri rapide (Lomuto, dernier élément comme pivot) moyenne = 2(n+1)H_n − 4n EXACTEMENT : n = 8 -> 16.921428571428571 ; n = 64 -> 360.70581748175005 tri fusion, pire cas = n·ceil(lg n) − 2^ceil(lg n) + 1 - une formule, non une borne : 321 pour n = 64, contre ceil(lg n!) = 296, le plancher de TOUT tri par comparaisons les deux sont égaux pour n <= 4 et s'écartent ensuite ; le tri fusion écrit aussi n·lg n éléments quelle que soit l'entrée - 384 pour n = 64 64 éléments, toutes les places mélangées : 1001 inversions ; insertion 1057 comparaisons / 1001 déplacements, fusion 307 / 384, tri rapide 352 / 306 64 éléments, entrée triée : insertion 63, fusion 192, tri rapide 2016 - et 2016 est n(n−1)/2, le PIRE cas du tri rapide la fusion passe devant l'insertion à 15 places mélangées sur 64 (269 contre 246) : le seuil est le désordre, non la taille - sur une entrée aléatoire la fusion est devant dès n = 4 clés égales, 64 éléments sur 8 valeurs : paires laissées en ordre inverse - insertion 0, fusion 0, tri rapide 77
