Skip to main content
adicionou 146 caracteres ao conteúdo
Fonte Link
Luiz Felipe
  • 36,5mil
  • 10
  • 74
  • 154

E funcionará como esperado. Note também que eu "extrai""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.

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

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.

E funcionará como esperado. Note também que eu "extrai" 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.

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

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.

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.

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.

removeu 25 caracteres do conteúdo
Fonte Link
Luiz Felipe
  • 36,5mil
  • 10
  • 74
  • 154

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

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

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:

Fonte Link
Luiz Felipe
  • 36,5mil
  • 10
  • 74
  • 154

Se você quiser remover a função "intermediária" bubbleSort, basta removê-la e simplesmente "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 "extrai" 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 do algoritmo em si.

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.