assemblymips

MIPS quicksort an array


I am trying to convert a piece of "C" code to MIPS Assembly language for learning purpose. I wrote the MIPS code, but somewhere I am doing wrong and not getting the desired output. When I ran the program, it is showing completely different numbers. Please correct me where I am doing wrong?

C code:

void swap(int array[], int a, int b) {
     int t = array[a];
     array[a] = array[b];
     array[b] = t;
 }

int partition (int arr[], int low, int high) {
    int pivot = arr[high]; // pivot
    int i = (low - 1); // Index of smaller element
     for (int j = low; j <= high- 1; j++) {
         if (arr[j] <= pivot) {
            i++; // increment index of smaller element
            swap(arr, i, j);
            }
      }
    swap(arr, i + 1, high);
    return (i + 1);
}


void quickSort(int arr[], int low, int high) {
     if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
       quickSort(arr, pi + 1, high);
     }
 }

MIPS written:

.data # Defines variable section of an assembly routine.
array: .word 12,1,13,10,3,5,2,1 # Define a variable named array as a word (integer) array.

.text # Defines the start of the code section for the program .
.globl main
main:
la $t0, array # Moves the address of array into register $t0.
addi $a0, $t0, 0 # Set argument 1 to the array.
addi $a1, $zero, 0 # Set argument 2 to (low = 0)
addi $a2, $zero, 7 # Set argument 3 to (high = 7, last index in array)
jal quickSort # Call quick sort

li $v0, 10 # Terminate program run and
syscall # Exit

### My code start from here
quickSort: 
        addi $sp, $sp, -20 #Make room on stack for  5 registers 
        sw $ra, 16($sp) #save return address on memory
        sw $a0, 12($sp) #save a0
        sw $a1, 8($sp)  #save a1
        sw $a2, 4($sp)  #save a2
        sw $s0 , 0($sp) #save $s0

        slt $t1, $a1, $a2       #t1=1 --> low < high, otherwise 0
        beq $t1, $zero, Exit    #if low > high, branch to Exit 
        jal partition           #call  if low < high
        
        move $s0, $v0           #load partition output to s0
        addi $a2, $s0, -1       #a2 = pi - 1
        jal quickSort           #calling quickSort

        addi $a1, $s0, 1        #a1 = pi + 1
        lw $a2, 4($sp)          #loading original a2
        jal quickSort           #calling quickSort

Exit: 
        lw $s0, 0($sp)
        lw $a2, 4($sp)
        lw $a1, 8($sp)
        lw $a0, 12($sp)
        lw $ra, 16($sp)
        addi $sp, $sp, 20 
        jr $ra



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

        sll $t1, $a2, 2     #t1 = 4 * high
        add $t1, $a0, $t1   #t1 = *arr + t1
        lw $s0, 0($t1)      #s0, pivot = arr[high]
        addi $s1, $a1, -1   #i=low -1
        add $s2, $a1, $zero #j=low
        add $s3, $a2, $zero #s3=high

        forloop:

            addi $t2, $s3, -1       #t2 = high - 1
            slt $t3, $t2, $s2       #t3=1 --> j> high - 1
            bne $t3, $zero, Exit1   #if j>high -1 branch to Exit 1

            sll $t4, $s2,2          #t4 = 4j
            add $t4, $a0, $t4       #t4 = *arr + 4j
            lw $s4, 0($t4)          #s4 = arr[j]

            slt $t5, $s0, $s4       #t5=1 --> arr[j] > pivot
            beq $t5, $zero, Exit2   #if arr[j] <= pivot, branch to Exit2
            addi $s2, $s2, 1        #j++
            j forloop               #jump to forloop

            Exit2:
                addi $s1, $s1, 1    #i++
                move $a1, $s1       #a1 = i 
                move $a2, $s2       #a2 = j 
                jal swap            #calling swap
                addi $s2, $s2, 1    #j++
                j forloop           #calling forloop

        Exit1:   
                addi $s1, $s1, 1    #i=i+1
                move $a1, $s1       #a1=i+1
                move $a2, $s3       #a2=high
                jal swap            #calling swap
                move $v0, $a1       #return i+1

            lw $ra, 20($sp)
            lw $s0, 16($sp)
            lw $s1, 12($sp)
            lw $s2, 8($sp)
            lw $s3, 4($sp)
            lw $s4, 0($sp)
            jr $ra

 swap:  
        addi $sp, $sp, -8           # Make room for two elements
        sw $ra, 4($sp)              # Save return address
        sw $s5, 0($sp)              # Save s5 register

        sll $t6, $a1, 2             #t6 = a*4
        add $t6, $a0, $t6           #t6 = *a0 + 4a
        lw $s5, 0($t6)              #t = array[a]

        sll $t7, $a2, 2             #t7 = b*4
        add $t7, $a0, $t7           #$t7 = *a0 + 4b
        lw $t8, 0($t7)              #t8 = array[b]
        sw $t8, 0($t6)              #array[a] = array[b]
        sw $s5, 0($t7)              #array[b] = t 

        lw $s5, 0($sp)
        lw $ra, 4($sp)
        addi $sp, $sp, 8
        jr $ra  

Solution

  • Here is the MIPS program for the quick sort. Taken from: https://github.com/bharathkarumudi/MIPS/blob/master/quicksort.asm

    #------------------------------------#
    # Authored by: Bharath Karumudi     #
    # Purpose Quicksort in MIPS         #
    #------------------------------------#
    
    .data # Defines variable section of an assembly routine.
    array: .word 12,15,10,5,7,3,2,1 # Define a variable named array as a word (integer) array.
    # After your program has run, the integers in this array
    # should be sorted.
    .text # Defines the start of the code section for the program .
    .globl main
    
    main:
    la $t0, array # Moves the address of array into register $t0.
    addi $a0, $t0, 0 # Set argument 1 to the array.
    addi $a1, $zero, 0 # Set argument 2 to (low = 0)
    addi $a2, $zero, 7 # Set argument 3 to (high = 7, last index in array)
    jal quicksort # Call quick sort
    li $v0, 10 # Terminate program run and
    syscall # Exit
    
    
    swap:               #swap method
    
    addi $sp, $sp, -12  # Make stack room for three
    
    sw $a0, 0($sp)      # Store a0
    sw $a1, 4($sp)      # Store a1
    sw $a2, 8($sp)      # store a2
    
    sll $t1, $a1, 2     #t1 = 4a
    add $t1, $a0, $t1   #t1 = arr + 4a
    lw $s3, 0($t1)      #s3  t = array[a]
    
    sll $t2, $a2, 2     #t2 = 4b
    add $t2, $a0, $t2   #t2 = arr + 4b
    lw $s4, 0($t2)      #s4 = arr[b]
    
    sw $s4, 0($t1)      #arr[a] = arr[b]
    sw $s3, 0($t2)      #arr[b] = t 
    
    
    addi $sp, $sp, 12   #Restoring the stack size
    jr $ra          #jump back to the caller
    
    
    
    partition:          #partition method
    
    addi $sp, $sp, -16  #Make room for 5
    
    sw $a0, 0($sp)      #store a0
    sw $a1, 4($sp)      #store a1
    sw $a2, 8($sp)      #store a2
    sw $ra, 12($sp)     #store return address
    
    move $s1, $a1       #s1 = low
    move $s2, $a2       #s2 = high
    
    sll $t1, $s2, 2     # t1 = 4*high
    add $t1, $a0, $t1   # t1 = arr + 4*high
    lw $t2, 0($t1)      # t2 = arr[high] //pivot
    
    addi $t3, $s1, -1   #t3, i=low -1
    move $t4, $s1       #t4, j=low
    addi $t5, $s2, -1   #t5 = high - 1
    
    forloop: 
        slt $t6, $t5, $t4   #t6=1 if j>high-1, t7=0 if j<=high-1
        bne $t6, $zero, endfor  #if t6=1 then branch to endfor
    
        sll $t1, $t4, 2     #t1 = j*4
        add $t1, $t1, $a0   #t1 = arr + 4j
        lw $t7, 0($t1)      #t7 = arr[j]
    
        slt $t8, $t2, $t7   #t8 = 1 if pivot < arr[j], 0 if arr[j]<=pivot
        bne $t8, $zero, endfif  #if t8=1 then branch to endfif
        addi $t3, $t3, 1    #i=i+1
    
        move $a1, $t3       #a1 = i
        move $a2, $t4       #a2 = j
        jal swap        #swap(arr, i, j)
    
        addi $t4, $t4, 1    #j++
        j forloop
    
        endfif:
        addi $t4, $t4, 1    #j++
        j forloop       #junp back to forloop
    
    endfor:
        addi $a1, $t3, 1        #a1 = i+1
        move $a2, $s2           #a2 = high
        add $v0, $zero, $a1     #v0 = i+1 return (i + 1);
        jal swap            #swap(arr, i + 1, high);
    
        lw $ra, 12($sp)         #return address
        addi $sp, $sp, 16       #restore the stack
        jr $ra              #junp back to the caller
    
    quicksort:              #quicksort method
    
    addi $sp, $sp, -16      # Make room for 4
    
    sw $a0, 0($sp)          # a0
    sw $a1, 4($sp)          # low
    sw $a2, 8($sp)          # high
    sw $ra, 12($sp)         # return address
    
    move $t0, $a2           #saving high in t0
    
    slt $t1, $a1, $t0       # t1=1 if low < high, else 0
    beq $t1, $zero, endif       # if low >= high, endif
    
    jal partition           # call partition 
    move $s0, $v0           # pivot, s0= v0
    
    lw $a1, 4($sp)          #a1 = low
    addi $a2, $s0, -1       #a2 = pi -1
    jal quicksort           #call quicksort
    
    addi $a1, $s0, 1        #a1 = pi + 1
    lw $a2, 8($sp)          #a2 = high
    jal quicksort           #call quicksort
    
     endif:
    
    lw $a0, 0($sp)          #restore a0
    lw $a1, 4($sp)          #restore a1
    lw $a2, 8($sp)          #restore a2
    lw $ra, 12($sp)         #restore return address
    addi $sp, $sp, 16       #restore the stack
    jr $ra              #return to caller