Below is the quickselect algorithm in mips. There is an error there but I can't find it. qselect function does not work correctly, but the other functions seem to be fine. I have spent so many hours trying to debug it but it compiles without errors in mars. It just doesn't work as supposed
How I tested it:
n: .word 4
v: .word 3, 10, 8, 2
k: .word 2
correct: 8 but the program finds 2
n: .word 21
v: .word 10, 3, 7, 21, 20, 15, 14, 24, 9, 5, 1, 22, 16, 13, 12, 18, 4, 6, 19, 17, 2
k: .word 12
correct:15 but the program finds 19
swap: # swap entry point
la $t0, v #t0 = address of v
sll $t1, $a0, 2 #t1 = 4*a0 = 4*i
add $t1, $t0 , $t1 #t1 = address of v[i]
lw $t2, 0($t1) # t2=v[i]
sll $t3, $a1, 2 #t3 = 4*a1 = 4*j
add $t3, $t0 , $t3 #t3 = address of v[j]
lw $t4 , 0($t3) #t4 = v[j]
sw $t4 , 0($t1) #v[i] = v[j]
sw $t2, 0($t3) # v[j] = v[i]
jr $ra # return to caller
partition:
addi $sp, $sp, -16 #adjust stack for 4 items
sw $ra, 0($sp) #store ra in stack
sw $s0, 4($sp) #store s0
sw $a0, 8($sp) #store a0
sw $a1, 12($sp) #store a1
la $s0, v #load address of v0 in s0
sll $t0, $a1, 2 #t0 stores 4 * l
add $t0, $t0, $s0 #t0 stores ad. of v[l]
lw $t1, 0($t0) #t1 contains v[l] (t1 pivot)
add $t2, $a0, $zero #t2 is f (t2 i)
add $t3, $a0, $zero #t3 is f (t3 j)
for1: slt $t4, $t3, $a1 #sets 1 to t4 if j < l
beq $t4, $zero, exit
sll $t5, $t3, 2 #t5 is 4 * j
add $t5, $t5, $s0 #t5 stores ad. of v[j]
lw $t6, 0($t5) #t6 has the value of v[j]
slt $t4, $t6, $t1 #sets 1 to t4 if v[j] < pivot
beq $t4, $zero, bfor
add $a0, $t2, $zero #a0 is i
add $a1, $t3, $zero #a1 is j
addi $sp, $sp, -12 #adjust stack for 3 items
sw $t1, 0($sp)
sw $t2, 4($sp)
sw $t3, 8($sp) #store pivot, i, j in stack
jal swap #call swap
lw $t1, 0($sp)
lw $t2, 4($sp)
lw $t3, 8($sp) #restores pivot, i, j before the call
addi $sp, $sp, 12 #return items to stack
lw $a1, 12($sp) #restore initial a1
addi $t2, $t2, 1 #i++
j bfor
bfor: addi $t3, $t3, 1 #j++
j for1 #continue loop
exit: add $a0, $t2, $zero #a0 is i
addi $sp, $sp, -4 #adjust stack for 1 item
sw $t2, 0($sp) #store i
jal swap #calls swap
lw $v0, 0($sp) #returns i
addi $sp, $sp, 4 #returns item to stack
lw $ra, 0($sp) #restore initial ra in stack
lw $s0, 4($sp) #restore initial s0
lw $a0, 8($sp) #restore initial a0
lw $a1, 12($sp) #restore initial a1
addi $sp, $sp, 16 #return items to stack
jr $ra
qselect:
# a0 = f
# a1 = l
# a2 = k
addi $sp, $sp, -4 #adjust stack for 1 item
sw $ra, 0($sp)
if1:
#if !(f < 1+l) goto else0
addi $t0, $a1, 1 #t0 = l+1
slt $t0, $a0, $t0 #if f<1+l t0 = 1
beq $t0, $zero, else0 # if t0 = 0 goto else0
#j partition
partition: #int p = partition(f,l);
jal partition #v0 becomes p
lw $ra, 0($sp) #restore ra
#j if3
if3:
#if (p==k) goto else_if2
beq $v0, $a2,else_if2
if2: #if p < k return qselect(f,p-1,k);
slt $t1, $a2, $v0 #if p > k, t1 = 1
beq $t1, $zero, qselectp1lk # if t1 = 0 goto qselectp1lk
#j qselectfp1k
qselectfp1k:
#return qselect(f,p-1,k);
addi $a1, $a1, -1 # a1 = p-1
jal partition
lw $ra, 0($sp) # restore ra
j end_qselect
else0: #return v[f];
la $t0, v # t0 = address of v
sll $t1, $a0, 2 # t1 = 4*f
add $t1, $t1, $t0 #t1 = address of v[f]
lw $v0, 0($t1) #v0 = v[f]
j end_qselect
else_if2:
#return v[k];
la $t0, v # t0 = address of v
sll $t1, $a2, 2 # t1 = 4*k
add $t1, $t1, $t0 #t1 = address of v[k]
lw $v0, 0($t1) #v0 = v[k]
j end_qselect
qselectp1lk: # return qselect(p+1,l,k);
addi $a0, $v0, 1 # a0 = p+1
jal qselect
lw $ra, 0($sp) #restore ra
j end_qselect
end_qselect:
lw $ra, 0($sp)
addi $sp, $sp, 4 #restore stack
jr $ra #return to caller
qselectfp1k:
#return qselect(f,p-1,k);
addi $a1, $a1, -1 # a1 = p-1 *** p is in $v0 so this is not p-1, but l-1
jal partition *** this is supposed to be a call to qselect
lw $ra, 0($sp) # restore ra
j end_qselect
Did you notice that the comment says return qselect(f,p-1,k), but the code calls partition(f,l-1) instead?
The usual Quickselect will have one call to the partition function and two recursive calls — but you have two calls to the partition function and one recursive call.