在 MIPS 中快速排序

Question

我根据C++代码在MIPS汇编中编写了一个快速排序算法。在C++中，它运行良好，但在MIPS中，它不起作用。 我调试了它，问题是递归。这是算法：

QuickSort(Data[], l , r)
{
// If the first index less or equal than the last index
if l <= r:
{
// Create a Key/Pivot Element
key = Data[r]
// Create temp Variables to loop through array
i = l;
j = r;
while i <= j:
{
while Data[i] < key AND i < r:
i = i + 1
while Data[j] > key AND j > 0:
j = j - 1
if i <= j:
{
swap Data[i], Data[j]
i = i + 1 
j = j + 1
}
}
if l < j:
QuickSort(Data, l, j);
if r > i:
QuickSort(Data, i, r);
}
}

这是MIPS代码。它在某些情况下有效。例如：数组 = {6， 5， 4， 3， 2， 1}。 MIPS代码：

#-function QuickSort(arr, left,right)
#parameter
#          $a0: array
#          $a1: left
#          $a2: right
QuickSort:
subu $sp, $sp, 16
sw   $a0, 0($sp)
sw   $a1, 4($sp)
sw   $a2, 8($sp)
sw   $ra, 12($sp)
la   $s0, 0($a0)
move $s1, $a1
move $s2, $a2
bgt  $s1, $s2, done
sll  $t3, $s2, 2
add  $t3, $s0,$t3
lw   $t2, 0($t3)
move $t0, $s1
move $t1, $s2
WhileOuter:
While_i:
sll $t3, $t0, 2
add $t3, $s0, $t3
lw  $t4, 0($t3)
bge $t4, $t2, EndWhile_i
bge $t0, $s2, EndWhile_i
addi $t0, $t0, 1    
j While_i
EndWhile_i:
While_j:
sll $t3, $t1, 2
add $t3, $s0, $t3
lw $t4, 0($t3)
ble $t4, $t2, EndWhile_j
blez $t1, EndWhile_j
addi $t1, $t1, -1
j While_j
EndWhile_j:
bgt $t0, $t1, EndWhileOuter
#swap arr[i], arr[j]
sll $t4, $t0, 2
sll $t5, $t1, 2
add $s3, $s0, $t4
add $s4, $s0, $t5
lw $t4, 0($s3)
lw $t5, 0($s4)
sw $t4, 0($s4)
sw $t5, 0($s3)
addi $t0, $t0, 1
addi $t1, $t1, -1
j WhileOuter
EndWhileOuter:
bge $s1, $t1, call2
lw $a1, 4($sp)
move $a2, $t1
move $a0, $s0
jal QuickSort
call2:
ble $s2, $t0, done
move $a1, $t0
lw $a2, 8($sp)
move $a0, $s0
jal QuickSort
done:
addu $sp, $sp, 16
lw $a0, 0($sp)
lw $a1, 4($sp)
lw $a2, 8($sp)
lw $ra, 12($sp) 
jr $ra

任何人都可以在此代码中找到错误吗？感谢您的任何帮助。

Answer 1

1. 您正在使用保存的寄存器$s0、$s1、$s2，但没有遵循为调用方保留这些寄存器中的值的要求。

因此，不能保证QuickSort的调用者将保留其$s寄存器。

您没有显示代码的其余部分，例如main。

但是，我们知道 QuickSort 调用自身，并且在对自身进行第一次递归调用后，它依赖于$s0&$s2寄存器，这应该没问题，但我们知道它们没有被QuickSort正确保存。

2. 您需要更仔细地分析寄存器的使用情况和要求。 以下代码在对快速排序的第一次(递归(调用之后运行。   它理所当然地期望保留$s0和$s2，但也期望保留 $t 0 — 这是一个临时寄存器，这意味着它不会被调用保留， 所以这是一个错误。

jal QuickSort       # this call wipes out $t0
call2:
ble $s2, $t0, done  # what's supposed to be in $t0 here?
move $a1, $t0
lw $a2, 8($sp)
move $a0, $s0

3. 您不需要保存寄存器$s1，应该为该用法选择一个临时寄存器。 我会在其原始$a1寄存器中使用该变量。 

4. 你正在$a0注册保存到内存，但不使用该内存位置的值。

5. 它要么丢失，要么您更改了外部 while 循环退出条件的位置。 它不再位于循环的顶部。   它现在读起来是这样的：

while true:
{
while Data[i] < key AND i < r:
i = i + 1
while Data[j] > key AND j > 0:
j = j - 1
if i > j break;

6. Python 代码确实如此

   if i <= j:
   {
   swap Data[i], Data[j]
   i = i + 1 
   j = j + 1
   }
   

而在交换之后，汇编代码做 i++ 但 j-- .

7. 您正在使用$s3和$s4但用于简单的临时用法 - 请改用$t寄存器来实现这些目的。