Ordering arrays with Bubble Sort

Question

I’m solving a question of my course which I need to use a vector ordering algorithm based on the Bubble Sort algorithm.

Making a previous summary, the logic consists of going through all the values of the array, in pairs, comparing each other and checking which one is larger. The largest number will always go to the right, switching with the smallest value, thus always passing the largest number to the extreme right. After passing through all the numbers of the array and sorting the first time, the repetition loop repeats by the number number of the array until all values are sorted.

I wrote this code and it’s functional:

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)

Code out:

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

As I’m still learning, I’d like to know how I could refactor the code so I didn’t need to use a function to do the second loop repeat. I tried to put it inside for but it ended up returning me undefined when I print the output on the console. You can give me tips to make the code more readable and simple?

Answer 1

The first thing is to put the entire algorithm within the function. If the 2 loops are part of the algorithm, so both should be there, you shouldn’t depend on a loop external function to function properly.

Another detail is that the function, as it was made, accesses the array bubble that was created outside the function. That is, it only works for that array. It would be better if it received the array as a parameter, so it works for any 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);

I also made a change in the loops. Doesn’t make any sense i how much j start from scratch (because then I will be comparing the element with itself). Another detail is that, after the first iteration, the first element will surely be the smallest of all, so there is no reason to compare it again in the following iterations. Thus, the loop internal always starts in i + 1 (instead of always starting from scratch).

Of course that won’t be that optimization, since Bubble Sort itself is not the most efficient algorithm of all, and for small arrays the difference will be imperceptible. But anyway, gets faster.

And note that this function modifies the array. If you want it not to modify the original array, do as a another answer indicated.

---

I also put a semicolon at the end of the lines. It may sound "fresh," and I know that Javascript "accepts" the semicolon code and "works," but it avoids some bizarre situations that can occur if you don’t use them, like that one and that one (see more about this here).

Answer 2

If you want to remove the "intermediate function" bubbleSort, just "relocate" the loop for that is in her body into the for main. Thus:

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]));

And it will work as expected. Note also that I "extracted" all the code into a single function, coincidentally called bubbleSort. So we can call the same function several times passing different arrays to be sorted. I also made a copy of array passed as argument to avoid mutations in the original list.

The problem with the above code is that it will always N^2 iterations, being N the quantity of elements of the array to be drawn. That’s because you haven’t implemented any means of verifying whether the array has already been properly classified. To illustrate this, let’s take the example below:

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 that, even if already drawn, a list will be swept (unnecessarily) 25 times, that is, the square of its number of elements.

A simple boolean can solve this problem. We will use it to indicate, from the "internal loop", when a change is made. Thus, from the "external link", we can verify if an "exchange" was made in any of the iterations of the "internal tie". In case that didn’t happen, we can assume that the array has already been drawn. So:

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 now that even if one array Already properly drawn is passed, instead of 25, only 5 iterations will occur (which is the best scenario). We can verify this by adding the counter:

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).

Worst case scenario, the N^2 will still be necessary, as it is an intrinsic feature of the algorithm.

Some over optimizations can also be done. But overall, this is not an efficient algorithm and there are more performative alternatives. A another answer gives a little more detailed explanation about this optimization.

Answer 3

I believe that the fastest way is to travel until you reach the end of this ordination:

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))

But if you want to get better, you can do this:

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))