In this tutorial, you'll find out how the Insertion sort algorithm works. Also, you'll find working samples of insertion sort in C, C++, Java, and Python.

Insertion sort algorithm works similarly as we sort cards in our hands during cards.

Insertion sort algorithm

We assume that the primary card is already sorted then, we select an unsorted card. If the unsorted card is bigger than the cardboard in hand, it's placed on the proper otherwise, to the left. within the same way, other unsorted cards are taken and put at their right place.

A similar approach is employed by insertion sort.

Learn How the Insertion Sort algorithm is going to Works

Insertion sort may be an algorithm that places an unsorted element at its suitable place in each iteration.

Initial array in insertion sort

The first element within the array is assumed to be sorted. Now Take the second element and work with it and store it separately in key.

in this photo first element greater then key is  in insertion sort

If the first element is greater than key, then key is placed in front of the first element 

Compare key with the primary element. If the primary element is bigger than key, then key's placed ahead of the primary element.

Now, the primary two elements are sorted.

Take the third element and compare it with the weather on the left of it. Placed it just behind the element smaller than it. If there's no element smaller than it, then place it at the start of the array. 

insertion sort algorithm step 1

follow these steps and put every unsorted element at its right position 

insertion sort algorithm step 2

 

 

in step 3 behind 1, all array is sorted

 

Algorithm for Insertion Sort:-

insertionSort(array)
 mark first element as sorted
 for every unsorted element X
 'extract' the element X
 for j X
 move sorted element to the proper by 1
 break loop and insert X here
end insertionSort

Complexity:-

Time Complexities

 Worst Case Complexity: O(n2)
 Suppose, an array is in ascending order, and you would like to sort it in descending order. during this case, the worst-case complexity occurs.

 Each element has got to be compared with each of the opposite elements so, for each nth element, (n-1) number of comparisons are made.

 Thus, the entire number of comparisons = n*(n-1) ~ n2
 
Best Case Complexity: O(n)
 When the array is already sorted, the outer loop runs for n number of times whereas the inner loop doesn't run in the least. So, there is only n number of comparisons. Thus, complexity is linear.

 Average Case Complexity: O(n2)
 It occurs when the weather of an array is in jumbled order (neither ascending nor descending).

Space Complexity for Insertion sort algorithm

Space complexity is O(1) because of an additional variable key's used.

Insertion Sort Applications

•  the array features a small number of elements

•  there are only a couple of elements left to be sorted

insertion sort algorithm with example in c

// Insertion sort in C

#include <stdio.h>

// Function to print an array
void printArray(int array[], int size) {
 for (int i = 0; i < size; i++) {
 printf("%d ", array[i]);
 }
 printf("\n");
}

void insertionSort(int array[], int size) {
 for (int step = 1; step < size; step++) {
 int key = array[step];
 int j = step - 1;

 // Compare key with each element on the left of it until a component smaller than
 // it's found.
 // For descending order, change keyarray[j].
 while (key < array[j] && j >= 0) {
 array[j + 1] = array[j];
 --j;
 }
 array[j + 1] = key;
 }
}

// Driver code
int main() {
 int data[] = {9, 5, 1, 4, 3};
 int size = sizeof(data) / sizeof(data[0]);
 insertionSort(data, size);
 printf("Sorted array in ascending order:\n");
 printArray(data, size);
}