Insertion sort in C

Consider first element of the array as sorted then loop through remaining elements and perform insertion like inserting an element is done in a sorted array.

Important points

  • Assume first element to be sorted. Then take each of remaining element and insert in that sorted array.
  • Time complexity is of O(n^2).
  • Insertion sort is more beneficial in linked lists as there is no need of swapping.
  • Adaptive
  • Stable

Program for Insertion Sort in C language

#include<stdio.h>
#include<stdlib.h>


void InsertionSort(int A[],int n)
{
    int i,j,x;
    for (i=1;i<n;i++)
    {
        j=i-1;
        x = A[i];
        while(j>-1 && A[j]>x)
        {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = x;
    }
}


int main()
{
    int A[10] = {1,5,2,1,6,3,6,2,5,10};
    int i;
    InsertionSort(A,10);
    for(i=0;i<10;i++)
    {
        printf("%d ",A[i]);
    }
    return 0;
}

Other sorting algorithms

Count sort in C/C++

Merge sort in C/C++

Quick Sort in C/C++

Selection sort in C/C++

Insertion Sort in C/C++

Bubble Sort in C/C++

Criteria for sorting analysis

LEAVE A REPLY