J’avais besoin d’un tri stable et qui reste assez rapide car le tri par insertion est stable mais pas très performant. J’ai donc recherché d’autres tris stables et j’ai donc testé plusieurs exemples de tri fusion.
Le premier algorithme est issu du site rosetta code et je l’ai intégré dans un programme qui génère une table de nombres aléatoires, qui effectue les mesures de performance comme vues au chapitre 87, ce qui permet la comparaison de plusieurs tris.
Dans le programme testMergeTri64.s, nous trouvons la génération de la table, sa copie, l’appel aux mesures et l’appel à chaque tri. Le premier tri est un tri shell qui servira de comparaison. Le deuxième est le tri de rosetta code.
Voici les résultats pour trier 1000 valeurs numériques :
Tri shell
instructions: 178676 Cycles: 195663 temps en µs: 365573 temps1: 358906
tri merge
instructions: 2074928 Cycles: 2150297 temps en µs: 3740209 temps1: 3738177
Ce dernier tri n’est donc pas du tout performant. Je recherche donc d’autres algorithme dont celui de Robert Sedgewick en langage C que j’adapte à l’assembleur :
Nouveau tri merge :
instructions: 257280 Cycles: 313895 temps en µs: 612135 temps1: 609896
ce qui est mieux !! mais attention ce tri utilise une table annexe ce qui peut poser un problème de place.
J’améliore ce tri en effectuant les opérations de manière itérative :
instructions: 214244 Cycles: 253779 temps en µs: 456458 temps1: 451771
Puis il me vient l’idée d’effectuer le premier passage qui compare 2 valeurs successives sans utiliser le stockage dans la table intermédiaire puisque dans ce cas il suffit de stocker les 2 valeurs à intervertir dans seulement 2 registres :
instructions: 179335 Cycles: 230524 temps en µs: 405052 temps1: 401042
Voyons pour 100000 valeurs
tri shell :
instructions: 37658720 Cycles: 42019684 temps en µs: 73245522 temps1: 73231616
tri merge 1
instructions: 20051919690 Cycles: 20112824889 temps en µs: 30899260563 temps1: 30899177076
C’est énorme
tri merge
instructions: 40135342 Cycles: 46668064 temps en µs: 83594376 temps1: 83597240
tri merge itératif :
instructions: 35420192 Cycles: 44364228 temps en µs: 77672919 temps1: 77622968
autre tri merge itératif :
instructions: 31226666 Cycles: 41760383 temps en µs: 72490157 temps1: 72477969
La différence est nette pour ce dernier tri.
Avec ces derniers tests itératifs, il est possible d’utiliser la pile pour stocker la table intermédiaire.
Maintenant il faut vérifier la stabilité de ces tris (sauf le shell qui n’est pas stable). Pour cela dans le programme testMergeTri64Multi.s je crée une structure avec 2 zones dont une est alphanumérique pour tester le tri sur zone alpha.
J’adapte les tris pour effectuer les comparaisons suivant le choix alpha ou numérique.
L’affichage du début de la table triée pour chaque tri montre la même séquence pour les 3 tris fusion et un écart pour le tri shell. Ce qui semble être bon.
J’ai refait un test sur un programme légèrement modifié : au lieu de générer des valeurs numériques aléatoires, je stocke directement le compteur. Ensuite en triant sur les chaînes, il suffit de vérifier que l’ordre des valeurs numériques est croissant pour les chaînes identiques.
Évidemment les temps sont supérieurs à ceux du premier programme ce qui est normal puisque la comparaison s’effectue sur des chaînes de plusieurs caractères.
