Javascript Algorithms — Bubble Sort

The next algorithm in the Javascript Algorithms series is bubble sort. Like insertion sort, bubble sort is a comparison algorithm and runs in O(n²) time, making it an inefficient algorithm for larger lists. As we saw in the last post about insertion sort, often times in practice quadratic sorting algorithms will outperform more advanced algorithms on very small lists. Bubble sort, while still holding true to that principal, is inefficient even on small inputs when compared to insertion sort. Odds are, you’ll never actually implement bubble sort in practice, but it can still prove useful to know. It’s best case run time is O(n), or linear, which occurs if the input array is already sorted. On average, bubble sort’s run time is still quadratic.

The idea behind bubble sort is that every pair of adjacent values is compared, and then the two values swap positions if the first value is greater than the second. This way during each pass through the array, the largest value “bubbles up” to the top, and after each pass the elements furthest to the right are in the correct order. Here’s an example: given the array [5,3,1,4,6] we can use bubble sort to sort the array in ascending order. It’ll start by comparing the first pair of values, 5 & 3. 3 is smaller than 5, so it’ll swap the two values and then move on to compare the next pair of values, 5 & 1. It’ll continue doing this over and over…