Munis de la lecture et de l’écriture de nombres (à la console), ainsi que de chaînes de caractères (de longueur fixe), éventuellement dans des fichiers, nous pouvons créer des tableaux de nombres afin de nous amuser à les trier. Commençons par le tri à bulles, obligeamment procuré par Messieurs Patterson et Hennessy (au passage je salue Alfred Aho et Jeffrey Ullman, qui viennent de recevoir le prix Turing qui avait en 2017 été décerné à Hennessy et Patterson). Voici le programme principal, qui demande la saisie du tableau de nombres au clavier, appelle le programme de tri, puis affiche le résultat trié.
- # Lire un tableau d’entiers, le trier, l’afficher
- .globl _start # adresse de démarrage du programme pour l’éditeur de liens
- _start:
- # Demander taille du tableau (< 17)
- la a1, message1 # charger l’adresse
- jal ra, print_str # affichage de la chaîne
- # Lecture de la taille (< 17)
- jal ra, read_int # a1 <-- l’entier lu
- la x30, nb_items
- sw a1, 0(x30) # sauve a1 dans nb_items
- # Remplissage du tableau
- la a0, tableau
- jal ra, remplir
- # Affichage du tableau
- la a0, tableau
- lw a1, nb_items
- jal ra, afficher
- # Tri du tableau
- la a0, tableau
- lw a1, nb_items
- jal ra, bubble_sort
- # Affichage du tableau trié
- la a0, tableau
- lw a1, nb_items
- jal ra, afficher
- exit:
- # Fin du programme
- addi a0, x0, 0 # code de retour 0
- addi a7, x0, 93 # le code de commande 93
- ecall # Appel Linux pour finir
- #####
- # remplissage du tableau
- # a0 : pointeur sur première case du tableau
- # a1 : nombre de cases à remplir
- remplir:
- addi sp, sp, -4
- sw ra, 0(sp) # sauvegarde ra sur la pile
- mv x29, a0 # x29 -> tableau
- mv x28, a1 # i <-- nb cases à remplir
- loop2:
- # Lecture d’un entier
- ble x28, x0, exit2 # rempli
- la a1, message2 # charger l’adresse
- jal ra, print_str
- jal ra, read_int # a1 <-- l’entier lu
- sw a1, 0(x29) # tableau[i] <-- l’entier lu
- addi x28, x28, -1 # décrément de i
- addi x29, x29, 4 # case suivante
- j loop2
- # Retour
- exit2:
- # Retour chariot pour y voir clair
- la a1, saut
- jal ra, print_str # on y voit plus clair
- lw ra, 0(sp) # restauration de ra depuis la pile
- addi sp, sp,4 # pour l’adresse de retour
- ret
- #####
- # affichage du tableau
- # a0 : pointeur sur première case du tableau
- # a1 : nombre de cases à afficher
- afficher:
- addi sp, sp, -4
- sw ra, 0(sp) # sauvegarde ra sur la pile
- addi x29, a0, 0 # x29 -> tableau
- addi x30, a1, 0 # x30 nb items à afficher
- addi x28, x0, 0 # i <-- 0
- loop3:
- # Affichage d’un entier
- lw a0, 0(x29) # a0 <-- l’entier à afficher
- jal ra, print_int
- # Retour chariot
- la a1, saut
- jal ra, print_str
- addi x28, x28, 1 # incrément indice boucle
- bge x28, x30, exit3 # affiché
- addi x29, x29, 4 # case suivante
- j loop3
- # Retour
- exit3:
- # Retour chariot pour y voir clair
- la a1, saut
- jal ra, print_str # on y voit plus clair
- lw ra, 0(sp) # restauration de ra depuis la pile
- addi sp, sp,4 # pour l’adresse de retour
- ret
- #####
- .include "read-print.s"
- .include "strings.s"
- .include "bubble-sort.s"
- ######
- .data
- .align 2
- tableau: .word 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
- nb_items: .word 0
- saut: .string "\n"
- message1: .string "Entrez le nombre de cases du tableau : \n"
- message2: .string "Entrez un nombre entier : \n"
- message3: .string "Oui, on est passé là !\n"
Et voici la procédure de tri à bulles (les autres procédures ont été publiées dans l’article précédent, cf. le lien ci-dessus).
- ######
- # Tri à bulles, d’après Patterson et Hennessy
- bubble_sort:
- addi sp, sp, -20 # accroît la pile pour 5 registres
- sw x1, 16(sp) # sauve l’adresse de retour sur la pile
- sw x22, 12(sp) # x22 sur la pile
- sw x21, 8(sp) # x21 sur la pile
- sw x20, 4(sp) # x20 sur la pile
- sw x19, 0(sp) # x19 sur la pile
- addi x21, x10, 0 # x21 <-- x10 v, vecteur à trier
- addi x22, x11, 0 # x22 <-- x11 n, nb de cases à trier
- addi x19, x0, 0 # i <-- 0
- for1tst:
- bge x19, x22, exit11 # si >= n exit11
- addi x20, x19, -1 # j <-- i - 1
- for2tst:
- blt x20, x0, exit12 # si j < 0 exit12
- slli x5, x20, 2 # x5 <-- j * 4
- add x5, x21, x5 # x5 <-- v + j * 4
- lw x6, 0(x5) # x6 <-- v[j]
- lw x7, 4(x5) # x7 <-- v[j + 1]
- ble x6, x7, exit12 # si x6 < x7 exit12
- addi x10, x21, 0 # paramètre v -> swap
- addi x11, x20, 0 # paramètre j -> swap
- jal x1, swap # appel swap
- addi x20, x20, -1 # j for2tst
- jal x0, for2tst # -> for2tst
- exit12:
- addi x19, x19, 1 # i <-- i+1
- jal x0, for1tst # -> for1tst
- exit11:
- add x10, x0, x21# x10 -> tableau
- lw x19, 0(sp) # restaure x19
- lw x20, 4(sp) # restaure x20
- lw x21, 8(sp) # restaure x21
- lw x22, 12(sp) # restaure x22
- lw x1, 16(sp) # restaure adresse de retour
- addi sp, sp, 20 # restaure pointeur de pile
- jalr x0, 0(x1) # retour à l’appelant
- ######
- swap:
- slli x6, x11, 2 # x6 <-- k * 4
- add x6, x10, x6 # x6 <-- v + (k * 4)
- lw x5, 0(x6) # x5 <-- v[k]
- lw x7, 4(x6) # x7 <-- v[k + 1]
- sw x7, 0(x6) # v[k] <-- x7
- sw x5, 4(x6) # x[k + 1] <-- x5
- jalr x0, 0(x1) # retour à l’appelant
- ######