Implement Bubble Sort in JavaScript

Algorithms
September 28, 2016

This article is part of a series covering sort algorithms in JavaScript. You can find the rest of the series here. 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 }

Congratulations on completing (possibly) your first sorting algorithm! Next up is insertion sort :)

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

More Blog Posts