# Bubble sort in assembly (MIPS)

2

My teacher asked us to implement Bubble Sort in the MARS environment but I can not. There are some errors in the code. Can anyone find the error?

Output should be `{1, 2, 3, 4, 5, 6, 7, 8}` but is `{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;
}
}
}
}``````

Assembly Code:

``````# 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``````

asked by anonymous 04.11.2016 / 22:51

2

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

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

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

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

And beware also of comparison. If the vector needs to be ordered incrementally, then the correct thing is to do something like `vec[j-1] > vec[j]` and change in this case.

05.11.2016 / 03:16