Problem Statement: Given an array of N integers, write a program to implement the Insertion sorting algorithm.

Examples:

Example 1:
Input: N = 6, array[] = {13,46,24,52,20,9}
Output: 9,13,20,24,46,52
Explanation: 
After sorting the array is: 9,13,20,24,46,52

Example 2:
Input: N=5, array[] = {5,4,3,2,1}
Output: 1,2,3,4,5
Explanation: After sorting the array is: 1,2,3,4,5

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach: 

• Take an element from the unsorted array.
• Place it in its corresponding position in the sorted part.
• Shift the remaining elements accordingly.
• In this approach, start iterating the “outer for loop”  from the 2nd position of the array.
• The “inner while loop” shifts the elements using swapping.
• In the below dry run, 

Blue color represents unsorted array elements

The yellow color represents the current element to be placed at the appropriate position.

The green color represents the sorted array elements

Code:

#include<stdio.h>

void insertion_sort(int arr[], int n) {
  // insertion sort
  int i;
  for (i = 1; i < n; i++) {
    int current = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > current) {
      //swap
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  printf("After insertion sort:\n");
  for (int i = 0; i < n; i++) {
    printf("%d ",arr[i]);
  }
 
}
int main() {
  int arr[] = {13,46,24,52,20,9};
  int n = sizeof(arr) / sizeof(arr[0]);
  printf("Before insertion sort:\n");
  for (int i = 0; i < n; i++) {
    printf("%d ",arr[i]);
  }
  printf("\n");
  insertion_sort(arr, n);
  return 0;
}

Special thanks to Subhrajit Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article

Reference: https://takeuforward.org/data-structure/insertion-sort-algorithm/