Insertion Sort

Write a C program to
implement Insertion Sort Algorithm

Algorithm:

 for (c
= 1 to  n - 1)

  {

    d
<= c;

   
while ( d > 0 AND array[d] < array[d-1])

    {

     
t          <= array[d];

     
array[d]   <= array[d-1];

     
array[d-1] <= t;

      d
<= d-1;

    }

  }

Program:

#include <stdio.h>

void main()

{

  int
n, array[20], c, d, t;

 
printf("Enter the number of Elements:");

 
scanf("%d", &n);

 
printf("Enter %d integers:\n", n);

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

  {

   
scanf("%d", &array[c]);

  }

  for
(c = 1 ; c <= n - 1; c++)

  {

    d =
c;

   
while ( d > 0 && array[d] < array[d-1])

    {

     
t          = array[d];

     
array[d]   = array[d-1];

     
array[d-1] = t;

     
d--;

    }

  }

 
printf("Sorted list in ascending order:\n");

  for
(c = 0; c <= n - 1; c++)

  {

   
printf("%d  ",
array[c]);

  }

}

Output:

Enter the number of Elements:5

Enter 5 integers:

Enter the elements:

8 6 5 1 65

Sorted list in ascending order: 1 5 6 8 65

Conclusion:

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 quicksort,
heapsort, or merge sort.