DEV Community 👩‍💻👨‍💻

Daniel Dormin
Daniel Dormin

Posted on • Updated on

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

Top comments (0)

11 Tips That Make You a Better Typescript Programmer

1 Think in {Set}

Type is an everyday concept to programmers, but it’s surprisingly difficult to define it succinctly. I find it helpful to use Set as a conceptual model instead.

#2 Understand declared type and narrowed type

One extremely powerful typescript feature is automatic type narrowing based on control flow. This means a variable has two types associated with it at any specific point of code location: a declaration type and a narrowed type.

#3 Use discriminated union instead of optional fields

...

Read the whole post now!