Bubble Sort in JavaScript

Bubble sort is a sorting algorithm where we compare each element in the array with the other element in the array. We swap the two elements if the first element is greater than the second element.

Here is a diagram of what it look like

Sorting an array with 8 elements

Algorithm

Start at the first index of the array and compare the value at the first index with the value at the next index. For example, array starts at 0, so we compare the value at index 0 with the value at index 1. If the value at index 0 is greater than index 1 then we swap the values at index 0 with index 1.

After the swap is done we compare the value at index 0 with the value at index 2 and swap the values if value at index 0 is greater than the value at index 2.

The above process repeats until we have reached the end of the array. After we reach the end of the array, we start again at index 1 and comparing the value at index 1 with value at index 2 and we keep repeating this process until we have reached the end of the array.

What we need

From the above description we need a way to loop through the entire array. We can use a for loop for this task.

It also appears that we need another loop on top of the above mentioned loop which starts at index 0 and keeps on incrementing until we have reached the end of the array. Sounds like this is a job for another for loop.

We need a function to swap two elements in an array and we are going to do this with the help of a temporary variable.

Implementation

const swap = (arr, indexOne, indexTwo) => {
  const tempValue = arr[indexOne];
  arr[indexOne] = arr[indexTwo];
  arr[indexTwo] = tempValue;
};

const bubbleSort = (arr) => {
  for (let index = 0; index < arr.length; index++) {
    for (let innerIndex = index + 1; innerIndex < arr.length; innerIndex++) {
      if (arr[index] > arr[innerIndex]) {
        swap(arr, index, innerIndex);
      }
    }
  }
};

The outer for loop starts at index 0 and the inner for loop starts at index 1 and the inner for loop goes through the entire array starting from index 1 to length of the array - 1.

The index at the outer loop now moves to 1 and the inner index starts at index 2 and the inner loop goes through the entire array starting from index 2 to length of the array - 1.

The entire process is repeated until the outer loop has gone through the entire array and at the end we have a sorted array.

Optimized Algorithm

Let's see how we can optimize the above algorithm with a diagram

From the above diagram, we compare the first two adjacent elements and move the bigger number to the right.

We always start with index 0 and index 0 + 1 and if the element at index 0 is greater than at index 0 + 1 then we swap the elements. We then compare index 1 with index 2 and so on... when we reach the end of the array the biggest number will be at the end of the array.

If we have gone over the array once, we will have the biggest number to the right end of the array. Which also means that we now need to sort n - 1 elements if n is the length of the array. For example, if the array has 8 elements as we see above then we have 7 elements to sort.

Everytime we go over the array we have one less element to sort. So if we have gone of the array once then we have to sort n - 1 elements. If we have gone over the array twice then we have to sort n - 2 elements. If we have gone over the array thrice then we have to sort n - 3 elements... and so on. At some point n will be 0 and we have no elements to sort.

What we need?

As we saw earlier, we need a variable to keep track of the ever changing length, meaning we cannot use the length property of the array as that will be a constant. So we need a variable to keep track of the length of the array. Let's call this variable, elementsToSort. We keep looping over the array as long as elementsToSort is greater than 0.

It could be that the array is sorted and elementsToSort is not yet 0, hence the swap function is not called once as we go through the array. So we need a variable to let us know whether to keep going on or not. Let's call this variable keepGoing.

We need a for loop because we need to go through the entire array.

Our diagram also showed us that we need to go over the array multiple times and we only do that if the keepGoing variable is set to true. So we need a do...while loop because we want to loop at least once to check if the any elements need to be swapped or not.

Variables with good names are helpful.

We can reuse the same swap function we saw earlier

Implementation

Let's look at the code in JavaScript

const swap = (arr, indexOne, indexTwo) => {
  const tempValue = arr[indexOne];
  arr[indexOne] = arr[indexTwo];
  arr[indexTwo] = tempValue;
};

const bubbleSort = (arr) => {
  let elementsToSort = arr.length;
  let keepGoing = false;

  do {
    keepGoing = false;

    for (let index = 0; index < elementsToSort; index++) {
      if (arr[index] > arr[index + 1]) {
        swap(arr, index, index + 1);
        keepGoing = true;
      }
    }

    elementsToSort--;
  } while (keepGoing === true);
};

Bubble sort is not an ideal sorting algorithm and is not good when it comes to performance. In the future we will look at other algorithms which are better at sorting arrays.

The code seen in this article can be found here and I need to work on my diagrams.