Site icon Embarcados – Sua fonte de informações sobre Sistemas Embarcados

Algoritmos de Ordenação: Bubble Sort

PSEUDOCODIGO bubble sort switch case

Sobre o Bubble Sort

Bubble Sort é um algoritmo de ordenação que pode ser aplicado em Arrays e Listas dinâmicas. Se o objetivo é ordenar os valores em forma decrescente, então, a posição atual é comparada com a próxima posição e, se a posição atual for maior que a posição posterior, é realizada a troca dos valores nessa posição. Caso contrário, não é realizada a troca, apenas passa-se para o próximo par de comparações.

Se o objetivo é ordenar os valores em forma crescente, então, a posição atual é comparada com a próxima posição e, se a posição atual for menor que a posição posterior, é realizada a troca. Caso contrário, a troca não é feita e passa-se para o próximo par de comparação.

Um array ou lista pode estar já ordenado no momento em que se solicita a ordenação, dessa forma, esta situação tem de ser considerada na implementação do algoritmo. Assim, demonstrarei a representação gráfica e o teste de mesa das duas situações usando array.

Vetor desordenado

Suponha o seguinte vetor chamado V:

Índice

0

1

2

3

4

elemento

200

10

0

5

30

posição

i

i+1

i+2

i+3

i+4

Vamos utilizá-lo para analisar e testar o comportamento deste algoritmo. Apenas reforçando que em Linguagem C o vetor começa na posição 0. Utilizamos o comando de controle FOR para manipular vetores, então, aqui implementaremos um for que irá da posição 0 até a posição 4 e será incrementado de 1, iniciando em zero. Dessa forma conseguimos obter o valor dos elementos das posições que serão comparadas usando o comando de controle IF e, conforme a ordem desejada fazer a troca se for necessária.

Para que não ocorra repetição desnecessária, utilizaremos uma FLAG, que nos avisará quando o vetor estará ordenado e, assim, a execução será terminada. Essa FLAG sempre será setada com 1 quando houver uma troca. Dessa forma, enquanto n for menor ou igual ao tamanho do vetor e, ao mesmo tempo a FLAG for igual a 1, então, deve-se continuar ordenando, caso contrário, o vetor estará ordenado.

Ordenando de forma crescente – Ordenação Bubble Sort

1.ª Passagem no While

i = 0; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

0

5

30

Verifica

Troca = 1

V[i] >= V[i+1]

V[0] >= V[1]

200 >= 10

V

aux = V[i]

aux = V[0]

aux = 200

V[i] = V[i+1]

V[0] = V[1]

V[0] = 10

V[i+1] = aux;

V[1] = aux;

V[1] = 200

Estado do vetor após a troca:

10

200

0

5

30

i = 1; troca = 1;

Estado do vetor e posições a serem comparadas:

10

200

0

5

30

Verifica

Troca = 1

V[i] >= V[i+1]

V[1] >= V[2]

200 >= 0

V

aux = V[i]

aux = V[1]

aux = 200

V[i] = V[i+1]

V[1] = V[2]

V[1] = 0

V[i+1] = aux;

V[2] = aux;

V[2] = 200

Estado do vetor após a troca:

10

0

200

5

30

i = 2; troca = 1;

Estado do vetor e posições a serem comparadas:

10

0

200

5

30

Verifica

Troca = 1

V[i] >= V[i+1]

V[2] >= V[3]

200 >= 5

V

aux = V[i]

aux = V[2]

aux = 200

V[i] = V[i+1]

V[2] = V[3]

V[2] = 5

V[i+1] = aux;

V[3] = aux;

V[3] = 200

Estado do vetor após a troca:

10

0

5

200

30

i = 3; troca = 1;

Estado do vetor e posições a serem comparadas:

10

0

5

200

30

Verifica

Troca = 1

V[i] >= V[i+1]

V[3] >= V[4]

200 >= 30

V

aux = V[i]

aux = V[3]

aux = 200

V[i] = V[i+1]

V[3] = V[4]

V[3] = 30

V[i+1] = aux;

V[4] = aux;

V[4] = 200

Estado do vetor após a troca:

10

0

5

30

200

i = 4; troca = 1;

Estado do vetor e posições a serem comparadas:

10

0

5

30

200

Verifica

Troca = 1

V[i] >= V[i+1]

V[4] >= V[5]

200 >= ?

F

Chegamos ao fim do Vetor com o FOR, entretanto, ele ainda NÃO está ordenado de forma crescente. Portanto, a execução do While continua.

2.ª Passagem no While

i = 0; troca = 1;

Estado do vetor e posições a serem comparadas:

10

0

5

30

200

Verifica

Troca = 1

V[i] >= V[i+1]

V[0] >= V[1]

10 >= 00

V

aux = V[i]

aux = V[0]

aux = 10

V[i] = V[i+1]

V[0] = V[1]

V[0] = 10

V[i+1] = aux;

V[1] = aux;

V[1] = 10

Estado do vetor após a troca:

0

10

5

30

200

i = 1; troca = 1;

Estado do vetor e posições a serem comparadas:

0

10

5

30

200

Verifica

Troca = 1

V[i] >= V[i+1]

V[1] >= V[2]

10 >= 5

V

aux = V[i]

aux = V[1]

aux = 10

V[i] = V[i+1]

V[1] = V[2]

V[1] = 5

V[i+1] = aux;

V[2] = aux;

V[2] = 10

Estado do vetor após a troca:

0

5

10

30

200

i = 2; troca = 1;

Estado do vetor e posições a serem comparadas:

0

5

10

30

200

Verifica

Troca = 1

V[i] >= V[i+1]

V[2] >= V[3]

10 >= 30

F

i = 3; troca = 1;

Estado do vetor e posições a serem comparadas:

0

5

10

30

200

Verifica

Troca = 1

V[i] >= V[i+1]

V[3] >= V[4]

30 >= 200

F

i = 4; troca = 1;

Estado do vetor e posições a serem comparadas:

0

5

10

30

200

Verifica

Troca = 1

V[i] >= V[i+1]

V[4] >= V[5]

200 >= ?

F

Chegamos ao fim do Vetor com o FOR, entretanto, apesar do vetor já estar ordenado de forma crescente, é preciso ainda que o WHILE passe mais uma vez pois TROCA ainda vale 1. A confirmação de que o vetor está ordenado será dado quando TROCA for setado como zero. Como o vetor está ordenado, então, o FOR correrá todas as posições, mas não entrará no IF, que é o onde TROCA é setada como 1.

3.ª Passagem no While

i = 0; troca = 1;

Estado do vetor e posições a serem comparadas:

0

5

10

30

200

Verifica

Troca = 0

V[i] >= V[i+1]

V[0] >= V[1]

0 >= 5

F

i = 1; troca = 0;

Estado do vetor e posições a serem comparadas:

0

5

10

30

200

Verifica

Troca = 0

V[i] >= V[i+1]

V[1] >= V[2]

5 >= 10

F

i = 2; troca = 0;

Estado do vetor e posições a serem comparadas:

0

5

10

30

200

Verifica

Troca = 0

V[i] >= V[i+1]

V[2] >= V[3]

10 >= 30

F

i = 3; troca = 0;

Estado do vetor e posições a serem comparadas:

0

5

10

30

200

Verifica

Troca = 0

V[i] >= V[i+1]

V[3] >= V[4]

30 >= 200

F

i = 4; troca = 0;

Estado do vetor e posições a serem comparadas:

0

5

10

30

200

Verifica

Troca = 0

V[i] >= V[i+1]

V[4] >= V[5]

200 >= ? F

O algoritmo terminou de executar, troca é igual a 0, portanto o vetor está ordenado.

Código fonte para ordenação bubble sort crescente

Ordenando de forma decrescente – Ordenação Bubble Sort

1.ª Passagem no While

i = 0; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

0

5

30

Verifica

Troca = 1

V[i] <= V[i+1]

V[0] <= V[1]

200 <= 10

F

i = 1; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

0

5

30

Verifica

Troca = 1

V[i] <= V[i+1]

V[1] <= V[2]

10 <= 0

F

i = 2; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

0

5

30

Verifica

Troca = 1

V[i] <= V[i+1]

V[2] <= V[3]

0 <= 5

V

aux = V[i]

aux = V[2]

aux = 0

V[i] = V[i+1]

V[2] = V[3]

V[2] = 5

V[i+1] = aux;

V[3] = aux;

V[3] = 0

Estado do vetor após a troca:

200

10

5

0

30

i = 3; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

5

0

30

Verifica

Troca = 1

V[i] <= V[i+1]

V[3] <= V[4]

0 <= 30

V

aux = V[i]

aux = V[3]

aux = 0

V[i] = V[i+1]

V[3] = V[4]

V[3] = 30

V[i+1] = aux;

V[4] = aux;

V[4] = 0

Estado do vetor após a troca:

200

10

5

30

0

i = 4; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

5

30

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[4] <= V[5]

30 <= ?

F

Chegamos ao fim do Vetor com o FOR, entretanto, ele ainda NÃO está ordenado de forma crescente. Portanto, a execução do While continua.

2.ª Passagem no While

i = 0; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

5

30

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[0] <= V[1]

200 <= 10

F

i = 1; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

5

30

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[1] <= V[2]

10 <= 5

F

i = 2; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

5

30

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[2] <= V[3]

5 <= 30

V

aux = V[i]

aux = V[2]

aux = 5

V[i] = V[i+1]

V[2] = V[3]

V[2] = 30

V[i+1] = aux;

V[3] = aux;

V[3] = 5

Estado do vetor após a troca:

200

10

30

5

0

i = 3; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

30

5

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[3] <= V[4]

5 <= 0

F

i = 4; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

30

5

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[4] <= V[5]

0 <= ?

F

Chegamos ao fim do Vetor com o FOR, entretanto, ele ainda NÃO está ordenado de forma crescente. Portanto, a execução do While continua.

3.ª Passagem no While

i = 0; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

30

5

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[0] <= V[1]

200 <= 10

F

i = 1; troca = 1;

Estado do vetor e posições a serem comparadas:

200

10

30

5

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[1] <= V[2]

10 <= 30

V

aux = V[i]

aux = V[1]

aux = 10

V[i] = V[i+1]

V[1] = V[2]

V[1] = 30

V[i+1] = aux;

V[2] = aux;

V[2] = 10

Estado do vetor após a troca:

200

30

10

5

0

i = 2; troca = 1;

Estado do vetor e posições a serem comparadas:

200

30

10

5

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[2] <= V[3]

10 <= 5

F

i = 3; troca = 1;

Estado do vetor e posições a serem comparadas:

200

30

10

5

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[3] <= V[4]

5 <= 0

F

i = 4; troca = 1;

Estado do vetor e posições a serem comparadas:

200

30

10

5

0

Verifica

Troca = 1

V[i] <= V[i+1]

V[4] <= V[5]

0 <= ?

F

Chegamos ao fim do Vetor com o FOR, entretanto, apesar do vetor já estar ordenado de forma crescente, é preciso ainda que o WHILE passe mais uma vez pois TROCA ainda vale 1. A confirmação de que o vetor está ordenado será dada quando TROCA for setado como zero. Como o vetor está ordenado, então, o FOR correrá todas as posições, mas não entrará no IF, que é o onde TROCA é setada como 1.

4.ª Passagem no While

i = 0; troca = 1;

Estado do vetor e posições a serem comparadas:

200

30

10

5

0

Verifica

Troca = 0

V[i] <= V[i+1]

V[0] <= V[1]

200 <= 30

F

i = 1; troca = 0;

Estado do vetor e posições a serem comparadas:

200

30

10

5

0

Verifica

Troca = 0

V[i] <= V[i+1]

V[1] <= V[2]

30 <= 10

F

i = 2; troca = 0;

Estado do vetor e posições a serem comparadas:

200

30

10

5

0

Verifica

Troca = 0

V[i] <= V[i+1]

V[2] <= V[3]

10 <= 5

F

i = 3; troca = 0;

Estado do vetor e posições a serem comparadas:

200

30

10

5

0

Verifica

Troca = 0

V[i] <= V[i+1]

V[3] <= V[4]

5 <= 0

F

i = 4; troca = 0;

Estado do vetor e posições a serem comparadas:

200

30

10

5

0

Verifica

Troca = 0

V[i] <= V[i+1]

V[4] <= V[5]

0 <= ?

F

O algoritmo terminou sua execução, troca é igual a zero, o vetor está ordenado.

Código fonte para ordenação bubble sort decrescente

Vetor ordenado

Não há valores que devem ser trocados entre as posições. Portanto, o WHILE será executado uma única vez, e o IF que está dentro do FOR nunca será executado.

Finalizando

No próximo artigo falarei sobre Selection Sort. Fiquem atentos! Até.

Outros artigos da série

<< Struct – Registros em Linguagem CVetor de Struct >>