Algorithms: Insertion Sort
Welcome to the first post on Software Engineering 101, where I aim to post weekly(ish) deep-dive articles on algorithms, design patterns, data structures and more!
This week we’ll be taking a look at the Insertion Sort algorithm.
Insertion Sort is an algorithm used to sort a given list of items. It does so by iterating through the list and building the sorted output one item at a time. Upon each iteration, an item is taken from the list and inserted into the correct position by comparison with its neighbours. This process is repeated until we reach the last item and there are no more left to be sorted.
Let’s begin by taking a look at some of it’s advantages:
- It’s a simple algorithm to implement
- Performance is very high when operating with small lists
- Even more so when the list is already mostly sorted, as fewer iterations of the sorting logic need to take place
However, the algorithm does hold some disadvantages:
- Performance suffers when large lists are used, as this could involve carrying out a lot of comparisons and shifting of array items
- The algorithm doesn’t perform as well as the merge sort and quick sort algorithms, both of which we’ll look at soon
So now we know what the algorithm does, we should declare exactly what it does in the form of pseudocode to help aid understanding and communicate the process carried out to sort our list. For insertion sort this is fairly simple, so let’s take a quick look at one of the ways in which we could approach it:
Pretty straightforward, eh? There’s not a huge amount going on here, but it’s important to understand the purpose of each line:
- We begin by declaring the for loop for the algorithm, we’re going to loop through the entire length of our input array. We start from the second item in our array as the first item has nothing to the left to compare it to.
- We set the current item which is to be sorted (key) equal to the current item at our iteration position.
- We declare the variable i which we use to reference the position before the current iteration, i.e to the left of it.
- If necessary, then this step is where we start sorting the current item. We begin by checking that our i index from step 3 is at least the first item in the list (> position 0) and that the value in our A array at this index i is greater than our key value from step 2.
- Whilst the above step holds true, the item at A[i] (the item to the left of our current iteration) becomes the value set at the current iteration A[i + 1] — which is equal to A[j]. This is because this value is greater than the value currently at A[i + 1], so it should be put in it’s place instead.
- At this step in our whilst loop, we move another step to the left in our array by decrementing our i value.
- We reach the end of our whilst statement when the conditions are no longer satisfied. This is if both the i value reaches zero or the value at A[i] is not greater than the key value.
- We then finish this iteration by inserting our key value into it’s position in the array. Whenever the whilst loop exited at step 6, our i variable was set to the next index (to the left) in our input array. If the loop exited because the value here was less than our key value, then the key value is insert to the right of that at [i + 1], yet before the item that was inserted at step 5 before i was decremented. If the loop exited due to i reaching zero, then our key value is simply inserted at the beginning of our array.
If you’ve got that, great! It’ll help to run through an example so we can really nail what’s going on. If you didn’t follow, try going through it again and return to this section after!
So, let’s start by declaring an array which we want to sort:
Now we’re ready to go, we begin at the very first line of the pseudo code. Our input array contains 4 elements, so we’re going to be looping:
Great, so we’re only going to be iterating 3 times and our array will be sorted. The first time round, where j = 2, looks like so:
- To begin with, we assign our key to the value at A[j], which is A at this iteration. This is the second value in our array, which is 3.
- Our i variable is set to the value of the position to the left of A.
- We now reach the while loop. Currently, i > 0 and A[i] is greater than the key value. A[i] is the value to the left of the key item in our array, so here 5 > 3 meaning that our while loop conditions are satisfied.
- Because of this, we enter the loop and place the value of A[i] one place to the right at A[i +1] - this is because A[i] is greater than the current value at that position.
- We now decrement i, which at this point becomes 0.
- Because i has reach 0 it means there’s no more items left to compare the key value to, so we exit the loop.
- The value at position A[i + 1] is set to the value of out key. This is because the while loop exits either when when i = 0 or where A[i] <= key (which is when the value to the left of our key value is not greater than the key value).
Our j = 2 iteration has completed! Our array now looks like:
Great, so we’ve completed the first step in sorting our array. We now move to the next iteration, where j = 3:
- At this point our key now becomes the value at A, which is equal to 1.
- Our i variable is set to the position to the left of A.
- Now we reach the while loop, which is satisfied as A[i] (currently equal to 5) is great than our key value, 1.
- Because of this, we shift our value at A (5) to the position A.
- Next, we decrement i, where it becomes 1, as we want to check the next item to the left in our array.
- Now, our while loop enters the next iteration as i is still > 0 and the value at A (3) is greater than our key value. Because of this, we shift the value at A (3) to the position A.
- We again decrement i, as if there is still a value to the left then we need to compare our key value to the value at this position
- However, i is now equal to 0 so our loop conditions are now invalid - meaning our loop exits here.
- Because we’ve reach the end of our array, the value at A becomes our key value of 1.
So now our array looks like so:
Looks like the array is sorted and we’re only on our third iteration! However, we weren’t to know this so we still need to enter the final iteration where j=4:
- At this point our key now becomes the value at A, which is equal to 9.
- Our i value is again set the position to the left of this in our array.
- The while loop conditions are not satisfied this time round, this is because the value to the left of our key in the array (A = 5) is less than our key value at A.
- Because of this, the while loop is not entered.
- At this point, the value at A[i + 1] is set to the value of our key - meaning the value at A remains unchanged in value.
Looks like we did it! Did you manage to follow that? If so, you would have noticed that:
- We started from the second item in our array (3) and compared it to the item to the left of it (5). Because 3 < 5, we shifted 5 to the right and as we reached the position at the start of the array, we put 3 in 5’s previous position because there was nothing left to sort at this stage.
- Next we moved to the third item of the array, which was the value of 1. We begin by entering the while loop and comparing it to the item to the left of it (5), because 5 > 1 we again moved the value of 5 one position to the right. Because 5 was at the second position in our array, we still had the first position in the array to compare the key value of 1 with. Because of this we then enter the next iteration of the while loop and as 3 > 1, we place the value of 3 at the second position of our array - this is where the while loop exists because again and we place the value of 1 as the first item in our array as there’s nothing left to compare.
- Finally, we reach the last item of the array with the value of 9. At this point, all the items to the left of this position have been sorted - so if 9 is greater than the value at the position to the left of it, then our array is sorted. Because this is the case, we don’t enter the while loop and the value at A remains set as 9.
Now we know how our Insertion Sort algorithm works , we need to understand how efficient the algorithm is and to do this, we have to calculate it’s running time. This process is done by taking a look at each step of the algorithm at calculating it’s ‘cost’ — which is how expensive the operation is in terms of time.
- The first cost is length of our input array, A.length which is equal to n. This is because the loop is going to be iterated n number of times.
- Because we don’t carry out the operation on the first item in the array (as there’s nothing to the left index of it to compare it to), step two is carried out for all the items in the array but one. This means the cost here is equal to n - 1.
- The same facts apply for step 3 as step 2, also making the cost n - 1.
- For iterations between j = 2 to n, we let tj represent the number of times in which the whilst loop is executed for that value of j. In step 4, this will always execute one more time than the body when the whilst loop exits in a normal way. This is because the i > 0 and A[i] > key statements need to be checked to determine whether to enter the loop or not.
- As stated in Step 4, the body of the whilst loop will execute one time less than the header. If the test of the header fails then the body of the loop is not reached, making the value of tj equal to tj - 1.
- The same cost for step 5 applies here.
- No cost.
- This step holds the same facts as step 2 + 3, so the cost here is also n - 1.
- No cost.
We now have the cost of each operation, but this isn’t too much use to us yet. So in order to calculate the running time, we need to sum all of these values from the cost column which gives us:
So that gives us the average case complexity for our algorithm of:
But what about the best case for our algorithm? This is the situation that occurs when say the input array is already sorted. The steps in the algorithm will still be executed, but the while loop that does the sorting will not be entered - which reduces the complexity greatly. because of this, the algorithm is simplified which is reflected in the equation below:
After simplifying our equation in the second step, this can be expressed as:
Following the rules of Big-O, we can remove the constants which gives our algorithm a best case time complexity of:
And finally, the worst case for our algorithm occurs when the input array is in the complete opposite order from what we want it to be for being sorted. So in our case, our example array would be equal to A= [9, 5, 3, 1] - which is in decreasing order. The equation for this would look like so:
This is because the entire algorithm, including the for loop, would need to be executed for every single iteration as each item in the array needs to be checked and sorted. We took three steps to simply this equation, with the final step being able to be expressed as:
We can again remove the constants from this expression, which gives use a worst case time complexity of:
As well as time, we should take a look at the memory (or space) that is required by the insertion sort algorithm.
Our Algorithm solution noted throughout this article does not create any additional arrays during it’s operation - it rearranges the input array, meaning that no additional space in memory is needed to account for this. Because the lines through 1. to 9. of our pseudocode are all executed in constant time (either declaring loops or assigning values to variables / array positions), even though each of these calls are added to the stack the algorithm itself only takes O(1) of space as these calls do not exist simultaneously.
And that’s it!
We’ve learnt what the insertion sort algorithm is, it’s strengths / weaknesses and how to implement it. Whether you’re learning from scratch or refreshing your algorithm knowledge, I hope this deep-dive has been a good companion in understanding how the algorithm works.
If you have any questions, feel free to leave a response or drop me a tweet!
The latest Tweets from Joe Birch (@hitherejoe). Android, photography, bass and a lot of running. Android Developer…twitter.com
Check out more of my projects at hitherejoe.com