I am trying to create a MIPS program of the Quicksort algorithm that sorts strings. I have a bit of C code that I am trying to translate, but I'm having an extremely hard time with it.
Here's the C code:
// 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);
}
and here is the MIPS code that I have so far:
.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:
I don't really know if any of my MIPS code is correct or if it works, and I'm especially stuck on the partitioning part (last two lines of recursive code in the C) and I have no idea how to go about it.
Would anyone be willing to help me figure out how to do this? Thank you so much.