Ordenação por flutuação - Bubble Sort

dormin

Daniel Dormin

Posted on October 3, 2022

Ordenação por flutuação - Bubble Sort

Começando meus estudos de algoritmos cai no Bubble sort.
Vamos entender o que é um algoritmo para começar nossa caminhada de estudo.

Em matemática e ciência da computação, um algoritmo é uma sequência finita de ações executáveis que visam obter uma solução para um determinado tipo de problema. Segundo Dasgupta, Papadimitriou e Vazirani; "Algoritmos são procedimentos precisos, não ambíguos, padronizados, eficientes e corretos." - Wikipédia

Esse trecho do wikipédia é o suficiente para entendermos o que é um algoritmo. Sabendo disso podemos passar para o algoritmo de estudo, o bubble sort, como o nome diz esse é um algoritmo de ordenação, ou seja o objetivo dele é ordenar uma estrutura de dados como um array. Por exemplo:

//Um array desordenado
var arr = [ 2, 3, 6, 1, 5, 7]
//Um array ordenado
var arr = [1, 2 , 3, 5, 6, 7]
Enter fullscreen mode Exit fullscreen mode

Neste exemplo o array está ordenado de forma crescente mas a ordenação pode ser feita conforme a necessidade.
O bubble sort reorganiza o array para que a ordenação seja feita.

Como o Bubble sort faz isso?

O bubble sort funciona comparando de dois em dois valores, trocando-os de lugar do maior pro menor ou do menor pro maior por meio de um loop e uma condicional. exemplo:

var arr = [ 2, 3, 6, 1, 5, 7]
Enter fullscreen mode Exit fullscreen mode
  • Na primeira comparação ele compara o primeiro e o segundo valor (2 e 3), não há nada para trocar ele passa para a próxima dupla.

  • Na segunda volta ele compara o segundo e o terceiro valor (3 e 6), também não precisa ser alterado.

  • Na terceira volta compara o terceiro e o quarto valor (6, 1), aqui os valores são trocados assim os organizando (1, 6).

E assim continua até que o maior valor fique totalmente à direita, depois ele volta fazendo de novo a comparação, até o segundo maior valor está organizado, seguindo até que todo o array esteja organizado.
Neste ponto podemos perceber que precisamos de dois loops, um loop para mais interno para comparar todos os valores e reorganizar o array e um mais externo para que ele faça isso para cada item do array.
O código fica assim:

let lista = [17, 2, 3, 4, 5]
let numero = 0
console.log(lista)
for (let i = 0; i <= lista.length - 1; i++) {
    for (let i = 0; i <= lista.length - 1; i++) {
        if (lista[i] >= lista[i + 1]) {
            numero = lista[i]
            lista[i] = lista[i + 1]
            lista[i + 1] = numero
        }
    }

}
console.log(lista)
Enter fullscreen mode Exit fullscreen mode

Fiz uma demonstração, caso queira conferir o link é: https://codepen.io/ddparkas/pen/JjpVJdb

Muito obrigado por ler até aqui abaixo deixo as referências usadas:
https://pt.wikipedia.org/wiki/Algoritmo
https://pt.wikipedia.org/wiki/Bubble_sort

💖 💪 🙅 🚩
dormin
Daniel Dormin

Posted on October 3, 2022

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Ordenação por flutuação - Bubble Sort