Comparaisons de performances
Présentation
Cette section propose de comparer les performances des différents algorithmes de tri. Les mesures ont été effectuées sur un ordinateur équipé d’un processeur ATHLON XP 2400+ et de 256 MO de mémoire DDR, le système d’exploitation utilisé étant windows XP. Les programmes qui ont été utilisés pour mener cette étude sont les programmes JAVA présentés dans les sections suivantes.
Performances théoriques
Le premier tableau présente les performances théoriques des différents algorithmes. Le cas moyen correspond à un tableau quelconque, sans ordre particulier. Le meilleur des cas correspond à un tableau préalablement triée (sauf pour les tris dichotomiques comme le tri rapide : se reporter au calcul de la complexité de ce tri). Le pire des cas à une liste préalablement triée à l’envers (sauf pour les tris dichotomiques comme le tri rapide : se reporter au calcul de la complexité de ce tri).
| Algorithme | Pire des cas | En moyenne | Meilleur des cas |
| Tri Bulle | O(n2) | ||
| Tri Bulle Optimisé | O(n2) | ||
| Tri par Selection | O(1/2 * n2) | O(1/2 * n2) | O(1/2 * n2) |
| Tri par Insertion | O(1/2 * n2) | O(1/4 * n2) | |
| Tri Shell | O(n2) | O(n2) | |
| Tri Fusion | O(n * lg(n)) | O(n * lg(n)) | O(n * lg(n)) |
| Tri Rapide | O(n * lg(n)) | O(n * lg(n)) | O(n2) |
| Tri Casier | O(n + m) | O(n + m) | O(n + m) |
| Tri par Création | O(n2) | O(n2) | O(n2) |
| Tri par Arbre Binaire de Recherche | O(n * lg(n)) | O(n * lg(n)) | O(n * lg(n)) |
n = nombre d’éléments à trier m = cardinal des éléments à trier
Mesures effectuées
Des tests sur des tableaux quelconques ont été menées, le temps (en millisecondes) pour trier différents éléments ont été réalisées. Les mesures sont répertoriées dans le tableau qui suit : (Ces test ont été menés sur des tableaux ayant des valeurs comprises entre -9999 et 9999).
| Algorithme | |||||||||||||||
| 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 | 65536 | 131072 | 262144 | 524288 | 1048576 | 2097152 | 4194304 | 8388608 | |
| Tri bulle | 0 | 16 | 31 | 125 | 500 | 2000 | 8625 | 34265 | 180062 | ??? | ??? | ??? | ??? | ??? | ??? |
| Tri bulle optimisé | 0 | 16 | 15 | 94 | 344 | 1312 | 5594 | 24546 | 168406 | ??? | ??? | ??? | ??? | ??? | ??? |
| Tri par selection | 0 | 0 | 16 | 31 | 140 | 547 | 2281 | 9312 | 49578 | 228407 | ??? | ??? | ??? | ??? | ??? |
| Tri par insertion | 0 | 0 | 0 | 31 | 125 | 484 | 2000 | 8625 | 43953 | 258532 | ??? | ??? | ??? | ??? | ??? |
| Tri Shell | 0 | 0 | 0 | 0 | 0 | 16 | 15 | 32 | 63 | 141 | 297 | 703 | 1609 | 3813 | 8406 |
| Tri Fusion | 0 | 0 | 0 | 0 | 0 | 0 | 16 | 31 | 62 | 140 | 266 | 563 | 1172 | 2391 | 4922 |
| Tri Rapide | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 15 | 31 | 62 | 141 | 375 | 922 | 2610 | 8235 |
| Tri Casier | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 16 | 0 | 15 | 16 | 31 | 62 | 109 | 234 |
| Tri par création | 16 | 0 | 47 | 140 | 578 | 2250 | 8953 | 30016 | 111172 | ??? | ??? | ??? | ??? | ??? | ??? |
| Tri par Arbre Binaire de Recherche | 0 | 0 | 0 | 0 | 15 | 16 | 78 | 140 | 407 | 954 | 2875 | 7890 | ??? | ??? | ??? |
Les résultats obtenus semblent bien correspondre aux résultats thèoriques obtenus grace à l’évaluation de la complexité. Les tris le plus performant pour trier un grand nombre d’entiers est donc bien le tri casier. Dans le cas général, le tri fusion offre des performances appréciables, comparables aux performances du tri rapide.
Performances du tri casier
Le tableau suivant présente les mesures effectuées avec le tri casier en faisant varier l’intervalle d’appartenance des valeurs à trier (le nombre de valeur à trier étant constant et vallant 1 000 000). On constate alors que le temps mis par l’algorithme pour trier les valeurs augmente dans des proportions proche de la linéarité.
| Intervalle de valeurs | Temps |
| [-999;999] | 31 |
| [-9999;9999] | 31 |
| [-99999;99999] | 110 |
| [-999999;999999] | 203 |
Accueil des algorithmes de tri
Article précédent : le tri par casiers
Article suivant : conclusion
