Annotated Algorithms: Bubble Sort, Insertion Sort, and Selection Sort

8 min readOct 28, 2020

We’ll be doing a step-by-step breakdown of three famous sorting algorithms. While they aren’t the most optimal sorting algorithms regarding time complexity, understanding how they work can help tremendously with mastering common problem-solving techniques such as sliding-windows and multiple pointers.

Before go into each specific algorithm, let’s first go over the two things that all three of them will share in common.

Commonality one: Sorting an array in place

Take a look at the reverseArray function below:

This function takes in an array as an argument, initializes an empty newArray and iterates backwards over the argument array by using a for loop. As it iterates, the function looks at each number in the argument array, pushes it into the newArray, and then returns the newArray as a result.

While this is a valid way to reverse an array, its space complexity is not great since we need to allocate additional memory in order to store the newArray.

What if instead of creating a newArray to store the reversed order of our numbers, we could just swap the numbers two at a time like this:

By swapping the numbers in the array in place, meaning without creating an additional array, we improve our space complexity.

Commonality two: The “swap” helper function

Now that we understand the need for a swap function, we can discuss the two purposes it intends to serve: it helps us separate our concerns by abstracting away the swapping functionality and also allows us to sort our arrays in place. The function takes in two indices and an array as arguments, then uses the indices to grab two different elements and swap their places within the array.

Both of the above functions work, but the bottom one works more optimally since the swapping is done… *inhales* … say it with me now… in place.

Bubble Sort

Bubble Sort, while being a pretty slow sorting algorithm, is pretty simple to understand and is a perfect way to introduce the swap function in practice.

We start with a for loop, iterating over every number in our array. We know we’ll eventually be returning the array after it has been sorted, so let’s add the array to our return statement.

Next, we have to emulate the bubble in Bubble Sort. This bubble is just a small slice of the array that looks at two adjacent numbers: the number at index i and the number at index i + 1

While we can sort an array in a variety of ways, most of the time the default is sorting an array in ascending order; meaning that larger numbers will go on the right and smaller numbers will go on the left.

We only ask ourselves one question within each bubble: is the number on the left ( index i ) greater than the number on the right ( index i + 1 )?

If the number on the right is smaller, we swap the two numbers in place.

Otherwise, the bubble continues to slide to the right and compare more numbers

Now that we can wrap our minds around the bubble idea, how can we represent this bubble comparison in code? First, remember we need to check if the number at index i is greater than the number at index i + 1. If this conditional is true, we will want to swap the two numbers.

How do we swap the two numbers? Let’s borrow from the swap function that we built earlier. The swap function takes in the two indices and the array itself as arguments and uses the indices to define the swap.

This makes up the main bulk of our logic, but there are some edge-case questions we have to address.

As it stands now, nothing is stopping our algorithm from going all the way to the very last number and then comparing the last number to a blank space on the right of the array.

To fix this problem, we tell the for loop to stop at the second-to-last index. This way, there’s always a number at index i + 1 for us to compare.

Another issue is that our for loop only iterates over the array once. It’s pretty uncommon for the array to be sorted after only one iteration of the for loop, as you can see here:

We tell the for loop to repeat itself as many times as needed by wrapping it inside of a while loop and giving it a conditional to work with.

First we declare a variable isSorted and initialize it to be false since our array is initially unsorted.

We need a conditional that returns true to get inside of our while loop, so we use the bang ( ! ) operator to reverse the truthiness of the isSorted variable.

If we are able to get inside of our conditional statement on line 7, that means we found two numbers that needed to be swapped and can safely assume that the array is still unsorted. We let the program know this, you’ll see why in a moment.

You might have noticed that this code locks us into an infinite loop because we have no way of getting ( !isSorted ) on line 5 to evaluate to false and break.

How do we know we’re done sorting? We go through an entire iteration of the for loop without needing to swap any numbers. What happens when we don’t have to swap any numbers? We never tell the program to change isSorted to be false on line 9 above.

Knowing this, we can change isSorted to be true once we get inside of the while loop.

If numbers need to be swapped that round, isSorted changes to false.

If we don’t have any numbers to swap, isSorted remains true, !isSorted evaluates to false, we break out of the while loop, and return the sorted array.

Our bubble sort algorithm now works without any problems, but there is still one more way we can optimize it.

By adding a counter variable to keep track of how many times we have completed a round of our for loop, we take advantage of knowing that at least one more number on the right side of the array will wind up in its final sorted position after running the for loop.

Put another way, we avoid having to look at numbers that we already know have been sorted.

Insertion Sort

Similarly to Bubble Sort, Insertion Sort moves slowly compared to other major sorting algorithms, but we can still use it to learn about and leverage multiple pointers.

One important thing to notice is that our for loop index starts at i = 1 and continues up to the last element of the array ( array.length ), as opposed to starting at i = 0 and continuing to the second-to-last element in the array ( array.length - 1 ). Why is this?

In Bubble Sort, we were comparing numbers to the number on the right ( i+ 1 ) whereas in Insertion Sort, we will be comparing each number to the numbers on the left.

As we iterate over our array, our goal is to take whatever number is at index i, look over all of the numbers to the left of index i, and insert the number in its proper position. Take the gif below as an example.

At index 7, we identify the number 6 and then move 6 to the left by swapping numbers until we reach a number smaller than 6 — in this case the 5 at index 3. A byproduct of the way insertion sort works is that all numbers to the left of index i wind up in sorted order as we continue to iterate over the array.

We move the number to its properly sorted position is by using another loop inside our initial for loop. We could use another for loop, but this would force our algorithm to continue sorting numbers even beyond when we’ve placed our number in the correct position.

Instead of a for loop, let’s use a while loop instead and give it some conditionals to pass. We want our algorithm to continue to move the number at index i to the left until:

The next number to the left ( j - 1 ) is smaller than the number we’re moving
We’ve reached the end of the array, or index 0

These two conditionals are accounted for in the while loop in the code below.

By declaring j as its own variable on line 3, we give ourselves more control of our flow once we’ve met the conditionals we’re looking for. The only catch is that we have to manually decrement j as we iterate to the left, which is addressed on line 6.

Selection Sort

Coming up…