C Program to sort using insertion sort

This program demonstrates insertion sort in C. Insertion sort  proceeds by considering each item in the list and placing it in the position it belongs to in the sorted list. Other elements will be shifted either to the left or to the right in order to make space for the current element. Insertion sort is only efficient for smaller lists and cannot be used in larger lists since the complexity will be high. In the best case insertion sort has a time complexity of O(n) and in the worst case, the time complexity is O(n²).

Program

#include<stdio.h>

#include<conio.h>

void main()

{

int a[10],small,n,i,j;

printf("Enter the size of the array: ");

scanf("%d",&n);

printf("Enter the elements: \n");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

for(i=1;i<n;i++)

{

small=a[i];

j=i-1;

while(j>=0&a[j]>small)

{

a[j+1]=a[j];

j--;

}

a[j+1]=small;

}

printf("\nArray after sorting\n");

for(i=0;i<n;i++)

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

getch();

}

Output

Insertion Sort

Related post:-  C++ program to implement insertion sort