Insertion Sort: Algorithm with C, C++, Java, Python Examples

What is Insertion Sort?

Insertion sort is one of the comparison sort algorithms used to sort elements by iterating on one element at a time and placing the element in its correct position.

Each element is sequentially inserted in an already sorted list. The size of the already sorted list initially is one. The insertion sort algorithm ensures that the first k elements are sorted after the kth iteration.

Characteristics of Insertion Sort Algorithm

The Algorithm for Insertion Sort has following important Characteristics:

  • It is a stable sorting technique, so it does not change the relative order of equal elements.
  • It is efficient for smaller data sets but not effective for larger lists.
  • Insertion Sort is adaptive, which reduces its total number of steps if it is partially sorted. Array is provided as input to make it efficient.

How does Insert Operation work?

In Insertion Sort algorithm, the insert operation is used to sort unsorted elements. It helps to insert a new element into an already sorted list.

Pseudocode of insert operation:

Consider a list A of N elements.

A[N-1] is the element to be inserted in the sorted sublist A[0..N-2].
For i = N-1 to 1:
if A[i] < A[i-1], then swap A[i] and A[i-1]
else Stop   

Insert Operation work

In the above example, a new element 6 is to be inserted in an already sorted list.

Step 1) Compared with the left adjacent element of A[5], 9 > 6, we swap the position of 9 and 6. Now element 6 is moved to A[4].

Step 2) Now, we compare A[4] and A[3], and we find that A[3] > A[4], we again swap the position of 6 and 8.

Step 3) Now compare A[3] and A[2], as A[2] > A[3] swap the position of 7 and 6.

Step 4) We compare A[1] and A[2], and as A[1] < A[2], i.e., the left adjacent element is no longer greater. Now we conclude that 6 is inserted correctly, and we stop the algorithm here.

How the Insertion Sort Works

The insert operation discussed above is the backbone of the insertion sort. The insert procedure is executed on every element, and in the end, we get the sorted list.

Insertion Sort Works

The above example figure demonstrates the working of insertion sort in data structure. Initially, only one element is there in the sorted sublist i.e., 4. After inserting A[1] i.e., 3, the size of the sorted sublist grows to 2.

C++ Program for Insertion Sort

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
    
    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); 

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){        
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    } 

    return 0;
}

Output:

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code for Insertion Sort

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Output:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Program for Insertion Sort

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Output:

Unsorted: 9 8 7 6 5 4 3 3 2 1 
Sorted: 1 2 3 3 4 5 6 7 8 9

Properties of Insertion Sort

Here are important properties of Insertion Sort:

  • Online: Insertion sort can sort elements as it receives. That is, if we have already sorted a list of elements and append some more elements to the lists, then we do not need to run the entire sorting procedure again. Instead, we need to only iterate on newly added elements.
  • In-place: The space complexity of insertion sort algorithm is constant and does not require extra space. This algorithm sorts elements in place.
  • Stable: In insertion sort, we do not swap the elements if their values are equal. For example, two elements, x, and y, are equal, and x appears before y in unsorted lists, then in the sorted list, x will appear before y. This makes insertion sort stable.
  • Adaptive: A sorting algorithm is adaptive if it takes less time if the input elements or subset of elements are already sorted. As we discussed above, the best running time of insertion sort is O(N), and the worst running time is O(N^2). Insertion sort is one of the adaptive sorting algorithms.

Complexity of Insertion Sort

Space Complexity

The insertion sort doesn’t require extra space to sort the elements, the space complexity is constant, i.e., O(1).

Time Complexity

As insertion sort iterates each element simultaneously, it requires N-1 passes to sort N elements. For each pass, it may make zero swaps if the elements are already sorted, or swap if the elements are arranged in descending order.

  • For pass 1, the minimum swaps required are zero, and the maximum swaps required are 1.
  • For pass 2, the minimum swaps required are zero, and the maximum swaps required are 2.
  • For pass N, the minimum swap required is zero, and the maximum swaps required are N.
  • The minimum swap is zero, so the best time complexity is O(N) for iterating N passes.
  • Total maximum swaps are (1+2+3+4+..+N) i. N(N+1)/2, the worst time complexity is O(N^2).

Here is the important time complexity of insertion sort:

  • Worst Case Complexity: O(n2): Sorting an array in descending order when it is in ascending order is the worst-case scenario.
  • Best Case Complexity: O(n): Best Case Complexity occurs when the array is already sorted, the outer loop runs for n number of times whereas the inner loop does not run at all. There is only n number of comparisons. So, in this case, complexity is linear.
  • Average Case Complexity: O(n2): It happens when the elements of an array occur in the jumbled order, which is neither ascending nor descending.

Summary

  • Insertion sort is a sorting algorithm method that is based on the comparison.
  • It is a stable sorting technique, so it does not change the relative order of equal elements.
  • On every element, the insert operation is used to insert the element in the sorted sub-list.
  • Insertion sort is an in-place sorting algorithm.
  • The worst and average time complexity of insertion sort is quadratic, i.e., O(N^2).
  • Insertion sort does not require any auxiliary space.