CODEWITHSUNDEEP
assemblymips
Vaelin Al Soran
Vaelin Al Soran

Reputation: 71

Sorting Algorithm Implementation in MIPS

I wrote a MIPS equivalent to the following C Quicksort program 

while(L<=R){
    if(A[M] < n)
    L=M+1;
    else if(A[M]==n){
        printf("%d found in %d\n",n,M );
        break;
    }
    else
        R=M-1;
    M=(L+R)/2;
}

Of which I wrote the MIPS equivalent , I have check the program for any other error but its not showing one 

 # $t0 is index of Leftmost entry of array considered
 # $t3 is index of Rightmost entry of array considered
 # $t1 is index of MIddle entry of array considered
 # $t2 is the adderess of middle entry (i.e. $t1*4 )
 # myArray is an array I took as input , with $s1 elements
        addi $t0, $zero, 0  # $t0 stores left
    add $t1, $s1, $t0   
    srl $t1, $t1, 1 #stores mid 
    sll $t2, $t1, 2
    add $t3, $s1, $zero

    BinSearch:
    bge $t0, $t3 , exit 
    lw $t6, myArray($t2)

    blt $t6, $s2, leftindex      # if(A[mid]<k) goto left
    beq $t6, $s2, found
    bgt $t6, $t2, rightindex


    leftindex:
    addi    $t0, $t1, 1     # left index leftindex= mid + 1
    add $t1, $t3, $t0       # mid = left + right 
    srl $t1, $t1, 1 
    sll $t2, $t1, 2
    j BinSearch             #goback to Binary Search 

    found:
    li $v0, 1
    add $a0, $t1, $zero
    syscall
    j exit                  #exit programme

    rightindex:             
    addi $t3, $t1, -1   #rightindex = mid -1
    add $t1, $t3, $t0   #mid = left+right
    srl $t1, $t1, 1 
    sll $t2, $t1, 2    #mid/2 
    j BinSearch         #goback to binarysearch

I already checked if I made a mistake in taking array as input or if I am making any other silly mistake .

So my question is , is there some mistake where I have made mistake in implementing algorithm in MIPS ? OR something else wrong I made ? thank you in advance.

Upvotes: 1

Views: 1123

Answers (1)

Craig Estey
Craig Estey

Reputation: 33601

I think there are a few bugs.

First, when setting R (i.e. $t3), it was being set to the array count but it should be set to the count - 1.

Second, based on the C code, the bge for loop exit should be bgt

Third, to track the C code, the bgt to rightIndex should be b (i.e. an unconditional branch)

I've created two versions of your code. An annotated one and one with the bugs fixed and some simplifications [please pardon the gratuitous style cleanup].

Here's the annotated one:

# $s1 is count of array
# $t0 is index of Leftmost entry of array considered
# $t3 is index of Rightmost entry of array considered
# $t1 is index of Middle entry of array considered
# $t2 is the address of middle entry (i.e. $t1*4 )
# myArray is an array I took as input , with $s1 elements
    addi    $t0,$zero,0             # $t0 stores left
    add     $t1,$s1,$t0
    srl     $t1,$t1,1               # stores mid
    sll     $t2,$t1,2

# NOTE/BUG: if C were the array count, this sets R = C, but we need R = C - 1
# so change this as follows:
    ###add      $t3,$s1,$zero
    addi        $t3,$s1,-1

# NOTE/BUG: based on the C code, the bge should be bgt
BinSearch:
    ###bge      $t0,$t3,exit
    bgt     $t0,$t3,exit
    lw      $t6,myArray($t2)

    blt     $t6,$s2,leftindex       # if(A[mid]<k) goto left
    beq     $t6,$s2,found

# NOTE/BUG: to track the C code, this should be uncondition
    ###bgt      $t6,$t2,rightindex
    b       rightindex

leftindex:
    addi    $t0,$t1,1               # left index leftindex= mid + 1
    add     $t1,$t3,$t0             # mid = left + right
    srl     $t1,$t1,1
    sll     $t2,$t1,2
    j       BinSearch               # goback to Binary Search

found:
    li      $v0,1
    add     $a0,$t1,$zero
    syscall
    j       exit                    # exit programme

rightindex:
    addi    $t3,$t1,-1              # rightindex = mid -1
    add     $t1,$t3,$t0             # mid = left+right
    srl     $t1,$t1,1
    sll     $t2,$t1,2               # mid/2
    j       BinSearch               # goback to binarysearch

Here's the cleaned up and simplified one:

# $s1 is count of array
# $t0 is index of Leftmost entry of array considered
# $t3 is index of Rightmost entry of array considered
# $t1 is index of Middle entry of array considered
# $t2 is the address of middle entry (i.e. $t1*4 )
# myArray is an array I took as input , with $s1 elements
    li      $t0,0                   # $t0 stores left
    addi    $t3,$s1,-1              # $t3 stores right

BinSearch:
    bgt     $t0,$t3,exit            # L<=R (i.e. L>R) ? if no, we're done

    add     $t1,$t3,$t0             # mid = left + right
    srl     $t1,$t1,1               # mid /= 2

    sll     $t2,$t1,2
    lw      $t6,myArray($t2)

    blt     $t6,$s2,leftindex       # if(A[mid]<k) goto left
    beq     $t6,$s2,found
    b       rightindex

leftindex:
    addi    $t0,$t1,1               # leftindex = mid + 1
    j       BinSearch               # goback to Binary Search

rightindex:
    addi    $t3,$t1,-1              # rightindex = mid - 1
    j       BinSearch               # goback to binarysearch

found:
    li      $v0,1
    add     $a0,$t1,$zero
    syscall
    j       exit                    # exit programme

Upvotes: 1

Related Questions