Bubble Sort

Bom, já que ontem eu dei uma boa estudada em algoritmos de ordenação, hoje vou postar o mais fácil (na minha opinião) para aqueles que ainda não conhecem.

Algoritmos de ordenação são muito básicos, e em alguns momentos eles podem ser muito úteis no seu programa.

Do que se trata?

Digamos que você receba uma quantidade N de valores, e você precisa colocá-los em ordem. Exemplo:

Você recebe os valores 4, 3, 6, 2, e 1, nesta mesma ordem, e agora precisa colocá-los em ordem crescente (1, 2, 3, 4, 6), ou decrescente (6, 4, 3, 2, 1).

É aí que entra o algoritmo de ordenação.

Existem vários algoritmos famosos de ordenação, cada um com um método, um nível de complexidade, um tempo de execução, etc.

Hoje eu vou explicar o mais básico, porém muito útil, algoritmo de ordenação, o Bubble Sort, ou, Método Bolha.

Na teoria, o bubble sort escolhe um valor na cadeia de valores e compara-o com o valor seguinte, para descobrir qual deles é maior, ou menor, e troca-os de lugar.

Vejamos um exemplo. A cadeia de valores está nesta ordem {5,3,2}. O algoritmo vai olhar primeiramente o primeiro valor da cadeia (5), e compará-lo com o segundo (3), para descobrir qual o maior. No caso, o primeiro valor é o maior, e como eu quero que a sequência fica em ordem crescente, eu vou trocá-los de lugar. Portanto a ordem agora é {3,5,2}. Logo após esta troca, o algoritmo vai olhar o próximo valor e compará-lo com o próximo do próximo, ou seja, primeiro ele olhou o primeiro e o segundo valor, agora ele vai olhar o segundo e o terceiro. No nosso caso ele vai olhar o segundo valor (5), compará-lo com o terceiro (2), e descobrir qual o maior. Novamente o primeiro valor é maior que o segundo, portanto ele vai trocá-los de lugar. Agora nossa sequência é {3,2,5}. Agora o algoritmo teoricamente iria olhar o terceiro e o quarto valor, correto? Porém vemos que não há quarto valor, portanto nossa primeira varredura chega ao fim. Podemos notar que o maior valor de toda a cadeia está agora em seu devido lugar, no final dela.

Esta foi a primeira parte do algoritmo, a varredura. Porém, como você deve ter notado, a sequência ainda não está em ordem, portanto será necessária mais varreduras. Esta é a segunda parte do algoritmo. Raramente uma varredura será suficiente para organizar a ordem. Mesmo que sejam só 3 valores, 1 varredura não foi suficiente, portanto vamos fazer mais uma.

Começa então a segunda varredura. O algoritmo volta a atenção para o primeiro valor (3) e o compara com o segundo (2). Vendo que o primeiro é maior, ele os troca de lugar, fazendo com que a ordem agora seja {2,3,5}. Agora o algoritmo vai para a próxima posição e faz a verificação. Verifica-se o segundo valor (3), e o terceiro (5). Como podemos ver, o segundo valor é menor que o terceiro, portanto não precisaremos trocá-los de lugar, pois já estão em ordem.

Finalmente, o algoritmo está em ordem {2,3,5}, e não será necessária mais uma varredura.

Aqui entra a primeira optimização do algoritmo: Quando saber que não serão mais necessárias varreduras, e que devo parar de fazê-las?

É muito simples, basta você ter uma variável de controle (recomendo uma variável booleana, ou seja, true or false).

Antes de iniciar a varredura, você ativa uma variável chamada Fim com o valor de True. Agora você inicia a varredura, e caso em algum momento da varredura você precise mudar 2 valores de posições, você também muda o valor da variável Fim para False. Após a varredura estar completa você cria uma condição perguntando se a variável Fim é True or False.

Caso seja True, significa que não houve nenhuma mudança, portanto o algoritmo está em ordem, e nenhuma varredura ou troca será mais necessária.

Caso o valor se False, significa que em algum momento houve uma troca, e ainda não há certeza que todos estejam em ordem, portanto é recomendado uma nova varredura.

Existe outra  optimização deste algoritmo que optimiza o tempo de execução, que você pode conferir neste link.

Caso alguém ainda tenha dúvidas, recomendo que procurem outros tutoriais na internet, e até alguns exemplos.

Um site que contém uma breve explicação e também exemplos em múltiplas linguagens de programação é o wikipédia, neste link.

Espero que tenham gostado da minha explicação, e peço que perguntem caso tenham dúvida, ou se quiserem que eu poste mais algoritmos é só pedi-los. Contanto que eu tenha domínio sobre tal eu o explicarei com todo prazer.

Até a próxima.