Write a Program Insertion Sort using C .

• Insertion sort is also a simple sorting technique and is best suited for small data sets. But it is not suitable for large data sets. 
• but it is a better sorting technique than bubble sort and selection sort because the complexity of insertion sort is less than both.

• Time Complexity  
• Best  [ Ω(n) ]
• Average  [ θ(n^2) ]
• Worst  [ O(n^2) ]

Insertion Sort Algorithm

insertionSort(arr)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

EXAMPLE :-

#include<stdio.h>

void Array(int arr[], int size)

{

for(int i=0; i<size; i++)

{

printf("%d ",arr[i]);

}

printf("\n");

}

void insertionSort(int arr[], int size)

{

for(int step=1; step<size; step++)

{

int key = arr[step];

int j=step-1;

while(key<arr[j] && j>=0)

{

arr[j+1] = arr[j];

--j;

}

arr[j+1]=key;

}

}

int main(){

int data[] = {90, 50, 14, 24, 20};

int size = sizeof(data)/sizeof(data[0]);

insertionSort(data, size);

printf("Sorted array in Asending order :\n");

            printf("***********************************\n");

Array(data, size);

}

OUTPUT

Sorted array in Asending order : *********************************** 14 20 24 50 90