Bubble Sort in Assembly (MIPS)

Question

My teacher asked us to implement Bubble Sort in the MARS environment but I’m not getting it. There is some error in the code. Can anyone find the error?

The way out should be {1, 2, 3, 4, 5, 6, 7, 8} but it’s being {1, 8, 7, 6, 5, 4, 3, 2}

Code in C:

void BubbleSort(int *vec, int vecsz)
{
    for (int i = 0; i < vecsz; i++)
    {
        for (int j = 0; j < vecsz; j++)
        {
            if (vec[i] < vec[j])
            {
                int aux = vec[j];
                vec[j] = vec[i];
                vec[i] = aux;
            }
        }
    }
}

Code in Assembly:

# Bubble Sort
# $a0 conterá o endereço do vetor
# $a1 conterá o tamanho do vetor
# $s0 = i
# $s1 = j


        .data
vec:    .word 8, 7, 6, 5, 4, 3, 2, 1
vecsz:  .word 8

        .text
main:   la $a0, vec
        lw $a1, vecsz
        j bubble

bubble: li $s0, 0               # (s0) i = 0

eloop:  bge $s0, $a1, end       # break if i >= vecsz
        li  $s1, 0

iloop:  bge $s1, $a1 endiloop   # break if j >= vecsz (vecsz >= j)

        sll $t1, $s0, 2         # t1 = i * 4 (para indexar o vetor)
        sll $t2, $s1, 2         # t2 = j * 4 (para indexar o vetor)

        add $t1, $a0, $t1       # endereço de vec[i] => t1 = vec + i * 4
        add $t2, $a0, $t2       # endereço de vec[j] => t2 = vec + j * 4

        lw $t3, ($t1)           # t3 = vec[i]
        lw $t4, ($t2)           # t4 = vec[j]

        blt $t3, $t4, swap

        addi $s1, $s1, 1 # j++
        j iloop

swap:
        sw $t3, ($t2)           # vec[j] = vec[i]
        sw $t4, ($t1)           # vec[i] = vec[j]

endiloop:
        addi $s0, $s0, 1        # i++
        j eloop
end:    
        li $v0, 10
        syscall

Answer 1

Your idea of Bubblesort is wrong. This sorting algorithm has some variants, but basically works as follows:

• Start with i = 0. j begins in n-1 and decreasing. At each iteration, it moves through the vector of two in two (j-1 and j). If you find two out of order, change places. Continue until you reach the position 0. At the end of the iteration, the position 0 will hold the smallest element of the vector;

• Pass to i = 1 and do the same thing, until the position 1. At the end of the iteration, it will hold the 2nd smallest element, and so on.

Note that it is not necessary to mess with the already ordered positions. Thus, it is guaranteed that the number of houses you will touch at each iteration is n-i.

And also be careful with comparison. If the vector needs to be increasingly ordered, then the correct thing is to do something like vec[j-1] > vec[j] and exchange in this case.