Insertion Sort

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.

Insertion sort works similarly as we sort cards in our hand in a card game.

We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in their right place.

A similar approach is used by insertion sort.

Working

In each iteration, it compares the current element with the values in the sorted array. If the current element is greater than the element in the array, then it leaves the element and iterates to the next array element. Otherwise, if the current element is smaller than the array element then it moves the rest of the element in the array by one position and makes space for the current in the sorted array.

This is how Insertion sort takes one input elements at a time, iterates through the sorted sub-array and with each iteration it inserts one element at its correct position. This is why the algorithm is known as Insertion sort.

As the average & worst-case complexity of this algorithm are O(n2), where n is the number of elements, Insertion sort is not good for large data sets.

Algorithm

The simple steps of achieving the insertion sort are listed as follows -

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step 2 - Pick the next element, and store it separately in a key.
Step 3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then move to the next element. Else, shift greater elements in the array towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.

Program using C

//INSERTION SORT
#include <stdio.h>  
  
    void insert(int a[], int n) /* function to sort an aay with insertion sort */  
    {  
        int i, j, temp;  
        for (i = 1; i < n; i++) {  
            temp = a[i];  
            j = i - 1;  
      
            while(j>=0 && temp <= a[j])  /* Move the elements greater than temp to one position ahead from their current position*/  
            {    
                a[j+1] = a[j];     
                j = j-1;    
            }    
            a[j+1] = temp;    
        }  
    }  
      
    void printArr(int a[], int n) /* function to print the array */  
    {  
        int i;  
        for (i = 0; i < n; i++)  
            printf("%d ", a[i]);  
    }  
      
    int main()  
    {  
        int a[] = { 12, 31, 25, 8, 32, 17 };  
        int n = sizeof(a) / sizeof(a[0]);  
        printf("Before sorting array elements are - \n");  
        printArr(a, n);  
        insert(a, n);  
        printf("\nAfter sorting array elements are - \n");    
        printArr(a, n);  
      
        return 0;  
    }