Insertion sort in C programming


In this tutorial, you will learn concept and implementation of insertion sort in C programming with the example.

Insertion sort in C programming is the simple sorting algorithm. As the name suggests, this algorithm just compares two elements in the array and insert it in the appropriate place.

For sorting n elements array, this method will have n-1 iteration.

For example: To sort an array of 3, 12, 7, 1, 5

How insertion sort in C programming works?

Following figure clearly, depicts the use of insertion sort in c programming.

insertion sort in c programming

Explanation of insertion sort in C programming

Pass 1: Comparison is made between 3 and 12. Since 3 is smaller than 12, it remains as it is.

Pass 2: 7 is compared against 12 and 3. Since 7 is less than 12 and greater than 3 it is moved to data[ 1 ] place.

Pass 3: 1 is compared against 12, 7 and 3. Since 1 is less than all elements it is moved to data[ 0 ] and other elements are moved one position down.

Pass 4: 5 is compared against 12, 7, 3 and 1. Since 5 is less than 7 and greater than 3 it is moved to data[ 2 ].

Other techniques for sorting elements of an array in C programming are:

C program for sorting elements of array using insertion sort algorithm

/* sorting array using insertion sort method */

#include <stdio.h>
#define SIZE 5

int main ()
{
   int data[ SIZE ] = { 3, 12, 7, 1, 5};
   int i, j, temp;

   printf("Original order of data items:\n");

   //printing data items
   for ( i = 0; i < SIZE; ++i)
   {
      printf("%4d", data[ i ]);
   }

   //sorting using insertion method
   for (i = 1; i < SIZE; i++)
   {
      temp = data[ i ];
      j = i - 1;
      while (j >= 0 && data[ j ] > temp)
      {
         data[ j + 1 ] = data[ j ];
         j = j - 1;
      } //end while loop

      data[ j + 1 ] = temp;
   } //end for loop

   printf("\n\nData items in ascending order:\n");
   for (i = 0; i < SIZE; ++i)
   {
      printf("%4d", data[ i ]);
   }
   return 0;
}

Output

Output insertion sort algorithm

Note: For sorting array elements in descending order following change should be made in while condition:

while (j >= 0 && data[ j ] < temp)