mansace 0 Newbie Poster

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.