Trier 8 éléments : un cas à la main
Pour 8 éléments, un tri simple fait 28 comparaisons et le tri fusion 17 au pire.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Tri à bulles ou par sélection
- 28 comparaisons
- Tri fusion, pire cas
- 17 comparaisons
- Minimum théorique de tout tri par comparaisons
- 16 comparaisons
- Rapport tri simple / tri fusion
- × 1,6
Le cas en détail
8 est une puissance de 2, ce qui simplifie : 8 × 3 - 8 + 1 = 17 comparaisons pour le tri fusion. Le minimum théorique est de 16 comparaisons. On peut donc trier 8 éléments en pratiquement l'optimum.
À retenir : Compter à la main sur 8 éléments est un bon exercice pour comprendre le tri fusion.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Nombre d'éléments à trier (n) : 8
- Tri à bulles ou par sélection
- 28 comparaisons
- Tri fusion, pire cas
- 17 comparaisons
- Minimum théorique de tout tri par comparaisons
- 16 comparaisons
- Rapport tri simple / tri fusion
- × 1,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.