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.

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

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

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