我正在尝试创建一个对字符串进行排序的 Quicksort 算法的 MIPS 程序。我有一些我正在尝试翻译的 C 代码，但我很难处理它。
这是C代码：
// QuickSortIdx (using array indexing)
// array is a pointer to the first element of an array of string pointers
// left is the lowest index to begin sorting at (initially 0)
// right is the highest index to end sorting at (initially array length - 1)
void quickSortIdx(char** array, int left, int right) {
int i = left;
int j = right;
int pivotIndex = (i + j) >> 1; // Arbitrarily pick middle element
char* pivot = array[pivotIndex]; // as the pivot element
// this loop is the partitioning step which divides the array into
// two areas, elements greater than the pivot and elements less than the pivot
do {
// move i down to first element greater than or equal to pivot
while (strcmp(array[i],pivot) < 0) i++;
// move j up to first element less than or equal to pivot
while (strcmp(array[j],pivot) > 0) j--;
if (i <= j) { // if i and j have not passed each other
char* temp = array[i];
array[i] = array[j]; // swap their respective elements
array[j] = temp;
i++; j--; // advance both i and j
}
} while (i <= j); // Continue until i passes j
// now sort the two partitions separately
if (left < j) quickSortIdx(array,left,j);
if (i < right) quickSortIdx(array,i,right);
}
这是我到目前为止的 MIPS 代码：
.data
str0:
.asciiz "Four"
str1:
.asciiz "score"
str2:
.asciiz "and"
sarray:
.word str0
.word str1
.word str2
size:
.word 3
newline
.asciiz "/n"
main:
la $s0, sarray # s0 = array
jal quickSort
quickSort:
li $t0, size # t0 = size
li $s2, $zero # s2 = left
subi $s3, $t0, 1 # t1 = right = size - 1
addi $s4, $s2, $s3 # s3 = pivotIndex = left + right
sra $s4, $s4, 1 # s3 = pivotIndex = (left + right) / 2
ble $s2, $s3, innerSort # if left >= right, go to innerSort
innerSort:
lw $s5, $s2($s0) # s5 = str1 = array[i]
lw $s6, $s3($s0) # s6 = str2 = array[j]
lw $s7, $s4($s0) # s7 = pivot = array[pivotIndex]
jal strcmp_loop_1 # s1 = strcmp(array[i], pivot)
bltz $s1, incrementI # if s1 < 0
jal strcmp_loop_2 # s1 = strcmp(array[j], pivot)
bgtz $s1, decrementJ # if s1 > 0
ble $s2, $s3, swap # if i <= j
swap:
lw $t0, $s2($s0) # t0 = temp = array[i]
lw $t1, $s3($s0) # t1 = temp = array[j]
lw $s2($s0), $t1 # array[i] = array[j]
lw $s3($s0), $t0 # array[j] = array[i]
addi $s2, $s2, 1 # i++
subi $s3, $s3, 1 # j--
ble $s2, $s3, innerSort
jal partition
incrementI:
addi $s2, $s2, 1 # i++
decrementJ:
subi $s3, $s3, 1 # j--
strcmp_loop_1:
lb $t0, 0($s5) # t0 = 1st char of array[i] = str1
lb $t1, 0($s7) # t1 = 1st char of pivot = str2
lw $t2, newline # t2 = newline
bne $t0, $t1, strcmp_notEqual_1 # end if chars are different
beq $t0, $t2, strcmp_checkEnd_1 # if end of str1 is a newline, check end of str2
addi $s5, $s5, 1 # increment str1 address
addi $s7, $s7, 1 # increment str2 address
jal strcmp_loop_1 # go to strcmp loop
strcmp_checkEnd_1:
lw $t2, newline # t2 = newline
beq $s7, $t2, strcmp_equal # check if end of str2 is newline
jal strcmp_notEqual_1 # if not, they aren't equal
strcmp_equal:
li $s1, $zero # if equal, print out a 0 and end
jal innerSort
strcmp_notEqual_1:
sub $s1, $s5, $s7 # if not equal, subtract str2 from str1 and print
beq $a0, -59, strcmp_equal
jal innerSort
strcmp_loop_2:
lb $t0, 0($s6) # t0 = load 1st character of str1 into $s0
lb $t1, 0($s7) # t1 = load 1st character of str2 into $s1
lw $t2, newline # t2 = newline
bne $t0, $t1, strcmp_notEqual_2 # end if chars are different
beq $t0, $t2, strcmp_checkEnd_2 # if end of str1 is a newline, check end of str2
addi $s6, $s6, 1 # increment str1 address
addi $s7, $s7, 1 # increment str2 address
jal strcmp_loop_2 # go to strcmp loop
strcmp_notEqual_2:
sub $s1, $s6, $s7 # if not equal, subtract str2 from str1 and print
beq $a0, -59, strcmp_equal
jal innerSort
strcmp_checkEnd_2:
lw $t2, newline # t2 = newline
beq $s7, $t2, strcmp_equal # check if end of str2 is newline
jal strcmp_notEqual_2 # if not, they aren't equal
partition:
我真的不知道我的任何 MIPS 代码是否正确或是否有效，而且我特别卡在分区部分（C 中的最后两行递归代码），我不知道如何去做.
有人愿意帮我弄清楚如何做到这一点吗？太感谢了。