6

Estou resolvendo uma questão do meu curso a qual eu preciso usar um algoritmo de ordenação de vetores com base no algoritmo Bubble Sort.

Fazendo um resumo prévio, a lógica consiste em passar por todos os valores do array, em pares, comparando um ao outro e verificando qual é maior. O número maior sempre irá para a direita, trocando com o valor menor, passando assim sempre o maior número para a extrema direita. Após passar por todos os números do vetor e ordenar a primeira vez, o laço de repetição se repete pela quantidade de números do array até ordenar todos os valores.

Eu escrevi esse código e ele está funcional:

let bubble = [82, 76, 6, 52, 45, 38, 24, 14, 54, 85, 143, 98, 65, 512, 96, 12, 4, 79];
    
function bubbleSort () {
    for (let i = 0; i < bubble.length; i++) {
        if (bubble[i] > bubble[i +1]) {
            let v1 = bubble[i]
            let v2 = bubble[i +1] 
            bubble[i] = v2
            bubble[i +1] = v1
        }
    }
}

for (let j = 0; j < bubble.length ; j++) {
    bubbleSort();
}

console.log(bubble)

Saída do código:

[
   4,  6,  12,  14, 24, 38, 45,
  52, 54,  65,  76, 79, 82, 85,
  96, 98, 143, 512
]

Como ainda estou aprendendo, gostaria de saber como eu poderia refatorar o código para que eu não precisasse usar uma function para fazer a segunda repetição do laço. Tentei colocar for dentro de for mas ele acabou me retornando undefined quando imprimo a saída no console. Podem me dar dicas para que o código fique mais legível e simples?

3 Respostas 3

8

A primeira coisa é colocar todo o algoritmo dentro da função. Se os 2 loops fazem parte do algoritmo, então ambos deveriam estar lá, você não deveria depender de um loop externo para que a função funcione corretamente.

Outro detalhe é que a função, da forma que foi feita, acessa o array bubble que foi criado fora da função. Ou seja, só funciona para aquele array. Seria melhor que ela recebesse o array como parâmetro, assim ela funciona para qualquer array:

function bubbleSort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = i + 1; j < array.length; j++) {
            if (array[i] > array[j]) {
                let aux = array[i];
                array[i] = array[j];
                array[j] = aux;
            }
        }
    }
}

let numeros = [82, 76, 6, 52, 45, 38, 24, 14, 54, 85, 143, 98, 65, 512, 96, 12, 4, 79];
bubbleSort(numeros);
console.log(numeros);

// posso reaproveitar a função para ordenar outro array
let outroArray = [1, 5, 34, 2, 6, 7, 8, 12];
bubbleSort(outroArray);
console.log(outroArray);

Também fiz uma alteração nos loops. Não faz sentido tanto i quanto j começarem do zero (pois aí estarei comparando o elemento com ele mesmo). Outro detalhe é que, depois da primeira iteração, o primeiro elemento com certeza já será o menor de todos, então não tem porque compará-lo novamente nas iterações seguintes. Sendo assim, o loop interno sempre começa em i + 1 (em vez de sempre começar do zero).

Claro que isso não vai ser aquela otimização, já que bubble sort em si não é o algoritmo mais eficiente de todos, e para arrays pequenos a diferença será imperceptível. Mas de qualquer forma, fica mais rápido.

E vale notar que esta função modifica o array. Se quiser que ele não modifique o array original, faça como a outra resposta indicou.


Também coloquei ponto-e-vírgula no final das linhas. Pode parecer "frescura", e sei que o JavaScript "aceita" o código sem ponto e vírgula e "funciona", mas isso evita algumas situações bizarras que podem ocorrer se você não usá-los, como essa e essa (veja mais sobre isso aqui).

7

Se você quiser remover a função "intermediária" bubbleSort, basta "realocar" o laço for que está no corpo dela para dentro do for principal. Assim:

function bubbleSort(originalArray) {
  const bubble = [...originalArray];

  // Este é o laço que antes estava no escopo global:
  for (let j = 0; j < bubble.length ; j++) {

    // Este é o laço que antes estava dentro da função:
    for (let i = 0; i < bubble.length; i++) {
      if (bubble[i] > bubble[i +1]) {
        let v1 = bubble[i];
        let v2 = bubble[i +1];
        bubble[i] = v2;
        bubble[i +1] = v1;
      }
    }
  }
  
  return bubble;
}

console.log(bubbleSort([4, 2, 5, 3, 1]));

E funcionará como esperado. Note também que eu "extraí" todo o código para dentro de uma única função, coincidentemente chamada bubbleSort. Assim, poderemos chamar a mesma função diversas vezes passando diferentes arrays para serem classificados. Também fiz uma cópia do array passado como argumento para evitar mutações na lista original.

O problema do código acima é que ele sempre fará N^2 iterações, sendo N a quantidade de elementos do array a ser sorteado. Isso porque você não implementou nenhum meio de verificar se o array já foi devidamente classificado. Para ilustrar isso, vejamos o exemplo abaixo:

function bubbleSort(originalArray) {
  const bubble = [...originalArray];
  
  let counter = 0;

  for (let j = 0; j < bubble.length ; j++) {
    for (let i = 0; i < bubble.length; i++) {
      counter++;
      
      if (bubble[i] > bubble[i +1]) {
        let v1 = bubble[i];
        let v2 = bubble[i +1];
        bubble[i] = v2;
        bubble[i +1] = v1;
      }
    }
  }
  
  console.log(counter);
  return bubble;
}

bubbleSort([1, 2, 3, 4, 5]);
// Imprimirá 25 no console (25 iterações foram feitas).

Note que, mesmo que já devidamente sorteada, uma lista será varrida (desnecessariamente) 25 vezes, isto é, o quadrado do seu número de elementos.

Um simples booleano pode resolver esse problema. Usaremos ele para indicar, do "laço interno", quando uma mudança for realizada. Desse modo, a partir do "laço externo", poderemos verificar se uma "troca" foi feita em alguma das iterações do "laço interno". No caso disso não tiver acontecido, podemos assumir que o array já foi sorteado. Assim:

function bubbleSort(originalArray) {
  // Copiamos o array para evitar modificações no array original:
  const array = [...originalArray];

  for (let i = 0; i < array.length; i++) {
    // Booleano que usaremos para verificar se houve troca:
    let swapped = false;

    for (let j = 0; j < array.length; j++) {
      const current = array[j];
      const next = array[j + 1];

      if (current > next) {
        array[j + 1] = current;
        array[j] = next;

        // Marcamos `swapped` como `true` para indicar que houve troca.
        swapped = true;
      }
    }

    // Se não houve nenhuma troca nesta iteração, significa
    // que o array já está sorteado. Podemos, então, sair.
    if (!swapped) {
      break;
    }
  }

  return array;
}

console.log(bubbleSort([4, 2, 5, 3, 1]));

Note agora que, mesmo que um array já devidamente sorteado seja passado, ao invés de 25, somente ocorrerão 5 iterações (que é o melhor cenário). Podemos verificar isso adicionando o contador:

function bubbleSort(originalArray) {
  // Copiamos o array para evitar modificações no array original:
  const array = [...originalArray];

  let counter = 0;

  for (let i = 0; i < array.length; i++) {
    // Booleano que usaremos para verificar se houve troca:
    let swapped = false;

    for (let j = 0; j < array.length; j++) {
      counter++;

      const current = array[j];
      const next = array[j + 1];

      if (current > next) {
        array[j + 1] = current;
        array[j] = next;

        // Marcamos `swapped` como `true` para indicar que houve troca.
        swapped = true;
      }
    }

    // Se não houve nenhuma troca nesta iteração, significa
    // que o array já está sorteado. Podemos, então, sair.
    if (!swapped) {
      break;
    }
  }

  console.log(counter);
  return array;
}

bubbleSort([1, 2, 3, 4, 5]);
// Imprimirá 5 no console (5 iterações foram feitas — esse é o improvável melhor cenário).

Para o pior cenário, os N^2 ainda serão necessários, já que é uma característica intrínseca do algoritmo.

Algumas otimizações a mais podem ser feitas também. Mas, no geral, esse não é um algoritmo eficiente e existem alternativas mais performáticas. A outra resposta dá uma explicação um pouco mais detalhada sobre essa otimização.

3
  • Era exatamente isso que eu precisava, Luiz! Não estou ainda pensando em implementações melhores pois estou passando pelo caminho das pedras antes antes de chegar em recursos mais eficientes, seguindo a linha do meu curto. Me ajudou bastante, e a implementação com o boolean matou essa questão de passar diversas vezes pelos números mesmo demais de estarem sorteados. Ainda assim, percebi que não houve redução do tempo de execução do código (antes 0.05~, agora 0,05~), existe alguma explicação para isso? Commented 19/10/2020 às 12:15
  • Provavelmente o número de elementos é tão pequeno que faz pouca diferença. A adição do boolean evita algumas iterações adicionais, mas em quase nada ajuda para contornar a ineficiência intrínseca desse algoritmo (O(N^2) não é muito bom, no pior dos casos...). Ah, e como você é novo no site, não esqueça de verificar no tour a melhor forma de dizer obrigado. Bem-vindo. :-) Commented 19/10/2020 às 12:17
  • @DiegoAugustoF. Tem que ver também como vc está medindo (eu uso sites como o jsbench.me) - e também coloquei uma resposta com outra alternativa (mas não vai melhorar tanto assim, bubble sort é ineficiente por definição)
    – hkotsubo
    Commented 19/10/2020 às 12:19
0

Acredito que a forma mais rápida é percorrendo até chegar no final dessa ordenação:

let bubble = [82, 76, 6, 52, 45, 38, 24, 14, 54, 85, 143, 98, 65, 512, 96, 12, 4, 79];
    
function bubbleSort(arr) {
         let t = arr.length;
        while (t) {
            for (let i in arr) {
                if (arr[ i ] > arr[i + 1]) {
                    let temp = arr[ i ];
                    arr[ i ] = arr[i + 1];
                    arr[i + 1] = temp
                }
            }
            t--;
        }
        return arr;
    }
    
    console.log(bubbleSort(bubble))

Mas se quiser melhorar, pode fazer isso:

let bubble = [82, 76, 6, 52, 45, 38, 24, 14, 54, 85, 143, 98, 65, 512, 96, 12, 4, 79];
 
function bubbleSort(arr) {
    return arr.sort((a, b) => {
        return (a < b+1) ? -1 : 1
 });
}
    console.log(bubbleSort(bubble))

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .