This article is part of a series covering sort algorithms in JavaScript. If you’re new to sorting algorithms, or algorithms in general, read this first to get a solid foundation for moving forward.

While we do want to learn the most efficient algorithms, studying the most inefficient algorithms can also give us context about what exactly a good algorithm is, what it looks like, and why it’s considered ‘good’. Bubble sort is by far one of the worst sorting algorithms and should (most likely) never be used in production code, so keep that in mind as we move forward :)

This is often the easiest to conceptualize and a natural way for the brain to think about sorting. Bubble sort gets its name from what a visualization might look like as each number is bubbled up to the front of the array space by space. It’s a quadratic sorting algorithm because it uses an iterative approach by continuously looping and swapping elements until they are in the correct order.

Elements are only swapped with other elements that are one index away. This can lead to a large number of swaps because it’s so inefficient. Algorithms like insertion sort and selection sort perform drastically better.

Complexity

The worst case scenario of this algorithm is quadratic — O(n²) — because it’s possible that the data will be the exact opposite of ordered. Best case scenario is linear — O(n) — because even if it’s entirely ordered, we have to check through each set of numbers.

The space complexity of Bubble Sort is O(1).

When it's fast

There is one case where bubble sort is fairly efficient. This is when the list is sorted or almost entirely sorted, therefore it would only require swapping a few elements that are only one index away. However, this is only true if you use an optimized algorithmic approach to bubble sort which tracks if no swaps take place and therefore exits the sort early. I’ll explore the code for this algorithm below.

Pseudocode

function bubbleSort(array, compare, swap) {
  Slice array to make it a pure function
  Create var for array length
  Do
    Create var to keep track of swapped
    Loop through array up to the array length
      If current value is greater than next value
        create temp var as current value
        Swap the current value and next value
        Set swap variable to true
  While swapped var is equal to true
  return sliced array variable

Code

Below is the optimized version of bubble sort that will exit the sort function if no swaps take place. The key here is to use a while loop where it can track if it doesn’t attempt to sort elements after the element that was swapped last in the most previous iteration.

function sort(values) {
  var origValues = values.slice();
  var length = origValues.length - 1;
  do {
    var swapped = false;
    for(var i = 0; i < length; ++i) {
      if (origValues[i] > origValues[i+1]) {
        var temp = origValues[i];
        origValues[i] = origValues[i+1];
        origValues[i+1] = temp;
        swapped = true;
      }
    }
  }
  while(swapped === true);
  return origValues
}