Insertion Sort

Insertion Sort program in C

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quick sort or merge sort. However, insertion sort provides several advantages:

• Efficient for (quite) small data sets, much like other quadratic sorting algorithms

• More efficient in practice than most other simple quadratic (i.e., O(N²)) algorithms such as bubble sort

• It is Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position

• It is a Stable sorting algorithm; i.e., does not change the relative order of elements with equal keys.

• It is an In-place algorithm ; i.e., only requires a constant amount O(1) of additional memory space

• Online; i.e., can sort a list as it receives it

Insertion sort program in C:

#include<stdio.h>

int main(){
    
    int swap,key,i,j,a[]={27,13,16,13,10,1,5,7,12,4,8,9,0};
    int n= sizeof(a)/sizeof(a[0]);
    j=0;
    for(i=1;i<n;i++){
       key=a[i];
       j=i-1;
       //insert key into sorted sequence
       while(j>=0 && key<a[j]){
          a[j+1]=a[j];
          j--; 
       }
       
       a[j+1]=key;
       
    }   
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
    
}

Also see: bubble sort, Merge Sort