Insertion Sort Program in C

Introduction

This is an on-the-spot comparison-based sorting algorithm. In this sort a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. It is named insertion sort as an element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). Insertion Sort is not suitable for large data sets as its average and worst case complexity are of Ο(n2), where n is the number of items.

Algorithm

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Program

//C program Insertion Sort Program

#include <stdio.h>
#include <conio.h>

int main()
{
    int a[50],n,i,j,temp;
    printf("Enter the size of array (less than 50): ");
    scanf("%d",&n);
    printf("Enter the array elements: ");

    for(i=0;i<n;++i)
        scanf("%d",&a[i]);

 for(i=1;i<n;i++)
 {
 temp = a[i];
 j=i-1;
 while(temp<a[j] && j>=0)
 /*To sort elements in descending order, change temp<a[j] to temp>a
[j] in above line.*/
 {
 a[j+1] = a[j];
 --j;
 }
 a[j+1]=temp;
 }

    printf("\nArray after sorting: ");
    for(i=0;i<n;++i)
        printf("%d ",a[i]);
    getch();

    return 0;
}

Output