I have this code where I have to implement binary search by first using the selection sort algorithm in mips
My selection sort works but trying to use the sorted list to execute a binary search is where my problem comes. I get an error saying is out of range. it is when i la s1, list and then la s2, list-4. what seems to be the problem?
# This program implements a binary search on a list that has been sorted by selection sort
.data
.align 2
endLbl: .asciiz "The selection sort is now complete"
list : .word 9,8,7,6,5,4,3,2,1
list2: # sorted array
count: .word 10
#------------------------------Beginning of the main-------------------------------------
.text
.globl main
main:
#------------------------------Initializes the variables---------------------------------
lw $s0, count # s0 is the remaining list length
la $s1, list # s1 is the list addr
ssort:
ble $s0, 1, search
move $a0, $s0 # a0 is now the remaining list length
move $a1, $s1 # a1 is the addr of the unsorted list
jal findSmallest
move $s2, $v0 # s2 is the index of the largest found
move $a0, $s1 # a0 is the addr of the first unsorted element
sll $a1, $s2, 2
add $a1, $a1, $a0 # a1 is the addr of the largest unsorted value
jal swap
addi $s0, $s0, -1 # decreases the list count by 1
addi $s1, $s1, 4 # update addr of unsorted list
jal search
#ssortdone:
#---------------------------------------End of main---------------------------------------
# la $a0, endLbl
# li $v0, 4
# syscall
# li $v0, 10
# syscall
#-----------------------------------------------------------------------------------------
#------------------------------Swap Function---------------------------------------------
# a0 - address of first word to exchange
# a1 - address of second word to exchange
swap:
addi $sp, $sp, -4 # allocates space on the stack
sw $ra, 0($sp) # stores the ra
#---------Swaps the values-----------------
lw $t0, 0($a0)
lw $t1, 0($a1)
sw $t0, 0($a1)
sw $t1, 0($a0)
#--------End of the function---------------
lw $ra, 0($sp) # restores return address
addi $sp, $sp, 4
jr $ra # return to the calling function
#-----------------------------Find Smallest Function-------------------------------------
# a0 - number of values in list
# a1 - address of first word in list
# v0 - integer position of the smallest value in list
findSmallest:
#-----------------------------Usual stuff at function beginning--------------------------
addi $sp, $sp, -24 # allocates space on the stack
sw $ra, 20($sp) # stores the ra
sw $s0, 16($sp)
sw $s1, 12($sp)
sw $s2, 8($sp)
sw $s3, 4($sp)
sw $s4, 0($sp)
#------------------------------function--------------------------------------------------
move $s0, $a0 # s0 is the list length
move $s3, $a1 # s3 is the addr of the list
lw $s1, 0($s3) # s1 is the smallest so far
li $s4, 0 # s4 is the index of largest so far
li $s2, 1 # s2 is the loop index; 1
loop: beq $s2, $s0, done # exit loop
#------------------------------proceeds to the next element in the list------------------
sll $t0, $s2, 2 # translate 1 into the addr
add $t1, $s3, $t0
lw $t2, 0($t1) # t2 = list
bge $t2, $s1, skip # list[s2] is not smaller than s1
#-------------------------------found a smaller value-------------------------------------
move $s1, $t2 # store off the new smallest so far
move $s4, $s2 # stores off its index
skip: addi $s2, $s2, 1 #i++
j loop
done: move $v0, $s4 # returns smallest index
#--------------------------------End of function------------------------------------------
lw $ra, 20($sp) # restores the return address
lw $s0, 16($sp)
lw $s1, 12($sp)
lw $s2, 8($sp)
lw $s3, 4($sp)
lw $s4, 0($sp)
addi $sp, $sp, 24
jr $ra # return to the calling function
#--------------------------------Binary Search Function-----------------------------------
#-----------------------------------------------------------------------------------------
#bsearch:
#Binary Search on an array that was sorted by selection sort
# search value = $a0
# first address in array = $a1
# last address in array = $a2
# v0 is the output of whether the searched value is found or not
li $s0, 7 # search value
la $s1, list # address of first array value
la $s2, list-4 # address of last array value
jal search
li $v0, 10
syscall
search:
addi $sp, $sp, 4 # allocates space on the stack
sw $ra, 4($sp) # saves the ra
add $t0, $a2, $a1 # t0 is the size of the array
bge $t0, 0, lookfor # if size > 0, perform operation
move $v0, $a1 # address of element in the array
lw $t0, ($v0) # loads the element
beq $a0, $t0, return # if the element equals the search value return
li $v0, 0 # loads 0 to v0 if the value is not in the array
jal return
lookfor:
srl $t0, $t0, 3
sll $t0, $t0, 2
add $v0, $a1, $t0
lw $t0, ($v0)
beq $s0, $t0, return
blt $s0, $t0, searchtotheleft
searchtotheright:
add $s1, $v0, 4
jal search
j return
searchtotheleft:
move $s2, $v0
jal search
return:
lw $ra, 4($sp)
add $sp, $sp, 4
jr $ra