Published on

Bubble sort - ordenação em bolha usando Javascript

Bubble sort ou ordenação em bolha.

O Bubble Sort é um algorítimo de ordenação simples que itera repetitivamente sobre cada posição de uma lista, comparando o valor do elemento na posição atual com o valor do elemento na próxima posição, trocando os valores de posição, quando necessário.

O algorítimo itera repetitivamente sobre cada elemento da lista até que nenhuma troca seja necessária durante a iteração atual.

O algrítimo ordena por comparação e tem o nome de bubble ou bolha, pois os maiores valores são jogados para o topo da lista.

Performance

Complexidade de tempo:

  • Pior caso

    O(n^2) comparações,

    O(n^2) trocas

  • Melhor caso

    O(n) comparações,

    O(1) trocas

  • Performance média

    O(n^2) comparações,

    O(n^2) trocas

Bubble sort tem em pior caso a complexidade O(n^2), onde n é o número de items a serem sorteados.

Outros algorítimos possuem piores casos ou complexidade média substancialmente melhores do que bubble sort, geralmente O(n log n). Até mesmo outros algorítimos O(n^2), como insertion sort, geralmente são executados mais rápidos do que o bubble sort. Por essa razão, o bubble sort é raramente utilizado em produção.

Pode ser mais vantajoso utlizar o bubble sort quando sabe-se que boa parte do conteúdo do vetor já se encontra ordenado.

Implementando com o uso do for.

    function bubbleSort(arr) {
        const vetor = [...arr];
        const numeroElementosVetor = vetor.length;
        // itera sobre cada elemento do vetor
        for(let x = 0; x < numeroElementosVetor; x++) {
            let houveTroca = false;
            // para cada elemento do vetor, itere novamente sobre todo o vetor,
            // comparando o valor da posicao atual com o valor da proxima posicao.
            // troque o valor da posicao atual caso o valor da proxima posicao seja maior que o valor atual.
            for(let y = 0; y < numeroElementosVetor; y++) {
                const valorAtual = vetor[y];
                const proximoValor = vetor[y + 1];
                if(valorAtual > proximoValor) {
                    vetor[y + 1] = valorAtual;
                    vetor[y] = proximoValor;
                    houveTroca = true;
                }
            }
            // se não houve troca, o vetor já está ordenado.
            if(!houveTroca) break;
        }

        return vetor;
    }

    console.log( bubbleSort([5 ,9, 2 , 3]) ) //  [ 2, 3, 5, 9 ]

Implementando com o uso do while.

    function bubbleSort(arr) {
        const vetor = [...arr];
        const numeroElementosVetor = vetor.length;
        let totalMinimoIteracoes = 0;
        let houveTroca = false;
        // itera ao menos ao primeiro elemento do vetor
        while (totalMinimoIteracoes < numeroElementosVetor) {
            let iteracaoSecundaria = 0;
            // itera sobre cada elemento do vetor
            while (iteracaoSecundaria < numeroElementosVetor) {
                const valorAtual = vetor[iteracaoSecundaria];
                const proximoValor = vetor[iteracaoSecundaria + 1];
                if(valorAtual > proximoValor) {
                    vetor[iteracaoSecundaria + 1] = valorAtual;
                    vetor[iteracaoSecundaria] = proximoValor;
                    houveTroca = true;
                }
                iteracaoSecundaria++;
            }
            // se não houve troca, o vetor já está ordenado.
            if(!houveTroca) {
                // sair do loop
                totalMinimoIteracoes = numeroElementosVetor
            } else {
                totalMinimoIteracoes++;
            }
        }
        
        return vetor;
    }

    console.log( bubbleSort([5 ,9, 2 , 3]) ) //  [ 2, 3, 5, 9 ]