Algoritmos de Ordenação: Bubble Sort

Tipos de dados em algoritmos

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

 

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 crescente

 

 

 

Ordenando de forma decrescente

 

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 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 >>
Bacharel em Engenharia de Computação. Mestre em Ciência da Computação. Cantora, Professora Universitária, Geek, Nerd, Otaku e Gamer. Apaixonada por Michael Jackson, Macross, Mulher Maravilha, Superman, Cervejas Artesanais/Especiais e Voleyball. Informações adicionais você encontra em: http://lattes.cnpq.br/8559022477811603.

Deixe um comentário

4 Comentários em "Algoritmos de Ordenação: Bubble Sort"

Notificar
avatar
 
Ordenar por:   recentes | antigos | mais votados
Nanos Klark
Visitante
Nanos Klark

Você poderia postar mais sobre estes algoritimos de ordenação, manipulação e etc? (tanto para vetores, matrizes ou gerais)
Por exemplo, metodos para achar valores em vetores gigantes (GB de informaçoes) de forma mais rapida...

Elaine Cecília Gatto
Visitante
Elaine Cecília Gatto

Oi!!! Obrigada por comentar e valeu pela dica. Gostaria de entender qual é a sua necessidade em relação a métodos para encontrar valores em muita informação. Normalmente, bancos de dados fornecem essas capacidades. Poderia explicitar melhor? Agradeço

José
Visitante
José

Apenas curiosidade mesmo para quando precisar, ja ter o conhecimento. É sempre legal ter alguns algoritimos otimizados para certas atividades... Você poderia trazer alguns destes algoritimos, eu não conheço nome de algoritimos entao não posso indicar um 🙁

Elaine Cecília Gatto
Visitante
Elaine Cecília Gatto

Entendi!!!!! Vou tentar ok! É que normalmente, em se tratando de grandes conjuntos de dados, usa-se técnicas de mineração de dados, que já é algo bem mais complexo/complicado que estes algoritmos de ordenação. Blz?!

wpDiscuz