Bubble Sort

This is the first article in an educational series covering various sorting techniques. The goal is to cover many of the popular sorting techniques, starting with the easiest to understand, and building up to a discussion about the strategies used by popular JavaScript engines to optimize the sort function of Array. Today’s article will cover bubble sort.

Bubble sort is a simple sorting algorithm that repeatedly steps through a list, comparing each pair of adjacent items and swapping them if they are in the wrong order. The algorithm gets the name bubble because smaller values rise to the top, like bubbles in a liquid. Anyway, this is a poorly performing algorithm because worst and average case performance requires passing through the complete array once for every value in the array or O(n2).

How do it…

Here is a simple bubble sort algorithm in JavaScript:

function bubbleSort(a) {
  var swapped = false,
    i = 1,
    j = a.length,
    tmp;

  for (; i < j; i += 1) {
    if (a[i - 1] > a[i]) {
      tmp = a[i];
      a[i] = a[i - 1];
      a[i - 1] = tmp;
      swapped = true;
    }
  }

  if (swapped) {
    bubbleSort(a);
  }
}

Here it is in action:


Restart Bubble Sort With New Array

After watching the demo above, you’ve probably concluded that there are some simple changes that could be made to improve algorithm performance. Most notably, by observing that the n-th pass finds the n-th largest element and puts it into its final place, so we do not need to iterate over those elements again. Here it is in action:


Restart Improved Bubble With New Array

The code for this new version is:

function bubbleSort(a, b) {
  var swapped = false,
    i = 1,
    j = a.length,
    tmp;

  if (! b) {
    b = 0;
  }

  j -= b;

  for (; i < j; i += 1) {
    if (a[i - 1] > a[i]) {
      tmp = a[i];
      a[i] = a[i - 1];
      a[i - 1] = tmp;
      swapped = true;
    }
  }

  if (swapped) {
    bubbleSort(a, b + 1);
  }
}

Lastly, notice after every pass all elements after the last swapped element are sorted, so we can further reduce the search space of subsequent iterations to the last swapped index.


Restart Optimized Bubble With New Array

The code for the optimized version is:

function bubbleSort(a, b) {
  var swapped = false,
    i = 1,
    j = a.length,
    tmp;

  if (! b) {
    b = 0;
  }

  j -= b;

  for (; i < j; i += 1) {
    if (a[i - 1] > a[i]) {
      tmp = a[i];
      a[i] = a[i - 1];
      a[i - 1] = tmp;
      swapped = true;
    }
  }

  if (swapped) {
    bubbleSort(a, b + 1);
  }
}

Lastly, if we take a 1000 element array and sort it, here is how bubble sort compares to native array sort (prints to the console):

Bubble Sort Comparison Tests

How it works…

The bubble sort algorithm visits each neighboring pair of elements in an array and swaps them, if the nth + 1 element is lesser than the nth. It keeps iterating over all elements in the array until no swaps need to be made, then it is done. This means that it frequently visits elements in the array that are already sorted. We made a simple modification to the algorithm, where the final largest element in each pass, becomes fixed, reducing the search space of each subsequent sort. The last improvement that is commonly made is to keep track of the last swap, each iteration, as all elements thereafter are guaranteed to be sorted.

Even with all the improvements, bubble sort performs much worse than the built in browser array sort function, and it is also considered the least efficient of the simple sorting algorithms. However, there is one instance where bubble sort is fairly efficient. If the list you have is likely to be sorted already, then bubble sort will tend to perform better than some of the more efficient algorithms (even quicksort), as it may only need to make one pass through the array.

There’s more…

For more information, see the Bubble Sort Wikipedia article.