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 until the array is sorted:

Iteration 1: [5,3,1,4,6] → [3,5,1,4,6] → [3,1,5,4,6] → [3,1,4,5,6] → [3,1,4,5,6]

Iteration 2: [3,1,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6]

Iteration 3: [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6]

As you can see, after iteration 2 the array is already sorted. Bubble sort, however, needs a final pass through the array to ensure that no other swaps are necessary before returning the array. Here’s one way to code bubble sort:

let bubbleSort = (inputArr) => {
    let len = inputArr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (inputArr[j] > inputArr[j + 1]) {
                let tmp = inputArr[j];
                inputArr[j] = inputArr[j + 1];
                inputArr[j + 1] = tmp;
            }
        }
    }
    return inputArr;
};

With the implementation above, the code will run until the “i” variable is equal to the “len” variable, which means that it may run on an already sorted array more than once. Another slightly more efficient way to code bubble sort that is slightly more efficient is to keep track of a variable “swapped” which is initially set to false. During each iteration, if values are swapped, then the “swapped” variable is set to true. Then, using a do-while loop, it will only run the code if the swapped variable is true, thus ensuring that only 1 extra verification iteration happens. The code for that looks like this:

let bubbleSort = (inputArr) => {
    let len = inputArr.length;
    let swapped;
    do {
        swapped = false;
        for (let i = 0; i < len; i++) {
            if (inputArr[i] > inputArr[i + 1]) {
                let tmp = inputArr[i];
                inputArr[i] = inputArr[i + 1];
                inputArr[i + 1] = tmp;
                swapped = true;
            }
        }
    } while (swapped);
    return inputArr;
};

That’s it for bubble sort! Feel free to copy and paste that code into your browsers console to see how it works! You can also add some console.log statements in the if block to see how the array looks after each iteration as it’s being sorted (careful as this will spam your console). You can also check out my post on insertion sort to learn more about that more useful algorithm. Thanks for reading!