######
 # 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

######