Insertion Sort in C

In this article, we will discuss the Insertion sort Algorithm. The working procedure of insertion sort is also simple. This article will be very helpful and interesting to students as they might face insertion sort as a question in their academics.

Insertion Sort can be explained by the card game that we have played. It is assume that the first card is already sorted in the card game, and then we select an unsorted card. if the selected unsorted card is greater than the first card, it will be placed on the left side. This same process is applied in Insertion Sort. So in simple terms.

Insertion Sort is the simple sorting algorithm that virtually splits the given array into sorted and unsorted parts.

Working of Insertion Sort Algorithm

Now let' see the working of Insertion Sort Algorithm.

To understand the working let us take an unsorted array(unsorted array means the data present in the array is in jumbled order that is neither in ascending order nor descending)and start sorting it using Insertion Sort Algorithm.

Lets start by taking the array elements.

In fig 1: 1st element is not at its correct position so we have to sort it. Insertion Sort starts with a key element (key is a variable where element is stored). Key element starts from array index 1. Here 15 is our key element.

We have to Compare key with the first element.

In fig 1 the first element is greater than key, so key should be placed in front of the first element.

We cannot directly place key element on the first position

We have to shift all the greater element in the array by one position towards right. (Here in fig 1 19 will be shifted.)

Then our key element will be placed at its correct position.

So lets insert it.

Now key element will be index 2.

In fig 3 the second element is greater than key as well as the first element, so key should be placed in front of the first element.

We have to shift all the greater element in the array by one position towards right. (Here in fig 3 19 wil be shifted then 15.)

How the shifting will be done let's have a look.

If your are getting the idea how Insertion sort works then Let's proceed towards sorting the rest of the array.

Now key element will be index 3.

In fig 5 the third element is greater than key as well as the second element, so key should be placed in front of the Second element.

We have to shift all the greater element in the array by one position towards right. (Here in fig 5 19 wil be shifted then 15.)

How the shifting will be done let's have a look.

Now key element will be index 4.

In fig 7 the forth element is greater than key as well as the third element, so key should be placed in front of the third element.

We have to shift all the greater element in the array by one position towards right. (Here in fig 7 19 wil be shifted then 15.)

How the shifting will be done let's have a look.

Hence our array is sorted. So full process of sorting using selection sort is represented in the below figure.

Just have a look

As we have learned the working of Insertion Sort Lets proceed towards the Pseudo Code.

Pseudo Code Of Insertion Sort

We are moving towards the Algorithm of Insertion Sort.

Algorithm of Insertion Sort

Insertion Sort Program in C

Time Complexity

Now let's see the Time complexity of Insertion Sort in Best case, worst case, Average case. We will also be learning about space complexity.

Best Case: In Insertion Sort best case occur when the array is already sorted.

Worst Case: Worst Case occurs when we have to sort the array elements in ascending order, but its elements are in descending order.

Average Case: Average Case of Insertion Sort occurs when the element are in jumbled order i.e. neither in ascending nor in descending order.

Space Complexity

Advantage of Insertion Sort

• Insertion sort is very efficient in case of small number of elements.

• Implementation of Insertion Sort is very easy as compared to toher sorting algorithms

• Insertion Sort is a stable sorting technique i.e. the order of key is maintained.

Disadvantage of Insertion Sort

• Insertion Sort takes larger time if more number of elements are present in the array.

• Major disadvantage is its average time complexity i.e. O(n^2)

• It is not as quick as merge sort or quick sort

When to use Insertion Sort

• It is used when the array contains small number of elements.

• When there are only few elements left to be sorted

Conclusion

So far our Insertion Sort article comes to an end but before ending we just conclude what are the things that we have learned today.

To conclude, it can be said that

• Insertion Sort algorithm one of the simplest algorithm with simple implementation

• It is efficient for small data values

• Insertion Sort is adaptive in nature i.e. it is appropriate for data sets which are already partially sorted

Main Banner Image Credit: Skolo Online Learning