Gagnant
Opérations
Terminés

  • Comparées
  • Marquées (minimum, pivot ou clé)
  • Échangées ou déplacées
  • En place
Rang Tri Comparaisons ou lectures Échanges ou déplacements Opérations

En savoir plus sur les algorithmes de tri

Course des tris

Quel algorithme de tri est le plus rapide ? Tout dépend de la liste. La Course des tris lance les huit algorithmes de tri en même temps sur la même liste, un couloir chacun, et compte chaque comparaison, lecture, échange et déplacement comme une opération. Les couloirs avancent au fil de leurs compteurs : vous voyez les tris efficaces finir pendant que les lents échangent encore, et l'ordre d'arrivée changer quand la liste est presque triée ou inversée. Appuyez sur Lecture pour regarder les huit algorithmes de tri faire la course sur la même liste, ou sur Étape et Retour pour avancer d'une opération à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. Chaque comparaison, lecture, échange ou déplacement compte pour une opération, et chaque couloir avance au rythme de son propre compteur : le tri qui demande le moins d'opérations finit donc en premier. Choisissez le nombre de barres et leur ordre de départ, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Choisissez le nombre de barres et leur ordre de départ : aléatoire, presque trié, inversé ou avec peu de valeurs distinctes. Ou saisissez vos propres nombres.
  2. Appuyez sur Lecture et regardez les huit couloirs. Étape et Retour avancent ou reculent d'une opération ; le curseur d'étapes va n'importe où dans la course.
  3. Comparez le tableau des résultats, puis essayez une liste presque triée et une liste inversée pour voir le classement changer.

Comment se déroule la course

Les huit tris reçoivent la même liste. Chaque comparaison de deux valeurs, chaque chiffre ou valeur lu par le tri par base et le tri par comptage, et chaque échange ou déplacement compte pour une opération. À chaque instant de la course, chaque couloir montre où en est son tri avec ce nombre d'opérations. Un tri qui demande moins d'opérations arrive plus tôt au bout. Le tableau des résultats indique, pour chaque tri, les comparaisons, les échanges ou déplacements et le total.

Ce que montrent les résultats

Sur 40 valeurs aléatoires, le tri par comptage demande environ 120 opérations, le tri par base environ 240, le quicksort environ 260 et le tri fusion environ 380. Le tri par tas suit avec environ 490, tandis que le tri par sélection et le tri par insertion demandent environ 820 et le tri à bulles plus de 1 100. Sur une liste presque triée, le tri par insertion gagne avec environ 50, et le tri à bulles arrive deuxième. Sur une liste inversée, le tri à bulles et le tri par insertion demandent tous deux 1 560. Le tri par comptage et le tri par base gagnent si souvent parce que ces valeurs sont de petits entiers ; sur d'autres données, ils sont tout simplement inutilisables.

Questions fréquemment posées

Quel est l'algorithme de tri le plus rapide ?

Tout dépend des données. Pour de petits entiers, le tri par comptage et le tri par base demandent le moins d'opérations. Pour des données quelconques, le quicksort et le tri fusion sont les plus rapides sur des listes aléatoires, et le tri par insertion sur des listes presque triées. Le tri à bulles et le tri par sélection sont lents, sauf sur les toutes petites listes.

Qu'est-ce qui compte comme une opération ?

Chaque comparaison de deux valeurs, chaque chiffre ou valeur lu par le tri par base et le tri par comptage, et chaque échange ou déplacement d'une valeur. C'est un modèle simple : les temps d'exécution réels dépendent aussi des accès à la mémoire et du coût de chaque opération.

Pourquoi le tri par comptage et le tri par base gagnent-ils si souvent ?

Parce qu'ils ne comparent jamais les valeurs. Ils tirent parti du fait que les valeurs sont de petits entiers : leur travail croît avec n plus l'étendue des valeurs, et non avec n log n. Sur des données qui ne sont pas de petits entiers, ils ne s'appliquent pas.

Pourquoi le tri par insertion gagne-t-il sur une liste presque triée ?

Parce que son travail vaut le nombre de valeurs plus le nombre de paires mal ordonnées. Une liste presque triée en compte très peu, donc chaque valeur ne bouge que d'une ou deux places.

Mes nombres sont-ils envoyés quelque part ?

Non. La course tourne dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur