Algoritmos de Ordenação: Bubble Sort

Tipos de dados em algoritmos
Este post faz parte da série Estruturas de Dados. Leia também os outros posts da série:

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 >>
Este post faz da série Estruturas de Dados. Leia também os outros posts da série:
  • 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

      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

      • http://portal.vidadesilicio.com.br/author/urbanze/ 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

          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?!