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.