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.

[Lord Wallace]

Algoritmos de ordenação são dos mais simples que se tem na programação, mas estão entre os que considero mais interessantes. É muito bacana ver como há inúmeras maneiras diferentes e criativas de se ordenar uma lista/vetor, e como elas impactam radicalmente a velocidade com que a tarefa é feita.

Bubblesort é bem lento comparado aos Mergesorts da vida, mas mesmo assim é infinitamente mais rápido que o meu favorito, o maravilhoso Bogosort 

[Corvo]

Opa, bom ver tutoriais mais genéricos por aqui, faz pouco tempo que comecei a estudar esse tipo de algorítimo. Hoje em dia tem-se bibliotecas e métodos pra fazer tudo automaticamente, o pessoal acaba ficando com preguiça de ver como funcionam. 

Obrigado por compartilhar, aulas são sempre bem vindas. o/

[MayLeone]

Eu gosto bastante de estudar patterns e algoritmos, e é como o Corvo disse, hoje em dia temos bibliotecas prontas que já fazem essas tarefas pra nós, e às vezes a gente acaba por não pensar como tal função funciona.
Obviamente que não estou dizendo pra reinventarmos a roda, se essas bibliotecas estão aí nós temos é mais que usá-las mesmo, mas para estudar e treinar um pouco a lógica, eu acho válido falar sobre esses tipos de algoritmos. 

[Sotelie]

Sorting Algorithms é um troço bem satisfatório de se mexer, e cada um possui o seu preferiro.

Pessoalmente não possuo um preferido visto que gosto de tentar vários diferentes dependendo da situação, e acredito que experimentar e aprender coisas novas constantemente é sinal de um bom programador. Obviamente, bibliotecas prontas estão aí e foram feitas para serem usadas, mas nunca é perda de tempo aprender como algo é feito. Agora não recomendo ninguém trabalhar com programação se você faz por gostar, visto que vai deixar de ser divertido ¯\_(ツ)_/¯

Acho muito bacana trazer esse conteúdo pra cá, May o/ (a propósito, o exemplo em C++ pode ser mais otimizado xD, mas é só meu lado cpluspluslesco gritando)