# Insertion Sort in C

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

DisclaimerDon’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:

## C Program

``````#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);
printf("Before insertion sort:\n");
for (int i = 0; i < n; i++) {
printf("%d ",arr[i]);
}
printf("\n");
insertion_sort(arr, n);
return 0;
}``````

Output:

Before insertion sort:
13 46 24 52 20 9
After insertion sort:
9 13 20 24 46 52

Time Complexity: O(n^2) (nested loops)

Space Complexity: O(1)