Combien de comparaisons pour trier un million d'éléments ?
Pour un million d'éléments, un tri simple demande 500 milliards de comparaisons contre environ 19 millions pour le tri fusion.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Tri à bulles ou par sélection
- 499 999 500 000 comparaisons
- Tri fusion, pire cas
- 18 951 425 comparaisons
- Minimum théorique de tout tri par comparaisons
- 18 488 885 comparaisons
- Rapport tri simple / tri fusion
- × 26 383,2
Le cas en détail
L'écart devient vertigineux : le tri simple est environ 26 000 fois plus lent. Un tri simple prendrait plusieurs minutes, quand un tri fusion se termine en une fraction de seconde. C'est la raison pour laquelle la complexité compte.
À retenir : Si un programme ralentit fortement quand les données grossissent, cherchez d'abord une double boucle cachée.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Nombre d'éléments à trier (n) : 1000000
- Tri à bulles ou par sélection
- 499 999 500 000 comparaisons
- Tri fusion, pire cas
- 18 951 425 comparaisons
- Minimum théorique de tout tri par comparaisons
- 18 488 885 comparaisons
- Rapport tri simple / tri fusion
- × 26 383,2
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.