Ordenação em Bolha (bubble sort)

Renan.mmerlo · 23 de setembro de 2009

Boa Tarde pessoal,

Gostaria de saber como funciona um bubble sort e se daria para alguem implementar em C um exemplo desse tipo de ordenação.

Obrigado

Laverson · 23 de setembro de 2009

Seria mais ou menos nesse estilo ai:


    for (x=0; x<max; x++)
    {
        for (y=0; y<max; y++)
        {
            if (ponto[y+1] > ponto[y])
            {
                 mei = ponto[y];
                 ponto[y] = ponto[y+1];
                 ponto[y+1] = mei;
                 strcpy(temp,nome[y]);
                 strcpy(nome[y],nome[y+1]);
                 strcpy(nome[y+1],temp);
             }
        }
    }

dontpanic · 23 de setembro de 2009

Aqui tem implementação dele em várias linguagens:

http://pt.wikipedia.org/wiki/Bubble_sort

Ele funciona mais ou menos assim:

Vetor -> 3, 1, 5, 2, 4

Começando do Indice 1, ele testa se o segundo numero é menor que o primeiro

Nesse, caso: 1 < 3

[3][1] 5, 2, 4

Se for menor, ele troca um por outro

1, 3, 5, 2, 4

Repete a mesma coisa com os items seguintes

1, [3][5] 2, 4 --> 5 não é menor que 3

1, 3, [5][2] 4 --> 2 é menor que 5, troca

1, 3, 2 [5][4] --> 4 é menor que 5, troca

1, 3, 2, 4, 5

Depois dessa primeira passagem, o algoritmo já pode deduzir uma coisa de certeza: O ultimo item já é o maior número do vetor. Então não precisa mais mexer nele.

Na segunda passagem, o algoritmo só testa até o quarto elemento:

[1][3] 2, 4, (5) --> 3 maior que 1, não troca

1, [3][2] 4, (5) --> 2 menor que 3, troca

1, 2, [3][4] (5) --> 4 maior que 3, não troca

1, 2, 3, 4, 5

Existe um bubble sort "inteligente" que faria mais uma passagem e veria que não houve mais trocas e portanto o vetor já tá ordenado. Pra isso precisa criar alguma variavel de controle pra testar essa condição.

Mas normalmente o algoritmo continua seguindo a mesma logica:

[1][2] 3, (4, 5) --> 2 maior que 1, não troca

1, [2][3] (4, 5) --> 3 maior que 2, não troca

1, 2, 3, 4, 5

[1][2] (3, 4, 5) --> 2 maior que 1, não troca

1, 2, 3, 4, 5

Fim.