Algorithm Action: Bubble Sort

Photo by Daniele Levis Pelusi on Unsplash

Algos, algos, algos: the cornerstone of a competent software engineer. This is why I’m compiling all my research and work on the topic in a set of articles titled Algorithm Action.

Today, we’re checking out a specific sorting pattern known as bubble sort.

What is it?

Bubble Sort if an algorithm where the largest values “bubble” to the top. While it’s not commonly used or very efficient, it does work in niche situations. In the category of sorting algorithms, it’s especially important to know what each type does and in what situations they perform optimally. This knowledge is the kind that separates juniors from everyone else.

How does it work?

Bubble sort uses the idea of “swapping” elements depending on predefined conditions until the collection is completely sorted.

Let’s first take a look at how to “swap” elements first:

//ES5
function swap(arr, idx1, idx2) { 
    let temp = arr[idx1]; 
    arr[idx1] = arr[idx2];
    arr[idx2] = temp; 
}
//ES2015
// const swap = (arr, idx1, idx2) => { 
//     [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]; 
// }

The way swap() is written here is more readable than the next type, although I like the second one slightly more. swap() takes an arr and two separate indexes as parameters. When executed, it used those parameters to access the array and “swap” the two elements in question by setting one to the other.

//ES2015
// const swap = (arr, idx1, idx2) => { 
//     [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]; 
// }

On the other hand, this version of swap() does the same but with ES2015 syntax.

But How About, You Know, Actually Bubble Sorting?

Say we have an array:

[37, 45, 29, 8]

How would we sort it? Well, let’s figure out some bubbleSort() pseudocode in order to guide us:

1. Start looping from a variable called i the end of the array towards the beginning.
2. Start an inner loop with a variable called j from the beginning until i — 1
3. If arr[j] is greater than arr[j+1], swap those two values
4. Return the sorted array

function bubbleSort(arr) {
     for (let i = arr.length; i > 0; i--) { 
             for (let j = 0; j < i - 1; j++) { 
                 if (arr[j] > arr[j + 1]) {
                      swap(arr, j, j + 1)
                
                 }
             }
         }
     return arr
}

Bubble Sort uses two loops: the outer for loop loops over the array from the end to the beginning while the inner loop does the opposite.

The inner loop compares an element, say at index 0, with the element directly next to it. (This is why the arr[j+1] is used.) If arr[j] is greater than arr[j+1], we swap them. If not, we move down the loop.

By the end, the array is sorted! Good stuff!