Insertion Sort Algorithm

After going through the basics of Algorithm let us try to understand a basic sorting Algorithm that is called Insertion Sort. It solves the problem of sorting of a sequence of numbers.

Input - a1,a2,a3,...,aN Output - a1',a2',a3',...,aN'

Such that a1'<=a2'<=a3'...<=aN'

The numbers that we wish to sort over here are called Keys. Insertion Sort Algorithm is an efficient algorithm for sorting a small number of elements. It is an In Place Sorting Algorithm which means that the numbers are arranged within the array with at most constant number of them stored outside the array at any time.

You can think of Insertion Sort as arranging or sorting a deck of cards placed in a table such that we pick the card one by one and place it in the correct position in the left hand. The card in the left are all always sorted. The card picked from the table is compared with each of the sorted sequence of cards and it is placed accordingly.

Insertion Sort Algorithm gives the best result when the cards placed on the table are already sorted. It gives the worst performance when the cards on the table are reverse sorted.

Insertion Sort Procedure - INSERTION-SORT Parameter -> An array A[1,...,N] containing a sequence of length N that is to be sorted.

INSERTION-SORT(A)

Step 1 for j=2 to A.length
Step 2 key = A[j]
Step 3 //Insert A[j] into the sorted sequence A[1,...,j-1]
Step 4 i = j - 1
Step 5 while i > 0 and A[i] > key
Step 6 A[i+1] = A[i]
Step 7 i = i - 1
Step 8 A[i+1] = key

Let us go through each of the above mentioned steps one by one.

Step 1 : We are initializing the variable j = 2 which means we are starting the outer for loop with the second element present in the input sequence. I am saying second element and not the third element since the array indexing is starting from 1 which might seem confusing to people who are habituated of starting the index of the array from zero like it is done in most of the programming languages. Also we are interested in the second element in the array since the first element being the only element in the array is already sorted.

Step 2 : Here we are just initializing the key variable to be the second element as this is the element which we have to position in the sorted array. This element can either be positioned at the first position or the second position depending on whether this key element is less than or greater than the first element or the only sorted element of the array. Step 3 : This line just represents the comment.

Step 4 : Initialization of the counter or the loop variable i = j - 1 to keep the track of the comparison to be made for the key element with the already sorted element in the array. Please note that all the key element is the element that needs to be placed/positioned in the already sorted sequence and all the elements prior to and on the left side of the key is the sorted sequence.

Step 5 : Checking the entry criteria for the inner loop. The entry criteria to enter the inner loop is valid until we have reached the first element of the sorted sequence and the element at that position is greater than the key element. If the key element is less than the element of the sorted sequence it simply means that the key is at the right position and its time to pick the next element as the key element. Step 6 : Here we are shifting the current element A[i] to the right since in the entry of the loop we found that the current element A[i] is greater than the key element and in order to accommodate the key element in the correct position we need to position the elements greater than that to the right one by one.

Step 7 : Decrementing the inner loop variable so that we compare the key element with all the elements to the left in the already sorted sequence and not just the immediate left element.

Step 8 : This step positions the key element to the correct position in the sorted sequence.

The above mentioned steps are repeated until we traverse to the end of the array i.e the last element to give us the output which is a sorted sequence of the provided inputs.

Conclusion

We have covered the following in this post -

1. What is an Insertion Sort Algorithm ?
2. Pseudocode for Insertion Sort Algorithm
3. Understanding of the pseudocode code of the Insertion Sort Algorithm step by step

Book for Reference

Introduction to Algorithm

Please share the post by clicking the social media icons at the beginning of the post.
Thank you for reading and see you in the next post !👋