Combien de comparaisons pour trier 10 000 éléments ?
Pour 10 000 éléments, un tri simple fait près de 50 millions de comparaisons contre environ 120 000 pour le tri fusion.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Tri à bulles ou par sélection
- 49 995 000 comparaisons
- Tri fusion, pire cas
- 123 617 comparaisons
- Minimum théorique de tout tri par comparaisons
- 118 459 comparaisons
- Rapport tri simple / tri fusion
- × 404,4
Le cas en détail
Le nombre de comparaisons du tri simple croît comme le carré de la taille. À 10 000 éléments, il atteint presque 50 millions. Le tri fusion en fait environ 120 000, soit plus de 400 fois moins.
À retenir : Les bibliothèques standard de vos langages utilisent des tris performants : appelez-les plutôt que de réécrire un tri.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Nombre d'éléments à trier (n) : 10000
- Tri à bulles ou par sélection
- 49 995 000 comparaisons
- Tri fusion, pire cas
- 123 617 comparaisons
- Minimum théorique de tout tri par comparaisons
- 118 459 comparaisons
- Rapport tri simple / tri fusion
- × 404,4
Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
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 !).
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.