Bubble Sort in JavaScript

Lately, I’ve been working on my understanding of algorithms. This post will try to explain and implementation of sorting with the easiest method — bubble sort.

Although the bubble sort algorithm compared to other sorting algorithms isn’t that efficient, and isn’t used anywhere in the real world, interviewers still commonly check for it during interviews. It is good to at least know how it works under the hood.

How does bubble sort (you can also find it under the alternate name sinking sort) work? The algorithm ‘bubbles’ large values (thus the name) to the top on each iteration of the algorithm. Then it compares adjacent elements between each other and swaps them if they are in the wrong order.

Pseudocode looks like this:

1. The algorithm will compare two adjacent elements. For example a and b.
2. The algorithm will swap them if they are out of order by checking whether a is less than b
3. The algorithm will repeat steps 1. and 2. until the end of the array is reached. At the end of the iteration, the largest number should be at the very end of the array.
4. The algorithm will then ignore the last item and repeat step 1 until all the elements are sorted

Let us visualize this algorithm using the inputs [15, 6, 4, 18, 7, 13, 1].
The algorithm is visualized using visualgo.

First, we compare every element with its adjacent elements (green elements). If the element is larger — it will be swapped, during each iteration, the largest element will be stuck to the end (orange elements). This process repeats itself until all the elements are sorted.

Implementation

function bubbleSort(arr) {
    for(let i = arr.length; i > 0; i--) {
        for(let j = 0; j < i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}
bubbleSort([15, 6, 4, 18, 7, 13, 1]);

Every iteration we reduce the iterator by 1 (because the last element is already sorted!). if the element is bigger than its adjacent element, we will use the swapping mechanism [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] (a pretty cool ES6 concept to swap items in place without the need for a temporary variable).

Optimize it!

There is one specific scenario in which we can optimize the algorithm a bit.

If the array is almost sorted — needing to rearrange only an item or two, the algorithm still goes through all the loops, even though nothing is happening.

In order to fix this — we just need to check whether we made any swaps.

function bubbleSort(arr) {
  let swapHappened;
  for (let i = arr.length; i > 0; i--) {
    swapHappened = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapHappened = false;
      }
    }
    if (swapHappened) {
      break;
    }
  }
  return arr;
}
bubbleSort([2, 4, 6, 5, 7, 9, 12]);

Big O Complexity

The average Big O of bubble sort is O(n2) because we iterate twice through the whole array. We need to compare the current element to every other element in the array.

Conclusion

That’s it! Bubble sort isn’t a very demanding algorithm to learn. I’ll post more sorting algorithms in the future. In the meantime, please check my LinkedIn for any questions. Happy Coding!

Marcus Siegel - Austin, Texas, United States | Professional Profile | LinkedIn