Insertion Sort algorithm in depth with C++

We can visualize an example of the Insertion Sort algorithm with an array of integers that needs to be sorted.

In this case we will set the start position as the blue arrow that is located at index 1. Where we will compare 3 < 7. If this is true, then we will have to swap these with eachother. Now, this is true for 3 < 7 so we will swap

From there we will mark the left side (The area that is colored green) as sorted. Next we will select index 2, marking integer 1 with the blue arrow. Where we will have to check if 1 is less than anything that is already marked as sorted. In this case we will get that 1 < 7 is true, so we will swap. We will also have to check again to see if 1 < 3 is true, and likewise have to swap these two. Our array will then be seen as.

Now having the blue arrow at index 3 we will check wether 2 < 7. This is true, so we will swap these.

Right after this we will see that 2 < 3 will equal as true, so we will swap these.

Since 2 < 1 is false we can say us done with the integer 2. Which means that we can then begin at index 4 with the integer 4. After repeating the process above we will land on 4 being between 3 and 7.

Now that there's only one integer left to compare with, namely 6 at index 5. We will have to do the same process to get our sorted list. In this case we will only have to move 6 one step.

The algorithm is done and we have our sorted list. However, we've up untill now only done everything manually and visually. So let's move onto the C++ code for this algorithm.

void insertionSort(int arr[], int len){

       for (int i = 1; i < len; i++){

             int key = arr[i];

             int j = i - 1;

             while (j >= 0 && arr[j] > key){

                    arr[j + 1] = arr[j];

                    j = j - 1;

             }

             arr[j + 1] = key;

       }

}

Here you will see that the function for Insertion Sort takes two parameters, an int array and an int len. The int array will be the array that needs to be sorted, and the int len will be the length of the array. We can imagine that we're bringing the same array we worked with above into the function.

First thing we'll see within the function is a i-for-loop, that goes from 1 and all the way up to the length of the array. The representation of this can visually be seen as.

We also have two more variables key and j, and a while-loop that stays true if j >= 0 and arr[ j ] > key. Let's dive a little deeper into that while-loop.

while (j >= 0 && arr[j] > key){

       arr[j + 1] = arr[j];

       j = j - 1;

}

arr[j + 1] = key;

Here we can see that j >= 0 will be true for the first round, since j = 0. Simultaneously, we will need arr[ j ] > key to stay true. But in this case that'll be false, because 7 > 8 is false. In other words, we will not move into the while-loop for the first round. Which leaves an opportunity to look closer at the arr[ j + 1] = key outside the loop.

Since arr[j + 1] is outside the while-loop it'll be triggered for every round the i-for-loop finishes, regardless of whether we've been inside the while-loop or not. In this case arr[j + 1] will be equal to that on index 1, namely the integer 8. Which is also what key was initially set as. So even though we're overwriting key, we're actually not changing key unless we've been inside the while-loop. Moving onto the next round, with i = 2.

Let's look closer at the while-loop now that it will trigger. Because in this case, j >= 0 and arr[ j ] > key will both be true. Where j = 1 and arr[ j ] > key will be 8 > 5. Let's focus on what happens inside the loop.

arr[j + 1] = arr[j];

j = j - 1;

In this snippet, arr[j + 1] = arr[ j ] will be setting the integer 8 to index 2. Replacing the integer 5. Which will make the array look like.

However, the integer 5 is not gone, because we have it saved as an extern variable called key. Since the next thing that will happen in the loop is j = j - 1, we will get j = 0. Which means that arr[ j ] will equal 7. That also means that we will have another round inside the while-loop, since j  = 0 for j >= 0 and arr[ j ] > key will be 7 > 5.

In this case index 1 being 8 will be swapped with 7. with j also being j = j - 1 = -1, which will break the while-loop after this. This is what we want. Because after the loop we'll set arr[j + 1] = key and get index 0  (7) to be set to key (5). The array will then be seen as.

In order to get a fully sorted array we can repeat this process. For the next round, i will be i = 3. But I will end the post here instead of repeating the steps for the last few integers.