Bubble sort in assembly (MIPS)

Question

Bubble sort in assembly (MIPS)

Navigation

#1 by (2 votes)

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

c assembly mips

asked by anonymous 04.11.2016 / 22:51

1 answer

create a global function in vue bootstrapValidator.js with jsf does not work

score 2 · Accepted Answer

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.