I have a selection sort. There is something wrong in the logic since its not sor

Question

I have a selection sort. There is something wrong in the logic since its not sorting. Can someone help me figure out what is is?

sort:
   move $t5, $zero
   move $t7, $a1
   move $t6, $a0

outerLoop:
   slt $t0, $t5, $t8
   beq $t0, $zero, ret          
   nop
   addu $t9, $zero, $t5               # t9 is min = k
   addiu $t1, $t5, 1               # t1 is j = k + 1
  
innerLoop:
   slt $t0, $t1, $t7               # if j < length t0 = 1
   beq $t0, $zero, endin
   nop
   addu $s3, $t9, $t9               # s3 = 2 * min
   addu $s3, $s3, $s3               # s3 = 4 * min
   addu $s3, $t6, $s3               # s3 is address of list[min]
   lw $t2, 0($s3)               # t2 is list[min]

   addu $s0, $t1, $t1               # s0 = 2 * j
   addu $s0, $s0, $s0               # s0 = 4 * j
   addu $s0, $t6, $s0               # s0 is address of list[j]
   lw $t3, 0($s0)               # t3 is list[j]

   slt $t0, $t3, $t2               # if list[j] < list[min] t0 = 1
   beq $t0, $zero, check          
   nop  
   addu $t9, $zero, $t1       
   j check

check:
   beq $t9, $t5, incrementJ  
   nop
   addu $s0, $t9, $t9               # s0 = 2 * min
   addu $s0, $s0, $s0               # s0 = 4 * min
   addu $s0, $s0, $t6               # s0 = address of list[min]
   lw $t4, 0($s0)  
   addu $s1, $t5, $t5               # s1 = 2 * k
   addu $s1, $s1, $s1               # s1 = 4 * k
   addu $s1, $t6, $s1               # s1 = address of list[k]
   lw $s3, 0($s1)

   sw $s3, 0($s0)               # list[min] = list[k]

   sw $t4, 0($s1)               # list[k] = temp
   addiu $t1, $t1, 1  
   addu $t9, $zero, $t5

   j innerLoop  

incrementJ:
   addiu $t1, $t1, 1    
   j innerLoop

endin:
   addiu $t5, $t5, 1
   j outerLoop
  
ret:
   return

loop:  
   slt $t0, $t5, $t7           # if k < length t0=1
   beq $t0, $0, ret      
   lw $a0, 0($t6)           # address of integer in a0
   addiu $t6, $t6, 4           # next number in array
   addiu $t5, $t5,1
   j loop   

Explanation / Answer

# register assignments

# if(v[k] < v[minIndex]) { minIndex = k }

#

                        sll $t3, $t1, 2   # t3 = 4 * k

                        add $t3, $s0, $t3 # t3 = address of v[k]

                        sll $t4, $t0, 2   # t4 = 4 * minIndex

                        add $t4, $s0, $t4 # t4 = addr of v[minIndex]?

                        lw $t5, 0($t3)   # t5 = v[k]

                        lw $t6, 0($t4)   # t6 = v[minIndex]

                        slt $t2, $t5, $t6      # v[k] < v[minIndex]

                        beq $t2, $zero, endif # if not skip if part

                        add $t0, $t1, $zero    # minIndex = k

endif:

addi $t1, $s3, 1         # k = s + 1

fork: slt $t2, $t1, $s1       # k < length ?

beq $t2, $zero, endfork # if not, exit

#

addi $t1, $t1, 1                      # k++

j    fork

endfork:

add $s3, $zero, $zero   # s = 0

fors: slt $t2, $s3, $s2       # s < length-1 ?

                        beq $t2, $zero, endfors # if not, exit loop

                        add $t0, $s3, $zero     # minIndex = s

                        sll $t3, $s3, 2             # compute array addresses

                        add $a0, $s0, $t3      # and store as parameters

                        sll $t3, $t0, 2

                        add $a1, $s0, $t3     

                        jal Swap                                # call swap function

                        addi $s3, $s3, 1                      # s++

                        j    fors

endfors:

#

# save state                              # restore state

addi $sp, $sp, -20                   

sw   $ra, 16($sp)                      lw   $ra, 16($sp)

sw   $s3, 12($sp)                     lw   $s3, 12($sp)

sw   $s2, 8($sp)                      lw   $s2, 8($sp)

sw   $s1, 4($sp)                      lw   $s1, 4($sp)

sw   $s0, 0($sp)                      lw   $s0, 0($sp)

                                                addi $sp, $sp, 20

# initialize

add $s0, $a0, $zero                # return

add $s1, $a1, $zero                jr   $ra

addi $s2, $s1, -1

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.