Algoritmos de Ordenação: Bubble Sort

bubble sort

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 >>
Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Receba os melhores conteúdos sobre sistemas eletrônicos embarcados, dicas, tutoriais e promoções.

Software » Algoritmos de Ordenação: Bubble Sort
Comentários:
Notificações
Notificar
guest
7 Comentários
recentes
antigos mais votados
Inline Feedbacks
View all comments
Jailson Souza Carvalho
Jailson Souza Carvalho
16/01/2020 00:36

Olá elaine, parabéns pelo excelente artigo, me ajudou muito, muito obg de coração msm, estou ingressando agora na área, faço Bacharelado em Ciência da Computação, e pretendo um dia ser uma pessoa tão incrível como vc, lhe desejo muito sucesso na sua vida profissional e pessoal.

Caio Alexandre
Caio Alexandre
10/04/2018 00:53

Ola, meu nome e Caio e sou iniciante em C, teria como me explicar o porque de usar no scanf(“%d%*c”,&numero[i]); o “%d%*c”? Eu nao entendi muito bem essa expressão

Nanos Klark
Nanos Klark
23/08/2017 00:12

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
Elaine Cecília Gatto
Reply to  Nanos Klark
23/08/2017 09:06

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é
Reply to  Elaine Cecília Gatto
24/08/2017 12:58

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
Elaine Cecília Gatto
Reply to  José
18/09/2017 20:44

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

Talvez você goste:

Séries



Outros da Série

Menu

WEBINAR
 

BlueNRG-LP – Bluetooth 5.2 de longo alcance para aplicações industriais

Data: 05/11 às 15:00h - Apoio: STMicroelectronics
 
INSCREVA-SE AGORA »



 
close-link