Insertion Sort Algorithm
As more and more companies asked questions related to Data Structures and Algorithms. So learning Insertion Sort is helpful in coding interviews.
Lets get started.
You have an Array and it consists of 5 items, from 0 to 4. Each item represents one card. And these items have assigned values in it. Which is:
8, 2, 4, 1, 3
Imagine you are playing a card game.
The dealer gives you one card at a time. Your task is to insert each card in its right position.
First you get card of 8, you keep it as it is. Then you get 2 and inserted before 8. Then you get 4 which you inserted between 2 and 8. You get 1 which you inserted at the start of all the items. Finally you get card 3, which you insert after 2 and before 4 which lies in the middle of the Array.
Your final list is:
1, 2, 3, 4, 8
So in this way items are inserted at correct position in ascending order, that’s why this is known as insertion sort algorithm.
Let’s solve this algorithm step by step.
As we have an Array of 5 items.
8, 2, 4, 1, 3
First we have given 8 so we assume that 8 in it’s right location.
8, 2, 4, 1, 3
Next we have 2. Now we have to look at all the items that we have sorted before. And this include only 8. If 8 is greater then 2 it will be moved to the right side of 2, otherwise remain to the left side. As 8 is bigger so we should shift it into right side.
To move 8 to the right, first we store 2 in a separate variable called current.
current = 2
After doing this, we can shift 8 to the right as the item 2 is now empty. Now we can move 2 to item 0 as it gets empty after moving 8 to the right.
The item 0 and 1 are sorted while others are unsorted yet. The new list is then:
2, 8, 4, 1, 3
In every step, we pick the item from an unsorted part and inserted in the correct position in the sorted part.
Next we have 4. First store item 4 in a separate variable current.
current = 4
Now look at all the sorted items and move items to the right place which are smaller then 8. In this case only 8 is greater then 4, so move it to the right side. So now we can insert 4 in it’s correct position.
Now, we have this list:
2, 4, 8, 1, 3
Next we have one 1. First store item 1 in a separate variable current.
current = 1
Again Look at all the sorted items. Items which are greater then 1 will move to the right place. As one is the smallest value so, all the items now move one place to the right. 1 is now inserted to the first place as it is the smallest item in the list.
The new list is:
1, 2, 4, 8, 3
Next we have one 1. First store item 3 in a separate variable current.
current = 3
Finally we have 3. So shift all items to the right side which are greater then 3. In this case 4 and 8 are greater then 3 so they will move to the right while 1 and 2 should remain at it’s place as they are already smaller then 3.
1, 2, 3, 4, 8
Now are Array is fully sorted.
Time Complexity
The time complexity of this algorithm give.
In the best case scenario, if the array is sorted the current item is already in the correct position. We don’t need to shift any item.
For best case scenario time complexity is: O(n), linear.
In the worst case scenario, where the array is sorted in descending order. We need to shift all the items we have seen to the right because the current items is smaller then all those items.
For worst case scenario the time complexity is: O(n²), quadratic.
Reference for this article:
