Nicolas DAILLY
www.dailly.info > Dossiers techniques > Algorithmes de Tri > Comparaisons de performances

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).

n = nombre d'éléments à trier
m = cardinal des éléments à trier
AlgorithmePire des casEn moyenneMeilleur des cas
Tri BulleO(n2)  
Tri Bulle OptimiséO(n2)  
Tri par SelectionO(1/2 * n2)O(1/2 * n2)O(1/2 * n2)
Tri par InsertionO(1/2 * n2)O(1/4 * n2) 
Tri ShellO(n2)O(n2) 
Tri FusionO(n * lg(n))O(n * lg(n))O(n * lg(n))
Tri RapideO(n * lg(n))O(n * lg(n))O(n2)
Tri CasierO(n + m)O(n + m)O(n + m)
Tri par CréationO(n2)O(n2)O(n2)
Tri par Arbre Binaire de RechercheO(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
Nombre de valeurs
51210242048409681921638432768655361310722621445242881048576209715241943048388608
Tri bulle016311255002000862534265180062??????????????????
Tri bulle optimisé01615943441312559424546168406??????????????????
Tri par selection0016311405472281931249578228407???????????????
Tri par insertion000311254842000862543953258532???????????????
Tri Shell0000016153263141297703160938138406
Tri Fusion000000163162140266563117223914922
Tri Rapide000000015316214137592226108235
Tri Casier000000016015163162109234
Tri par création160471405782250895330016111172??????????????????
Tri par Arbre Binaire de Recherche000015167814040795428757890?????????

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 valeursTemps
[-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


© 2000-2017 ~ Nicolas Dailly
Page générée le 24/10/2017 à 04:03:00 ~ Site réalisé avec SPIP