>我正在尝试在MIPS中实现选择排序。我的输出偶尔是正确的，但有几种情况是不正确的。通常直到某个点它是正确的，在那一点之后，数字打印出来未排序。它似乎也难以处理多个负数。
我相信问题可能出在交换功能上，但我不确定。任何帮助将不胜感激。
注意：我不允许使用伪指令，例如 bge 或 move。
这是我正在模拟的 C 实现中的代码。
.data
msg1: .asciiz "The elements sorted in ascending order are:"
.align 2
space: .asciiz " "
.align 2
comma: .asciiz ","
.align 2
arr: .space 80
.text
MAIN:
# Ask for user input and put value in $s1
addi $v0, $zero, 5 # call service 5 for integer input
syscall # read integer
add $s1, $zero, $v0 # Save $t0 = len
# Load address for arr
la $s0, arr # Pointer to arr goes in $t1
add $a0, $zero, $s0 # Save arr pointer to $a0
add $a1, $zero, $s1 # Save len to $a1
# Ask for user input to fill arr
jal FILL
# Sort the list using selection sort
jal SORT
# Print list
jal PRINT
# Call to end program
addi $v0, $zero, 10 # system call for exit
syscall
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
FILL: # deal with stack and save
addi $t0, $zero, 0 # $t0 = counter = 0
FILL_LOOP:
slt $t1, $t0, $a1 # if(counter < len) continue
beq $t1, $zero, FILL_RETURN # if(counter >= len) branch out of loop
addi $v0, $zero 5 # call service 5 for integer input
syscall # read integer
addi $t2, $zero, 0 # clear $t2 and set to 0
add $t2, $zero, $v0 # $t2 holds input integer
add $t3, $zero, $t0 # $t3 = i
sll $t3, $t3, 2 # $t3 = counter * 4
add $t3, $t3, $a0 # addr of arr[counter]
sw $t2, 0($t3) # store values in arr
addi $t0, $t0, 1 # counter = counter + 1
j FILL_LOOP
FILL_RETURN:
jr $ra # Return
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
SORT:
addi $sp, $sp, -28 # make space for variables
sw $a0, 0($sp) # store $a0 (arr)
sw $a1, 4($sp) # store $a1 (len)
sw $ra, 8($sp) # store return address
sw $s0, 12($sp) # store $s0 ( i )
sw $s1, 16($sp) # store $s1 ( j )
sw $s2, 20($sp) # store $s2 (tmp)
sw $s3, 24($sp) # store $s3 (minIndex)
addi $s0, $zero, 0 # i = 0
add $t0, $zero, $a1 # $t0 = len
addi $t0, $t0, -1 # $t0 = len - 1
FOR_1:
slt $t1, $s0, $t0 # i < $t0 = len - 1 continue
beq $t1, $zero, SORT_RETURN # if !(i < len - 1) branch out of loop
add $s3, $zero, $s0 # minIndex = i
addi $t1, $s0, 1 # $t1 = i + 1
add $s1, $zero, $t1 # j = $t1 = i + 1
FOR_2:
slt $t1, $s1, $a1 # j < len continue
beq $t1, $zero, IF_1 # if !(j < len) branch out of loop
IF_2: # "FIND MIN"
# get value at arr[ j ] store in $t3
add $t2, $zero, $s1 # calculate index $t2 = j
sll $t2, $t2, 2 # offset = $t2 * 4
add $t2, $t2, $a0 # add offset to base address
lw $t3, 0($t2) # load value at arr[ j ] into $t3
# get value at arr[minIndex] store in$t5
add $t4, $zero, $s3 # calculate index $t4 = minIndex
sll $t4, $t4, 2 # offset = $t4 * 4
add $t4, $t4, $a0 # add offset to base address
lw $t5, 0($t4) # load value at arr[minIndex] into $t5
slt $t1, $t3, $t5 # if(arr[ j ] < arr[minIndex]) continue
beq $t1, $zero, LOOP_2 # if !(arr[ j ] < arr[minIndex]) branch out of if stmt
add $s3, $zero, $s1 # minIndex = j
LOOP_2:
addi $s1, $s1, 1 # j++
j FOR_2
IF_1: # "SWAP"
beq $s3, $s0, LOOP_1 # if(minIndex == i) branch out of if stmt (jump to LOOP_1)
# tmp = arr[minIndex]
add $t2, $zero, $s3 # calculate index $t2 = minIndex
sll $t2, $t2, 2 # offset = $t2 * 4
add $t2, $t2, $a0 # add offset to base address
lw $s2, 0($t2) # $s2 = tmp = arr[minIndex]
# arr[minIndex] = arr[ i ]
add $t3, $zero, $s0 # calculate index $t3 = i
sll $t3, $t3, 2 # offset = $t2 * 4
add $t3, $t3, $a0 # add offset to base address
lw $t0, 0($t3) # $t0 = arr [ i ]
sw $t0, 0($t2) # store value at arr[ i ] in arr[minIndex]
# arr[ i ] = tmp
sw $s2, 0($t3) # store tmp value in arr[ i ]
LOOP_1:
addi $s0, $s0, 1 # i++
j FOR_1
SORT_RETURN:
lw $a0, 0($sp) # Get $a0
lw $a1, 4($sp) # Get $a1
lw $ra, 8($sp) # Get return address
lw $s0, 12($sp) # Get $s0
lw $s1, 16($sp) # Get $s1
lw $s2, 20($sp) # Get $s2
lw $s3, 24($sp) # Get $s3
addi $sp, $sp 28 # Adjust stack pointer
jr $ra # Return
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
PRINT:
addi $t0, $zero, 0 # $t0 = counter = 0
add $t1, $zero, $a0 # $t1 = arr address pointer
# Print msg1
la $s3, msg1
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
# Print a space
la $s3, space
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
PRINT_LOOP:
slt $t2, $t0, $a1 # if(counter < len) continue
beq $t2, $zero, PRINT_RETURN # if(counter >= len) branch out of loop
add $t3, $zero, $t0 # $t3 = counter
sll $t3, $t3, 2 # $t3 = counter * 4
add $t3, $t3, $t1 # $t3 = addr of arr[counter]
lw $t4, 0($t3) # Load value to print
add $a0, $zero, $t4 # put address of $t4 in $a0 to print
addi $v0, $zero, 1 # call service 1 to print integer
syscall # print integer
# Check if last array element
# Skip printing comma and space
addi $t3, $a1, -1 # $t3 = len - 1
beq $t3, $t0, PRINT_RETURN # if(at least element)
# Print a comma
la $s3, comma
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
# Print a space
la $s3, space
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
addi $t0, $t0, 1 # counter - counter + 1
j PRINT_LOOP
PRINT_RETURN:
jr $ra # Return
C imp
for ( c = 0 ; c < ( n - 1 ) ; c++ )
{
position = c;
for ( d = c + 1 ; d < n ; d++ )
{
if ( array[position] > array[d] )
position = d;
}
if ( position != c )
{
swap = array[c];
array[c] = array[position];
array[position] = swap;
}
}
发出确实发生在交换函数中。我重用 $t 0 将值保存在 arr[i] 处，然后将该值存储在此处显示的 arr[minIndex] 处，
lw $t0, 0($t3) # $t0 = arr [ i ]
sw $t0, 0($t2) # store value at arr[ i ] in arr[minIndex]
在我的代码中，$t 0 是我的外部 for 循环中使用的变量FOR_1如下所示，
slt $t1, $s0, $t0 # i < $t0 = len - 1 continue
beq $t1, $zero, SORT_RETURN # if !(i < len - 1) branch out of loop
实际上，我在不应该修改$t 0时修改了它，这导致我过早地退出了排序方法，从而导致不正确的输出。
下面是更正后的代码以及其他注释。还对 FILL 和 PRINT 函数进行了修改，以处理将函数使用的变量保存和还原到堆栈。
.data
msg: .asciiz "The elements sorted in ascending order are:"
.align 2 # align string
space: .asciiz " "
.align 2 # align string
comma: .asciiz ","
.align 2 # align string
arr: .space 80 # max array length = 20 * 4 bytes
.text
MAIN:
# Ask for user input and put value in $s1
addi $v0, $zero, 5 # call service 5 for integer input
syscall # read integer
add $s1, $zero, $v0 # Save $s1 = len
# Load address for arr
la $s0, arr # pointer to arr goes in $s0
add $a0, $zero, $s0 # save arr pointer to $a0
add $a1, $zero, $s1 # save len to $a1
# Ask for user input to fill arr
jal FILL
# Sort the list using selection sort
jal SORT
# Print list
jal PRINT
# Call to end program
addi $v0, $zero, 10 # system call for exit
syscall # exit program
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
FILL:
addi $sp, $sp, -8 # make space on stack
sw $s0, 0($sp) # save $s0 (position) on stack
sw $s1, 4($sp) # save $s1 (input) on stack
addi $t0, $zero, 0 # $t0 = 0
add $s0, $zero, $t0 # initialize $s0 = $t0 = 0
FILL_LOOP:
slt $t1, $s0, $a1 # if(position < len) continue
beq $t1, $zero, FILL_RETURN # if(position >= len) branch out of loop
addi $v0, $zero 5 # call service 5 for integer input
syscall # read integer
addi $s1, $zero, 0 # clear $s1 and set to 0
add $s1, $zero, $v0 # $s1 holds input integer
add $t3, $zero, $s0 # $t3 = position
sll $t3, $t3, 2 # $t3 = position * 4
add $t3, $t3, $a0 # addr of arr[position]
sw $s1, 0($t3) # store value $s1 in arr[position]
addi $s0, $s0, 1 # position++
j FILL_LOOP
FILL_RETURN:
lw $s0, 0($sp) # restore $s0 from stack
lw $s1, 4($sp) # restore $s1 from stack
addi $sp, $sp 8 # adjust stack pointer
jr $ra # Return
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
SORT:
addi $sp, $sp, -28 # make space on stack
sw $a0, 0($sp) # save $a0 (arr) on stack
sw $a1, 4($sp) # save $a1 (len) on stack
sw $ra, 8($sp) # save return address on stack
sw $s0, 12($sp) # save $s0 ( i ) on stack
sw $s1, 16($sp) # save $s1 ( j ) on stack
sw $s2, 20($sp) # save $s2 (tmp) on stack
sw $s3, 24($sp) # save $s3 (minIndex) on stack
addi $s0, $zero, 0 # i = 0
add $t0, $zero, $a1 # $t0 = len
addi $t0, $t0, -1 # $t0 = len - 1
FOR_1:
slt $t1, $s0, $t0 # if(i < len - 1) continue
beq $t1, $zero, SORT_RETURN # if(i >= len - 1) branch out of loop
add $s3, $zero, $s0 # minIndex = i
addi $t1, $s0, 1 # $t1 = i + 1
add $s1, $zero, $t1 # j = $t1 = i + 1
FOR_2:
slt $t1, $s1, $a1 # if(j < len) continue
beq $t1, $zero, IF_1 # if(j >= len) branch out of loop
IF_2: # "FIND MIN"
# get value at arr[ j ] store in $t3
add $t2, $zero, $s1 # calculate index $t2 = j
sll $t2, $t2, 2 # offset = $t2 * 4
add $t2, $t2, $a0 # add offset to base address
lw $t3, 0($t2) # load value at arr[ j ] into $t3
# get value at arr[minIndex] store in$t5
add $t4, $zero, $s3 # calculate index $t4 = minIndex
sll $t4, $t4, 2 # offset = $t4 * 4
add $t4, $t4, $a0 # add offset to base address
lw $t5, 0($t4) # load value at arr[minIndex] into $t5
slt $t1, $t3, $t5 # if(arr[ j ] < arr[minIndex]) continue
beq $t1, $zero, LOOP_2 # if(arr[ j ] >= arr[minIndex]) branch out of if stmt
add $s3, $zero, $s1 # minIndex = j
LOOP_2:
addi $s1, $s1, 1 # j++
j FOR_2
IF_1: # "SWAP"
beq $s3, $s0, LOOP_1 # if(minIndex == i) branch out of if stmt (jump to LOOP_1)
# tmp = arr[minIndex]
add $t2, $zero, $s3 # calculate index $t2 = minIndex
sll $t2, $t2, 2 # offset = $t2 * 4
add $t2, $t2, $a0 # add offset to base address
lw $s2, 0($t2) # $s2 = tmp = arr[minIndex]
# arr[minIndex] = arr[ i ]
add $t3, $zero, $s0 # calculate index $t3 = i
sll $t3, $t3, 2 # offset = $t2 * 4
add $t3, $t3, $a0 # add offset to base address
lw $t6, 0($t3) # $t6 = arr [ i ]
sw $t6, 0($t2) # store value at arr[ i ] in arr[minIndex]
# arr[ i ] = tmp
sw $s2, 0($t3) # store tmp value in arr[ i ]
LOOP_1:
addi $s0, $s0, 1 # i++
j FOR_1
SORT_RETURN:
lw $a0, 0($sp) # restore $a0 from stack
lw $a1, 4($sp) # restore $a1 from stack
lw $ra, 8($sp) # restore return address from stack
lw $s0, 12($sp) # restore $s0 from stack
lw $s1, 16($sp) # restore $s1 from stack
lw $s2, 20($sp) # restore $s2 from stack
lw $s3, 24($sp) # restore $s3 from stack
addi $sp, $sp 28 # adjust stack pointer
jr $ra # Return
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
PRINT:
addi $sp, $sp, -4 # make space on stack
sw $s0, 0($sp) # save $s0 (position) on stack
addi $t0, $zero, 0 # $t0 = 0
add $s0, $zero, $t0 # initialize $s0 = $t0 = 0
# Print msg
la $s3, msg # load address of msg into $s3
add $a0, $zero, $s3 # put address of msg in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
# Print a space
la $s3, space # load address of space into $s3
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
PRINT_LOOP:
slt $t2, $s0, $a1 # if(position < len) continue
beq $t2, $zero, PRINT_RETURN # if(position >= len) branch out of loop
la $a0, arr # reload arr pointer into $a0
add $t3, $zero, $s0 # $t3 = position
sll $t3, $t3, 2 # $t3 = position * 4
add $t3, $t3, $a0 # $t3 = address of arr[position]
lw $t4, 0($t3) # Load value to print
add $a0, $zero, $t4 # put address of $t4 in $a0 to print
addi $v0, $zero, 1 # call service 1 to print integer
syscall # print integer
# Check if last array element
# Skip printing comma and space
addi $t3, $a1, -1 # $t3 = len - 1
beq $t3, $s0, PRINT_RETURN # if(at last element)
# Print a comma
la $s3, comma # load address of comma into $s3
add $a0, $zero, $s3 # put address of comma in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
# Print a space
la $s3, space # load address of space into $s3
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
addi $s0, $s0, 1 # position++
j PRINT_LOOP
PRINT_RETURN:
lw $s0, 0($sp) # restore $s0 from stack
addi $sp, $sp 4 # adjust stack pointer
jr $ra # Return