bug in qselect mips assembly program-CodePudding

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

CodePudding user response：

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.