Ordenação por flutuação - Bubble Sort
Daniel Dormin
Posted on October 3, 2022
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]
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]
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)
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
Posted on October 3, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.