Bubble Sort - Algoritmo

[Mayleone]

Você já ouvir falar sobre a técnica Bubble Sort?
Bubble Sort (ou ordenação em bolha) é um algoritmo de ordenação numérica que consiste em reorganizar os valores de uma coleção (normalmente arrays) de forma que os mesmos sejam reposicionados em ordem decrescente de acordo com o índice da coleção.
Em linguagens de programação como o C# por exemplo, temos funções de ordenação através de LINQ, assim como é feito com dados de tabelas em SQL (vide função OrderBy), mas não deixa de ser interessante estudar este algoritmo de ordenação para fins didáticos e treinar a lógica, mesmo porque, conhecer novos algoritmos e técnicas, nunca é demais.

Como funciona?
O algoritmo consiste em apenas ''trocar'' os valores de um array, de forma que os maiores valores ocupem os primeiros índices, fazendo com que os menores, obviamente, vão ficando por último na indexação.
Graficamente falando, podemos ter como exemplo a seguinte situação (um array de inteiros):

Veja que ao final do processo o array está devidamente ordenado de forma decrescente, assim o maior valor ocupa o primeiro índice, e o menor valor ocupa o último índice da coleção.

Em programação:
Para realizar essa "troca" de valores dentro do array, primeiramente precisamos criar um laço de repetição que percorra toda a coleção, e a validação a ser feita dentro deste laço deve ocorrer sempre entre o elemento atual do laço e o elemento do índice sucessor, como foi feito no exemplo gráfico, onde trocamos os elementos sucessores se estes forem maiores que o elemento anterior.
Para realizar essa validação, deve ser criado outro laço de repetição que tenha um limite menor que o tamanho do array atual, assim evitamos que seja extrapolado o último elemento, ao verificar seu sucessor, que na verdade não há.
Quando se é verificado que o sucessor no array é maior que seu antecessor, realize-se a 'troca', ou seja, o maior valor passa a ocupar o índice de seu antecessor e o menor valor vai para o índice de seu sucessor. Para tal, basta criar uma variável temporária que armazene o valor do elemento do índice atual (para que ele não se perca), e o índice atual recebe o valor de seu sucessor, e o sucessor receba o valor da variável temporária.

Exemplo em C++

Exemplo em C#

Veja que através do output do array podemos visualizar como a coleção ficou ordenada de forma decrescente:

Claro que se você quiser ordenar o array em ordem crescente, basta trocar o sinal da validação do menor (<) para maior (>):

(saída em output do array em ordem crescente)

Os exemplos neste artigo foram feitos nas linguagens em C++ e C#, mas qualquer linguagem de programação que suporte arrays pode realizar a técnica do Bubble Sort.

 

[Kaw]

Interessante.
Uma coisa que me deixou em dúvida é dentro dos for loops, no segundo loop(index j) eu entendi o que houve. Você armazenou o valor atual numa variável temporária, comparou o valor atual com o próximo valor da array e, se for menor, você troca eles de lugar e isso se repete pra cada elemento da array.

Mas, qual o propósito do primeiro loop(index i)? A ideia que tenho é que o segundo loop só move o valor 1 vez pra esquerda caso seja maior o que faria com que o maior número(caso no último index da array) não chegasse ao primeiro index e só fosse pra esquerda uma vez. Estou certa?

 

[DanTheLion]

Que coincidência! Eu estou estudando exatamente ordenação na facul que estou fazendo de Sistemas de Informação (ou TI).  :XD:

Há diversos métodos de organizar vetores, um é mais eficiente que o outro, ou pior, dependendo do caso e Bubble Sort é um deles. Você vai fazer outras maneiras de ordenação? Insertion, Selection, Shell, etc? Aguardo por mais!

~ Abraços!
Até mais!

 

[HermesPasser]

Interessante.
Uma coisa que me deixou em dúvida é dentro dos for loops, no segundo loop(index j) eu entendi o que houve. Você armazenou o valor atual numa variável temporária, comparou o valor atual com o próximo valor da array e, se for menor, você troca eles de lugar e isso se repete pra cada elemento da array.

Mas, qual o propósito do primeiro loop(index i)? A ideia que tenho é que o segundo loop só move o valor 1 vez pra esquerda caso seja maior o que faria com que o maior número(caso no último index da array) não chegasse ao primeiro index e só fosse pra esquerda uma vez. Estou certa?

Veja esse vídeo.

 

[Mayleone]

[member=1052]Kawthar[/member]:
Isso. Em resumo, o for loop i percorre o array por completo, enquanto o for loop j é responsável apenas por deslocar os valores para a esquerda, por isso que o limite dele é sempre uma unidade menor que o limite do loop i, porque quando chega-se no último elemento do array, não tem como verificar o sucessor dele, visto que ele não tem por ser o último.
Eu até mostraria isso com um exemplo gráfico, mas o vídeo que o Hermes passou já diz tudo.

[member=468]Daniel M. Neto[/member]:
Eu gosto bastante do Bubble Sort porque ele é bem simples de explicar inicialmente (tem uns que são bem mais complexos), mas ele pode pesar na execução se a coleção for muito grande, por isso realmente existem métodos melhores, talvez eu fale sobre eles sim.
Eu por exemplo testei o bubble sort num array relativamente grande, e ele demorou um tempinho considerável para executar:

// Example program
#include <iostream>

int main()
{
  int a[9999];
  int l = sizeof(a)/sizeof(*a);
  for (int i = 0; i < l; i++){
      a[i] = i;
      }
      
      for (int b = 0; b < l; b++){
          for (int c = 0; c < l-1;c++){
              if (a[c] < a[c+1]){
                  int t = a[c];
                  a[c] = a[c+1];
                  a[c+1] = t;
                  }
              }
          }
          
          for (int d = 0; d < l; d++){
              std::cout << a[d] << std:: endl;
              }
              return 0;
}

Obrigada a todos pelo feedback. o/

 

[Cristiano Sword]

[member=1052]Kawthar[/member]:
Isso. Em resumo, o for loop i percorre o array por completo, enquanto o for loop j é responsável apenas por deslocar os valores para a esquerda, por isso que o limite dele é sempre uma unidade menor que o limite do loop i, porque quando chega-se no último elemento do array, não tem como verificar o sucessor dele, visto que ele não tem por ser o último.
Eu até mostraria isso com um exemplo gráfico, mas o vídeo que o Hermes passou já diz tudo.

[member=468]Daniel M. Neto[/member]:
Eu gosto bastante do Bubble Sort porque ele é bem simples de explicar inicialmente (tem uns que são bem mais complexos), mas ele pode pesar na execução se a coleção for muito grande, por isso realmente existem métodos melhores, talvez eu fale sobre eles sim.
Eu por exemplo testei o bubble sort num array relativamente grande, e ele demorou um tempinho considerável para executar:

// Example program
#include <iostream>

int main()
{
  int a[9999];
  int l = sizeof(a)/sizeof(*a);
  for (int i = 0; i < l; i++){
      a[i] = i;
      }
      
      for (int b = 0; b < l; b++){
          for (int c = 0; c < l-1;c++){
              if (a[c] < a[c+1]){
                  int t = a[c];
                  a[c] = a[c+1];
                  a[c+1] = t;
                  }
              }
          }
          
          for (int d = 0; d < l; d++){
              std::cout << a[d] << std:: endl;
              }
              return 0;
}

Obrigada a todos pelo feedback. o/

O tutorial ficou muito bom  almas:

Sobre o Bubble Sort, estudei ele uma vez só. Embora seja de fácil entendimento, a velocidade de processamento deixa a desejar.
Na verdade de todos os algoritmos de ordenação que estudei ,só uso mesmo o Quick Sort e de vez em quando.....kkkkk