Before we proceed, let's usnderstand the meaning of insertion sort in simple language. Insertion Sort is a simplest data Sorting algorithm which sorts the array elements by shifting elements one by one and inserting each element into its proper position.

Insertion sorting in C

In the insertion sort algorithm, we sort a unsorted array by inserting its elements to the proper positions in a sorted array. Insertion sort algorithm picks elements one by one and places it to the right position where it belongs in the sorted list of elements. An insertion sort has the benefits of simplicity and low overhead.

Best case complexity of insertion sort is O(n), average and the worst case complexity is O(n2).

It is good for substantially sorted list, if the list is long and requires lots of sorting then usually heap or merge sort is best.

It is a simple data Sorting algorithm. It is also better than Selection Sort and Bubble Sort algorithms.

Insertion-sort-example-min.png

Image Source

The above diagram depicts the complete run of insertion sort on an array of four integers which is initially reverse-sorted. The red elements are the sorted partition, while the elements to their right are yet to be sorted.

Main logic

In an insertion sort, the first element in the array is considered as sorted, even if it is an unsorted array.

In an insertion sort, each element in the array is checked with the previous elements, resulting in a growing sorted output list.

With each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array and inserts it there. The iteration continues until the whole list is sorted.

Considering above logic Algorithm for insertion sort will be as below

1. Iterate from arr[1] to arr[n] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor, compare its elements before. 
   Move the greater elements one position up to make space for the swapped element.

Insertion sort program in C

#include<stdio.h>
int main()
{
    int i, n, arr[10],j, p,tmp;
    //ask user for number of elements of list
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    
    //get the list of elements
    printf("Enter %d elements : ", n);
    for(i = 0; i < n; i++)
    {
        scanf("%d",&arr[i]);
    }
    //loop each element of list
    for(i = 1; i < n; i++)
    {
        //get current variable in tmp 
        j = i;
        //loop while value is greater than 0 and left side value is greater than right side value
        //then you should interchange the values using temp
          while ( j > 0 && arr[j-1] > arr[j]) {
              tmp          = arr[j];
              arr[j]   = arr[j-1];
              arr[j-1] = tmp;
         
              j--;
            }   
        
    }
    printf("The sorted elements are :  ");
    for(i = 0; i < n; i++)
    {
        printf("%d  ",arr[i]);
    }
    
    return 0;
}

I have explained the code using comments, take a look, after executing the above program online provide me output as below

Enter the number of elements: 5                  
Enter 5 elements : 2 1 5 4 3                                  
The sorted elements are :  1  2  3  4  5

insertion-sort-in-c-min.png

You may also like:

Linear search program in C (Various ways explained with example)

Sorting array elements in ascending order program in C

Leap year program in C

If you have any doubt feel free to ask questions in the comment's section.