Sorting And Searching Arrays in MIPS
We have the following as an assignment for computer organization:
Write a MIPS Assembly code that implements a recursive binary search in a signed integer array of an arbitrary size. The code should consist of a main part that calls a recursive procedure with the base address of the array. Beware that the array does not have to be sorted; hence, in your code you need to sort the array before calling the binary search procedure. The sorting can be either done using another procedure or directly in the main part of the code.
I have no problem in searching the array OR sorting it, but I'm unsure how am I supposed to search it after sorting it since I'll be making changes to the base array. So far, this is my code:
.globl main .data # this is a data structure in MIPS Array: .word 1, 3, 6, 2, 8 # this is an array size: .word 5 welcome: .asciiz "Enter an integer" notfound:.asciiz "Not found" .text main: la $t7, Array # Copy the base address of your array into $t0 addi $t7, $t7, 20 # 4 bytes per int * 10 ints = 40 bytes outterLoop: # Used to determine when we are done iterating over the Array add $t9, $0, $0 # $t9 holds a flag to determine when the list is sorted la $a0, Array # Set $a0 to the base address of the Array innerLoop: # The inner loop will iterate over the Array checking if a swap is needed lw $t2, 0($a0) # sets $t0 to the current element in array lw $t3, 4($a0) # sets $t1 to the next element in array slt $t8, $t2, $t3 # $t8 = 1 if $t2 < $t3 beq $t8, $0, continue # if $t8 = 1, then swap them add $t9, $0, 1 # if we need to swap, we need to check the list again sw $t2, 4($a0) # store the greater numbers contents in the higher position in array (swap) sw $t3, 0($a0) # store the lesser numbers contents in the lower position in array (swap) continue: addi $a0, $a0, 4 # advance the array to start at the next location from last time bne $a0, $t7, innerLoop # If $a0 != the end of Array, jump back to innerLoop bne $t9, $0, outterLoop # $t9 = 1, another pass is needed, jump back to outterLoop addi $t0,$a0,-20 lw $t5,size addi $t6,$0,0 li $v0, 4 #print string la $a0, welcome syscall li $v0, 5 #read integer syscall addi $a1, $v0,0 #int in a1 la $t4, Array # load the array "Array"'s base address to register $t4 jal search li $v0,10 #exit the program syscall search: beq $t6,$t5,Not addi $sp,$sp,-4 sw $ra,0($sp) lw $t1, 0($t4) # load the first element in the "Array", which is Array. beq $a1,$t1, L1 #branch to L1 if t1 = a1 addi $t6,$t6,1 addi $t4,$t4,4 jal search lw $ra,0($sp) addi $sp,$sp,4 jr $ra L1: addi $v1,$t6,0 end: jr $ra Not: li $v0, 4 #print string la $a0,notfound syscall