2

Meu professor pediu para que implementássemos o Bubble Sort no ambiente MARS mas não estou conseguindo. Tem algum erro no código. Alguém consegue encontrar o erro?

A saída deveria ser {1, 2, 3, 4, 5, 6, 7, 8} mas está sendo {1, 8, 7, 6, 5, 4, 3, 2}

Código em 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;
            }
        }
    }
}

Código em 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

1 Resposta 1

2

Sua ideia de BubbleSort está errada. Este algoritmo de ordenação possui algumas variantes, mas basicamente funciona da seguinte forma:

  • Comece com i = 0. j começa em n-1 e vai decrescendo. A cada iteração, vai se andando pelo vetor de duas em duas casas (j-1 e j). Se encontrar duas fora de ordem, troca de lugar. Continua até chegar na posição 0. Ao final da iteração, a posição 0 guardará o menor elemento do vetor;

  • Passe para i = 1 e faça a mesma coisa, até a posição 1. Ao final da iteração, ela guardará o 2º menor elemento, e assim por diante.

Observe que não é necessário mexer nas posições já ordenadas. Assim, é garantido que o nº de casas que você irá tocar a cada iteração é n-i.

E cuidado também com a comparação. Se o vetor precisa estar ordenado crescentemente, então o correto é fazer algo do tipo vec[j-1] > vec[j] e trocar neste caso.

1
  • 1
    Verdade, está errado mesmo. Já corrigi. Obrigado! Commented 5/11/2016 às 15:33

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .