Home » Code Snippets » C/C++ Data Structure programs

# C program to implement Insertion Sort Algorithm

**Insertion Sort Algorithm implementation using C program**: Here, we are going to learn about the **Insertion Sort Algorithm**, how it works and its C language implementation.

Submitted by Sneha Dujaniya, on May 09, 2020

Insertion sort is a simple sorting algorithm that is **online, stable, and in-place**.

- A
**stable sorting algorithm**is the one where two keys having equal values appear in the same order in the sorted output array as it is present in the input unsorted array. - An
**in-place sorting algorithm**has various definitions but a more used one is –

"An in-place sorting algorithm does not need extra space and uses the constant memory for manipulation of the input in-place. Although, it may require some extra constant space allowed for variables."

The basic principle followed in **Insertion sort** is that the key element is placed at its position in the sorted array in every iteration.

**Pseudo code:**

for i = 1 to n key = arr[i] j = i-1 while j >= 0 and key < arr[j] arr[j + 1] = arr[j] j = j – 1 end while arr[ j + 1 ] = key end for

**Example:**

Array = 12, 14, 11, 5, 6 Initially, we run the loop from index = 1 (14) till index = 4 (last value) For i = 1, compare 14 with 12 and we see, 12< 14, so no change. For i = 2, compare 11 with 14, and we see, 11<14, shift 14 to next place. Now, compare 11 with 12, we see that 11<12, shift 12 by one place. Now, put 11 at index 0. Array: 11, 12, 14, 5, 6 For i = 3, compare 5 and keep shifting the values. Array: 5, 11, 12, 14, 6 For i = 4, compare with all the previous elements and keep shifting the values accordingly.

**Time Complexity: **The time complexity of Insertion Sort can be described as: **T(n) = T(n/2) + C **

- Worst case: O(n^2)
- Average Case: O(n^2)
- Best case: O(n), when the array is already sorted
- Space Complexity: O(1)

**C Implementation:**

#include <stdio.h> void insertion(int arr[], int n) { int i, j; for (i = 1; i < n; i++) { int key = arr[i]; j = i - 1; while (key < arr[j] && j >= 0) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } printf("\nAfter performing Insertion sort:\n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); } int main() { int arr[] = { 10, 14, 3, 8, 5, 12, 16, 13 }; int n = sizeof(arr) / sizeof(arr[0]); insertion(arr, n); return 0; }

**Output**

After performing Insertion sort: 3 5 8 10 12 13 14 16

**Insertion Sort** can be optimized using Binary Insertion sorting. We must use Insertion sort where the elements are mostly sorted and only some elements are misplaced. Also, it should be used where there is lesser number of data points due to its large time complexity.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.