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

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, ** push**es it into the

**newArray**, and then

**the**

*returns***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

**, meaning**

*in place**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

**. The function takes in**

*in place***two indices**and an

**array**as arguments, then uses the

**indices**to grab two different elements and

**their places within the array.**

*swap*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

**statement.**

*return*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** )

**than**

*greater***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

**is**

*i***the number at index**

*greater than***. If this conditional is true, we will want to swap the two numbers.**

*i + 1*How do we swap the two numbers? Let’s borrow from the ** swap function** that we built earlier. The

**takes in the two indices and the array itself as arguments and uses the indices to define the swap.**

*swap function*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

**for us to compare.**

*i + 1*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.

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

**statement.**

*return*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

**and continuing to the**

*i = 0***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

**the number in its proper position. Take the gif below as an example.**

*insert*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
is smaller than the number we’re moving*left ( j - 1 )* - 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

**as we iterate to the left, which is addressed on line 6.**

*j*# Selection Sort

*Coming up…*