Combien de comparaisons pour trier 100 éléments ?
Pour 100 éléments, un tri simple fait 4 950 comparaisons contre 573 au pire pour le tri fusion.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Tri à bulles ou par sélection
- 4 950 comparaisons
- Tri fusion, pire cas
- 573 comparaisons
- Minimum théorique de tout tri par comparaisons
- 525 comparaisons
- Rapport tri simple / tri fusion
- × 8,6
Le cas en détail
n (n - 1) / 2 donne 4 950 pour n = 100. Le tri fusion, au pire cas, en fait 100 × 7 - 128 + 1 = 573. Le rapport est déjà proche de 9, et il grandit avec n.
À retenir : Pour trier de petites listes, un tri simple suffit. Pour de grosses listes, choisissez un tri en n log n.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Nombre d'éléments à trier (n) : 100
- Tri à bulles ou par sélection
- 4 950 comparaisons
- Tri fusion, pire cas
- 573 comparaisons
- Minimum théorique de tout tri par comparaisons
- 525 comparaisons
- Rapport tri simple / tri fusion
- × 8,6
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.