Translate Quicksort from C into MIPS assembly?

1.6k views Asked by At

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.

0

There are 0 answers