Algoritmo Bubble Sort – O demonio das buscas

Hoje vou responder um email de uma leitora a Heloisa, que me pediu para falar mais sobre o algoritmo bubble sort, vamos lá.

Algoritmo 1:

1. Procedimento BubbleSort(Vetor)
2. var AUX {variavel de apoio}
3. Inicio
4. para i=0 até n-1 faça
5. para j=0 até n-1 faça
6. se vetor[j] > vetor[j+1] então
7. AUX = vetor[j]
8. vetor[j] = vetor[j+1]
9. vetor[j+1] = AUX
10. fim_se
11. fim_para
12. fim_para

O Bubble Sort ou “metodo bolha” como é chamado, consiste em correr um vetor comparando cada elemento com o elemento seguinte:

vetor[j] > vetor[j+1]

No caso de organizar as informações crescente, se o elemento comparadao com o vetor[i] for menor (<) ou igual (=) ao elemento, nada se faz, porém se o elemento comparado com o vetor[i] for maior (>) que o elemento, inverte-se a posição dos 2 elementos, comparando assim com todos os elementos até finalizar o vetor.

O máximo de execuções que esse algoritmo faz para que o vetor fique ordenado é (N-1), em que N é o número de elementos do vetor.

Existe também uma variação do algoritmo Bubble Sort, onde não existe uma variável Auxiliar, para fazer a troca utiliza-se um calculo matemático, no começo parece estranho como ele trabalha mas analisando bem é fácil de assimilar.

vejamos:

Digamos que:

• j = 5
• i = 3

Então

• j = j + i –> 5 + 3 = 8
• o j agora vale 8
• i = j – i –> 8 – 3 = 5
• agora o i vale 5
• j = j – i –> 8 – 5 = 3
• agora o j vale 3

Pronto trocamos os vales fazendo calculos, depois disso o valor inverte;

• j = 3
• i = 5

Vejamos o algoritmo:

Algoritmo 2:

1. Procedimento BubbleSort(Vetor)
2. Inicio
3. para i=0 até n-1 faça
4. para j=0 até n-1 faça
5. se vetor[i] > vetor[j] então
6. vetor[j] = vetor[j] + vetor[i]
7. vetor[i] = vetor[j] – vetor[i]
8. vetor[j] = vetor[j] – vetor[i]
9. fim_se
10. fim_para
11. fim_para

Utilizando as linguagem de programação PASCAL e C, veremos abaixo como fica o algoritmo nas duas linguagens:

Em Pascal:

Procedimento BubbleSort(A:Vetor)

var aux, i, j:integer;

Begin

for i=0 to n-1 do

Begin

for j=0 to n-1 do

if A[j] > A[j+1] then

aux = A[j+1];

A[j] = A[j+1];

A[j+1] = aux;

end;

end;

 

Em C

• void BubbleSort(Vetor A){
• int aux, i, j;
• for(i=0;i<n;i++){
• for(j=0;j<n;j++){
• if(a[j] > a[j+1]){
• aux = a[j];
• a[j] = a[j+1];
• a[j+1] = aux;
• }
• }
• }
• }