Insertion sort Algorithm explained

Sorting algorithms are pretty much the very foundation when comes to learning algorithms. So far we have seen tutorials on

– What is Algorithm ans why it is used ?
– Bubble Sort Algorithm
– Selection sort Algorithm

Along with these tutorials we also saw few exercises based on these to try out with programming language of your desire. In this tutorial we are gonna explain about Insertion sort Algorithm, how to use them and it’s advantages and disadvantages.

Insertion sort Algorithm:

As the name implies this algorithm works by inserting the numbers by comparing two values at a time and then arrange them in sequence we want it to be. In a given array of numbers this Algorithm considers a value as sorted. It then picks the nearest value of already sorted value and compares them. If the current picked value meets the sort criteria ( depends on the type of sort you want to perform ) then value which is considered as already sorted swaps with the current value. Now both the values are considered as sorted. The Algorithm then picks the next value and compares it with already sorted values and swaps its position depending on the sorting criteria.

Explanation:

Consider the following values in an array and we are going to sort this in Ascending order with the help of Insertion sort algorithm.

Circuits Library - 220+ practical circuits

The leftmost value 43 is considered to be fully sorted.

Next to fully sorted value 43 lies 15. Now 15 is compared with 43 to see which one is greater.

15 is less than 43 so its moved to the leftmost position of the array.

Now both 15 and 43 is considered to be fully sorted.

Now the third value 5 is taken out and compared with already sorted neighbor 43.

5 is smaller than 43, therefore the positions are swapped.

Now 5 is again compared with its already sorted neighbor 15.

Since 5 is small compared to 15 its positions are swapped. Now 5, 15 and 43 are considered to be fully sorted.

Now the next unsorted value 25 is compared with 43.

Since 25 is smaller than 43 its positions are swapped. And 25 is again compared with already sorted value 15.

15 is smaller than 25 so the position of 25 is retained and algorithm inserts it in 3rd position of the array.

And now the last value 7 is compared against 43 first and swaps position with it. It then goes on to compare with 25, 15 and 5. Since 7 is smaller than 25 and 15 it moves three positions to the left and takes the second spot in the array.

Now entire array is fully sorted.

How to implement Insertion sort Algorithm:

Taking the above example, here is the actual algorithm that you need to implement in your code to sort the array in ascending order.

Consider the leftmost value ( 0th position ) in the array as completely sorted.
Compare value in the 1st position to the value in 0th position.
If the value in 1st position is smaller than value in 0th position swap the positions.
Now move towards the next value ( 2nd position ) and compare them with values in 1st and 0th positions.
Swap the positions of values in the array if values in the Right hand side is smaller than values in left.
Repeat this until you reach the end of array.
Now your array is sorted in ascending order.

Code:

#include <stdio.h>

int main()
{
    int i,j,temp;
    int numbers[5]={43,15,5,25,27};    //Number sequence
    for(i=1;i<=4;i++)
    {
    for(j=i;j>0;j--)
     {
        if(numbers[j]<numbers[j-1])
            {
                temp=numbers[j];
                numbers[j]=numbers[j-1];
                numbers[j-1]=temp;

            }
     }
    }
    printf("The sorted sequence is\n");
    for(i=0;i<=4;i++)
    {
        printf("%d\n",numbers[i]);
    }
    return 0;
}

Where to use Insertion sort Algorithm:

This type of sorting algorithm works best with small data however bigger the data gets worse it performs. Although its lot efficient than selection sort and bubble sort since the number of steps it take for sorting data is significantly less. Also it offers stable results even with repetitive data sets.

Activity:

For better understanding of this sorting algorithm better, try the below exercise.

Write code for user to accept 10 numbers and then sort them in descending order.

I believe this Algorithm tutorial will help you understand Insertion sorting better. Do try this activity and share your code in the below comment box. Also do share your feedback, queries and thoughts about this Algorithm series. It will help me to improvise this Algorithm tutorial series better. Happy coding 🙂