Comparaisons : tri simple contre tri fusion

Trier 1 000 éléments avec un tri simple demande près de 500 000 comparaisons, contre moins de 9 000 pour un tri fusion. Saisissez n pour voir l'écart grandir.

Jimenez JulienPar , éditeur de Calepin Binaire · mis à jour le

Tri à bulles ou par sélection
499 500 comparaisons
Tri fusion, pire cas
8 977 comparaisons
Minimum théorique de tout tri par comparaisons
8 530 comparaisons
Rapport tri simple / tri fusion
× 55,6

Comment ça se calcule

Le tri à bulles et le tri par sélection comparent tous les couples : n (n - 1) / 2 comparaisons. Le tri fusion, au pire, en fait n × plafond(log2 n) - 2^plafond(log2 n) + 1. Le minimum théorique d'un tri par comparaisons est le plafond de log2(n !).

Questions fréquentes

Existe-t-il un tri plus rapide que n log n ?

Pas par comparaisons : c'est une borne démontrée. Certains tris sans comparaison, comme le tri par dénombrement, font mieux dans des cas particuliers.

Pourquoi enseigne-t-on encore le tri à bulles ?

Pour sa simplicité : il illustre bien le principe et l'effet d'une complexité quadratique.

Cas fréquents

Des exemples déjà remplis, avec leur explication :

Intégrer cet outil sur votre site

Copiez ce code pour afficher l'outil sur votre site ou votre blog. L'outil s'exécute dans le navigateur du visiteur, sans cookie ni suivi, et affiche un lien « Propulsé par Calepin Binaire » vers cette page.

Aperçu de la version intégrable : https://mircode.org/embed/nombre-de-comparaisons-tri-simple-contre-tri-fusion/

Les résultats sont fournis à titre indicatif. Pour aller plus loin, découvrez les sites de la catégorie Sandbox et casse-têtes de l'annuaire et lisez le guide de cette catégorie.

Autres outils

Voir les 35 outils