Insertion Sort

Insertion sort is a simple and it is type of comparison sort.its performance is very good and efficient. In this algorithm,initially we select two element and swap them if required ,the increase the data slide and perform swapping till array is sorted.

• This algorithm is very efficient for small data sets(due to its low overhead).
• Insertion is adaptive in nature means if some element of array is already sorted the complexity will be O(n+d) where d=number of inversion.
• Insertion sort is also a type of In-place type algorithm.
• It is also stable algorithm.
• Insertion sort is used when data list is nearly sorted(due to its adaptiveness)

Explanation of Insertion Sort by Example

In Above Figure, we select data slide of two element and perform Swapping Operation if required, and again increase the data slide and apply swapping operation till n-1.

Animation of Insertion Sort

Flow Chart of Insertion Sort

Code Implementation

#include <stdio.h>
int main()
{
    int A[]={0,5,2,1,8,4};
    int n=sizeof(A)/sizeof(A[0]);
    //Start the Insertion Sort Logic
    int i, PickElemet, j;  
    for (i = 1; i < n; i++)  // Increase the Data Slide
    {  
        PickElemet = A[i];  
        j = i - 1;  
        while (j >= 0 && A[j] > PickElemet) // Inside the slide perform Swapping
        {  
            A[j + 1] = A[j];  
            j = j - 1;  
        }  
        A[j + 1] = PickElemet;  
    }  
    //End the Insertion Sort Logic
    for(int i=0;i<n;i++)
    {
        printf("%d\n",A[i]);
    }
    return 0;
}

Time & Space Complexity

Worst case complexity : O(n^{2})
Best case complexity : O(n^{2})
Average Case complexity : O(n).
Space Complexity : O(n^{2})