Problems in the selection sort loop

Question

I am having problems in the implementation of the selection sorting method in the assembly.

I still don't understand where I'm going wrong. Every help is welcome.

Maybe I'm wrong when allocating the number in the vector and then comparing it.

Follow the code in C # and then what I did in assembly.

public static void selecao(int[] vet)
{
   int i, j, min, temp;
   for (i = 0; i < vet.Length - 1; i++)
   {
      min = i;
   for (j = i + 1; j < vet.Length; j++)
   {
      if (vet[j] < vet[min])
      {
         min = j;
      }
   }
   temp = vet[i];
   vet[i] = vet[min];
   vet[min] = temp;
   }
}

Assembly

addi $t0, $zero, 0 
addi $t1, $zero, 0  
sub $s1, $s0, 1     
addi $s2, $zero, 0  
addi $t1, $zero, 0 
forS1:
slt $t2, $t0, $s1 (i < size v - 1)
beq $t2, $zero, fimForS1

addi $s2, $t0, 0

addi $t3, $t0, 1 
forS2:
slt $t4, $t3, $s0
beq $t4, $zero, fimForS2

add $s6, $s6, 1 
mul $t3, $t3, 4 
lw $s3, vetor($t3)      # vet[j]
mul $s2, $s2, 4
lw $s4, vetor($s2)      # vet[min]
slt $t5, $s3, $s4       # vet[j] < vet[min]
beq $t5, $zero, forS2
add $s7, $s7, 1 
add $s2, $t3, 0         # min = j
addi $t3, $t3, 1 
j forS2

fimForS2:
lw $t6, vetor($t1)      # vet[i]
mul $s5, $s2, 2         # posicao do vet[min]
lw $t7, vetor($s2)      # vet[min]  
addi $t8, $t6, 0        # temp = vet[i]
sw $t6, vetor($s2)          # vet[i] = vet[min];
sw $t7, vetor($t1)          # vet[min] = temp;
addi $t1, $t1, 4 
addi $t0, $t0, 1 

j forS1

Answer 1

Let's look at the flow of control for a for-statement, first in pseudo code:

for ( int i = 0; i < n; i++ ) {
    ...body...
}

1. first we do i=0, once, outside the loop.
2. next, we start the loop with a check i<n to see if we are done with the loop,
3. next the code for ...body..., and then
4. the increment i++, and finally,
5. to repeat the loop: go back to step 2.

When (using structure programming) we nest another control statement in the body of the loop, we still follow the same pattern, unchanged:

for ( int i = 0; i < n; i++ ) {
    if ( a < b ) {
         b = a;
    }
}

So, here the body is simply an if-statement.  Thus:

1. first we do i=0, once, outside the loop.
2. next, we start the loop with a check i<n to see if we are done with the loop,
3. next the ...body..., which here is the if-statement:
   • test a < b and if not the case, skip ahead to 4.
   • capture b=a
4. the increment i++, and finally,
5. to repeat the loop: go back to step 2.

Do you see how whether the nested if-statement fires or doesn't fire, the proper next thing to do is the for-statement increment i++?

You have accidentally moved your j++ increment to inside the then-part, inside the nested if-statement.  Your code is not following the proper pattern for nested control structures — the if-statement should not interfere with the for-statement that it is nested within.  So rather than doing j++ regardless of what the if-statement does, you're doing j++ only when the if-statement fires.  So, it is an incorrect translation of the pseudo code, and simply will not work properly.

Further below when you swap, you are using vet[min] but your array indexing is off.

---

See descriptions inline:

addi $t0, $zero, 0 
addi $t1, $zero, 0  
sub $s1, $s0, 1     
addi $s2, $zero, 0  
addi $t1, $zero, 0    <--- unnecessary, already done above
forS1:
slt $t2, $t0, $s1 (i < size v - 1)
beq $t2, $zero, fimForS1

addi $s2, $t0, 0

addi $t3, $t0, 1 
forS2:
slt $t4, $t3, $s0
beq $t4, $zero, fimForS2

add $s6, $s6, 1 
mul $t3, $t3, 4 
lw $s3, vetor($t3)      # vet[j]
mul $s2, $s2, 4
lw $s4, vetor($s2)      # vet[min]
slt $t5, $s3, $s4       # vet[j] < vet[min]

beq $t5, $zero, forS2   <--- this if statement skips the then part (good)
                             ***** but also skip the j++ (bad) *****

+------------------------------- this it the then part
add $s7, $s7, 1 
add $s2, $t3, 0         # min = j
addi $t3, $t3, 1        <--- this is j++
+-------------------------------
j forS2

fimForS2:
lw $t6, vetor($t1)      # vet[i]
mul $s5, $s2, 2         # posicao do vet[min]  <--- multiply by 2 (why 2??)
                                                    ***** $s5 is never used *****
lw $t7, vetor($s2)      # vet[min]         <--- here using $s2, min (bad)
                                           ***** you want min*4 instead *****
addi $t8, $t6, 0        # temp = vet[i]
sw $t6, vetor($s2)          # vet[i] = vet[min];
sw $t7, vetor($t1)          # vet[min] = temp;
addi $t1, $t1, 4 
addi $t0, $t0, 1 

j forS1