使用堆栈指针在MIPS中对数组进行排序

Question

我想在MIPS汇编中使用交换函数对预定义的数组进行排序，但我仍然坚持编写交换代码。

我也必须使用堆栈指针。

这是它的c ++代码：

for (i=0; i<n; i+=1) {
    for (j=i-1; j>=0 && v[j] > v[j+1]; j-=1) {
    swap (v,j);
    }
}

这是代码。我尝试过使用jal和jr并搞砸了。

.data
.align 2
ARRAY: .word 12, 4, 23, 2, 5, 26, 13, 42, 41, 18
msg1: .asciiz " "

.text
.globl main
main:
la $a0, ARRAY
addi $a1, $zero, 10     #array length

sort:
addi $sp, $sp, -20
sw $ra, 16($sp)
sw $s3, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)

add $s0, $zero, $zero
add $s2, $a0, $zero
add $s3, $a1, $zero

loop1:
slt $t0, $s0, $s3
beq $t0, $zero, exit1
addi $s1, $s0, -1

loop2:
slt $t0, $s1, $zero
bne $t0, $zero, exit2
sll $t1, $s1, 2
add $t2, $s2, $t1
lw $t3, 0($t2)
lw $t4, 4($t2)
slt $t0, $t4, $t3
beq $t0, $zero, exit2

add $a0, $s2, $zero
add $a1, $s3, $zero

swap:
?

addi $s1, $s1, -1
j loop2

exit2:
addi $s0, $s0, 1
j loop1

exit1:
lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20

exit:
li $v0, 10
syscall

我需要做什么才能将较小的一个与更大的一个交换，以便我可以对数组进行排序？

Answer 1

您不应该像在循环入口处的测试那样实现循环。您需要一个效率较低的额外分支，并且难以理解代码。

如果你有一个循环

for(initial; test; increment) { body }

只需将其翻译为：

   initial
loop:
   body
   increment
   test -> loop

您只需要一个唯一的分支，这大大提高了代码的可读性。

此外，首先编写带有指针的C代码以简化翻译

for (i=0; i<n; i+=1) {
    for (j=i-1, parray=array[i-1]; j>=0 ; j-=1, parray--) {
       if(*parray > *(parray+1)) 
         swap (parray); // the pointer is sufficient
    }
}

关于交换操作，为什么要一个子程序？您已将数组[j]和数组[j + 1]的值存储在寄存器中，您只需将它们写回到正确的位置即可。

这是一个可能的转换（跳过开始和结束保持不变）

...
sort:
addi $sp, $sp, -20
sw $ra, 16($sp)
sw $s3, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)

   add $s0, $zero, $zero # i=0
   add $s2, $a0, $zero   # @array
   add $s3, $a1, $zero   # N

loop1:
    addi $s1, $s0, -1    # j=i-1
    sll $t1, $s1, 2
    add $t2, $s2, $t1    # @array[j]

loop2:
    lw $t3, 0($t2)         # $t3 array[j]
    lw $t4, 4($t2)         # $t4 array[j+1]
    sgt $t0, $t3, $t4      # array[j] > array[j+1]?
    bne $t0, $zero, noswap # no? -> noswap

swap:
    # just exchange the loaded values of array[j] and array[j+1]
    sw $t3, 4($t2)
    sw $t4, 0($t2)

noswap:

    addi $s1, $s1, -1   # j--
    addi $t2, $t2, -4   # array--
    sge $t0, $s1, $zero # j>=0?
    bne $t0, $zero, loop2

    addi $s0, $s0, 1  #i++
    slt $t0, $s0, $s3 #i<N?
    bne $t0, $zero, loop1

exit1:
...

加载次数可能会减少，因为在每次迭代中，您已经加载了数组[i]。