What is Insertion Sort in C with Example

Insertion Sort in C is a comparison-based sorting algorithm that arranges numbers of an array in order. It is stable, adaptive, in-place and incremental in nature. The insertion sort is useful for sorting a small set of data. It sorts smaller arrays faster than any other sorting algorithm. But, it is impractical to sort large arrays.

 What is insertion sort?

Insertion sort is a sorting algorithm that places an unsorted element at its correct position in each iteration. During insertion sort, the relative order of elements not changed. Therefore, it is a stable sorting algorithm. And insertion sort requires only O(1) of additional memory space. Consequently, it sorts in-place.

Insertion Sort works in the same way as we set up a card deck. We also introduced it in the following Program code.

How insertion sort works in C

In every iteration, it compares the current element with all the values in the sorted array. If the current element is higher than the array element, it leaves the element and iterates into the next array element. But, if the current element is smaller than the array element, it shifts the remaining part of the element in the array by one place and makes space for the present in the sorted array.

The way insertion sort takes one input elements at a time, iterates through the sorted sub-array. With every iteration, it inserts one element at its correct position—that why the algorithm is known as Insertion sort.

Insertion sort is an example of an incremental algorithm.

In the incremental algorithms, the complicated structure on n items is built by first building it on n − 1 item. And then, we make the necessary changes to fix things in adding the last item. Insertion sort builds the sorted sequence one element at a time. Therefore, it is an example of an incremental algorithm.

The time complexity of insertion sort

The complexity of an algorithm is the measure of the number of comparisons made in the algorithm—an algorithm’s complexity measure for the worst case, best case, and the average case.

Worst-Case Complexity (Reverse sorted array): O(n²)

In the case of insertion, the worst case occurs when the array is already in reverse order. In the first pass, it compares a maximum of one element. The second pass compares a maximum of two elements and so on, up to a maximum of (n-1) comparisons in the last pass. Hence, the total number of comparisons made will be O(n²).

• If an array is in ascending order, and you want to sort it in descending order. In this situation, the worst-case complexity occurs.
• Each element has to compare with every other element, so the number of comparisons made for every nth element (n-1).
• The worst-case for an insertion sorting algorithm is a reverse ordered array, and its time is quadratic.
• Thus, the total number of comparisons = n*(n-1) ~ n²

For example:
 If the input array has elements as {9, 8, 7, 4, 2}
 then the output array will have data as {2, 4, 7, 8, 9}

Best Case Complexity: O(n)

The best-case running time of the insertion sort is O(n). The best-case occurs when the array is already sorted. We have to make a minimum number of swaps. In that case, only one comparison is made on each pass, so that the time required is O(n).

For example:
 If the input array has data as {-4, 41, 76} 
 then the expected output array will have data as {-4, 41, 76}

Average Case Complexity: O(n²)
It occurs when the elements of an array are in random distribution.

For example:
If the input array is {5, 7, 2, 3, 6, 4}
the expected output array will have data as {2, 3, 4, 5, 6, 7}

Space Complexity

Space complexity is O(1) because an extra variable key is used.

Insertion Sort Algorithm

insertionSort(array)
 mark first element as sorted
 for each unsorted element X
 'extract' the element X
  for j <- lastSortedIndex down to 0
   if current element j > X
    move sorted element to the right by 1
    break loop and insert X here
    end insertionSort

Insertion Sort Program in C

/* C Program for Insertion Sort */
#include<stdio.h>
int main() {
 int a[100], n, i, j, element; 
 printf("\nEnter the total Number of Elements : ");
 scanf("%d", &n);
 printf("\nEnter the Array Elements : ");
 for(i = 0; i < n; i++)
  scanf("%d", &a[i]);
  for(i = 1; i <= n - 1; i++) {
   for(j = i; j > 0 && a[j - 1] > a[j]; j--) {
     element = a[j];
     a[j] = a[j - 1];
     a[j - 1] = element;
   }
}
  printf("\n Insertion Sort Result : ");
  for(i = 0; i < n; i++) {
    printf(" %d \t", a[i]);
  }
  printf("\n");
  return 0;
}