Chapitre 12 :Utilisation données locales sur la pile et exemple de tri

Nous avons utilisé la pile pour passer des paramètres dans des routines et nous allons voir l’utilisation de la pile pour stocker des données locales, cela permettant d’appeler une routine dans elle-même (appel récursif). Nous allons utiliser le générateur de nombres aléatoires du chapitre précédent légèrement modifié pour générer 100 nombres que nous stockerons dans une table puis nous trierons cette table en utilisant une routine de tri rapide.

Voyons le source du programme :

Nous commençons par générer 100 nombres aléatoires que nous plaçons dans une table. Le générateur calcule un nombre aléatoire comme précédemment mais nous prenons les chiffres à gauche en fonction de la plage à la place des chiffres à droite (ce qui devrait produire des nombres plus aléatoires).

Pour mesurer le temps du tri, nous allons effectuer un call system pour positionner le temps avant le tri et nous effectuerons la même opération après le tri et nous calculerons la différence. Sur mon raspberry, l’appel system TIME (code 0x0D ) n’est pas implémenté et j’ai donc utilisé l’appel GETTIMEOFDAY (code 0x4E).

Nous appelons ensuite la routine de tri et nous terminons par une vérification que la table est bien triée. Nous balayons la table en comparant 2 postes successifs et nous signalons une erreur si le premier est plus grand que le second.

Dans la routine de tri, nous nous contentons de sauvegarder les registres qui vont être utilisés et nous appelons la sous routine tri. Dans celle-ci après la sauvegarde habituelle des 2 registres fp et lr sur la pile, nous réservons sur la pile 16 octets par l’instruction sub sp,#16 (rappel ; les adresses de la pile décroissent). Et nous positionnons le registre fp (frame pointer) à l’adresse de la pile. Cela nous permet de manipuler les données de la zone réservée facilement.

Le tri rapide utilise un algorithme de partitionnement de la table à trier en 2 sous tables qui seront-elles mêmes partitionner en deux en utilisant un appel récursif de la même sous routine. Avant chaque appel, les pointeurs gauche, droite et courant et l’adresse de la table sont sauvegardé sur la pile dans la zone réservée. Le registre fp permet d’utiliser ces adresses sans difficulté.

Le début de la table est affiché avant et après le tri pour vérification ainsi que le temps mis pour le tri. Ce tri est efficace puisque sur mon raspberry il trie 1000000 de nombres en 1,5 secondes. Attention, ce tri peut utiliser une grande partie de la pile si les données sont mal réparties (voir la théorie sur ce type de tri).

Exercice : Adapter le tri pour trier dans l’ordre décroissant

                Écrire d’autres routines de tri et comparer le temps d’exécution.

                   Modifier le tri pour trier des chaines de caractères.