algorithm - Mips 汇编程序中的快速排序

Question

我正在尝试学习一些汇编程序，现在我正在尝试让快速排序算法发挥作用。但是出了点问题。

假设我使用这个数组

1,2,3,4,5,6,7,8,9,4

结果是这样的

1,2,3,4,4,6,6,8,8,9

有人知道问题出在哪里吗？
这是我的快速排序代码。

QuickSort:
    bgt     a1, a2, QuickSortEnd    
    nop

    subu    sp, sp, 16
    sw      ra, 16(sp)
    sw      a0, 12(sp)
    sw      a1, 8(sp)
    sw      a2, 4(sp)   #save a0, a1, a2, ra
    jal Partition       #partition(v, a, b)
    nop 

    subu    sp, sp, 4
    sw      v0, 4(sp)   
    lw      a0, 16(sp)      #a0 = v
    lw      a1, 12(sp)      #a1 = a
    addi    a2, v0, -1      #a2 = k - 1 
    jal QuickSort
    nop

    lw      a0, 16(sp)  #a0 = v
    lw      t0, 4(sp)
    addi    a1, t0, 1   #a1 = k + 1
    lw      a2, 8(sp)   #a2 = b
    jal QuickSort
    nop

    addu sp, sp, 20
    lw ra, 0(sp)    
    nop

QuickSortEnd: jr ra 

这是分区部分

Partition:
    add t1, a1, a1
    add t1, t1, t1
    add t1, t1, a0      #t2 = pivot
    lw  t2, 0(t1)       #v[a]
    nop
    addi t3, a1, 1      #t3 = lower = a + 1
    addi t4, a2, 0      #t4 = upper = b

Do:
blt t4, t3, PartitionEnd

    W1:
    add     t8, t3, t3
    add     t8, t8, t8
    add     t8, t8, a0      
    lw      t5, 0(t8)       #t5 = v[lower]
    nop
    ble     t5, t2, W12
    nop
    b       W2
    W12:
    ble     t3, t4, W1_Op
    nop
    b       W2
    W1_Op:
    addi    t3, t3, 1
    b       W1

    W2:
    add     t8, t4, t4
    add     t8, t8, t8
    add     t8, t8, a0      
    lw      t5, 0(t8)       #t5 = v[upper]
    nop
    bgt     t5, t2, W22
    nop
    b       f
    W22:
    ble     t3, t4, W2_Op
    nop
    b       f
    W2_Op:
    addi    t4, t4, -1
    b       W2

f:
    bgt     t3, t4, Do
    nop
    add     t8, t3, t3
    add     t8, t8, t8
    add     t8, t8, a0      
    lw      t6, 0(t8)       #temp = v[lower]
    nop

    add     t9, t4, t4
    add     t9, t9, t9
    add     t9, t9, a0      
    lw      t7, 0(t1)       #v[upper]
    nop

    sw      t7, 0(t8)       #v[lower] = v[upper]
    sw      t6, 0(t9)       #v[upper] = temp

    addi    t3, t3, 1
    addi    t4, t4, -1

j Do

PartitionEnd:
    add     t8, t4, t4
    add     t8, t8, t8
    add     t8, t8, a0      
    lw      t2, 0(t8)       #temp = v[upper]
    nop

    add     t9, a1, a1
    add     t9, t9, t9
    add     t9, t9, a0      
    lw      t3, 0(t9)       #v[a]
    nop

    sw      t3, 0(t8)       # v[upper] = v[a]
    sw      t2, 0(t9)       # v[a] = temp

    addi    v0, t4, 0       #return upper(k)
    jr      ra
    nop

我用参数调用快速排序函数

a0 = address of array to be sortet
a1 = 0
a2 = (number of elements) - 1

Answer 1

在您的“f”子例程中，当您打算调用 $t9 寄存器时，您调用了 $t1 寄存器。简单修复，但下次评论您的代码并学习更有效地利用您的寄存器可能会有所帮助。更少的寄存器更容易跟踪。