Insertion Sort Algorithm and its Implementation in C++/Java

Insertion Sort Featured Image

In this article, we will be learning the concept and implementation of Insertion Sort. As the name suggests, insertion sort works on the basic principle of inserting fresh values to an already sorted set of values.

Let us quickly move onto the underlying concept behind this sorting technique.


The concept behind Insertion Sort

In order to understand the concept, let us consider an empty array. Each iteration a new value is inserted and has to be placed within the array, such that the entire array is sorted.

Firstly, the array contains a single element, which means it is already sorted.

Insertion Sort Concept 1
Array containing a single element – 9

Subsequently, a new element is to be inserted into the array. Before placing it to the first empty place, we will check it against the elements already present.

We repeat this process of comparing until we encounter a greater element. On adding multiple elements, we will have the following stages.

Inserting 15 to the above array:

Insertion Sort Concept 2
Inserting 15 to the array

Adding 11 to the above array:

Insertion Sort Concept 3
Inserting 11 to the array

Lastly, as we insert 5, we notice that since there is no smaller element, it has to be placed at the beginning of the array.

Insertion Sort Concept 4
Inserting 5 to the array

This combined method of inserting and sorting gives rise to the established algorithm of Insertion Sort.

In real-life scenarios, we come across filled arrays instead of random numbers coming in for insertion. Therefore, the algorithm for Insertion Sort tries to apply the above concept to an already filled array.

Without any further ado, let us move on to the full-fledged algorithm of Insertion Sort.


The Insertion Sort Algorithm

The algorithm for this comparison-based sorting is very basic. It will be easier to walk-through the algorithm with an example.

Insertion Sort Basic Array
An example array

Step 1: Compare each element with preceding elements

Firstly, the comparison needs to start at the second element, since the first element by itself is already sorted. We will compare each element with the previous ones until the element under inspection is greater than the preceding element.

Insertion Sort Comparison Edited
Comparing second and first element

For every series of comparisons, the process either stops when we reach the first element or we encounter a smaller element. In the above case, we reach the first index while comparing.


Step 2: Shift each compared element on the right

In this step, we will shift each element that was compared to the right side of the array. The motive of the shifting is to make room for the element under inspection.

In the above example, only 25 is shifted.

Insertion Sort Shift Edited
Shifting 25 to the right

The shift creates an empty spot. That empty spot is occupied by the current element.


Step 3: Place the element at the empty spot

As the heading suggests, we will place the element, being used for comparison, at the empty index.

Insertion Sort Place Edited
Placing 15 at the empty spot

The combination of the above three steps sorts the array up to the second index. Similarly, these steps are repeated for all the elements within the array.

Let us take a quick look at the array after few iterations of the algorithm:

After second iteration:

Insertion Sort Second Iteration
Array after second iteration

However, no effect on the array since it is already sorted.

After third iteration:

Insertion Sort Third Iteration Edited
Array after third iteration

Step 4: Print the sorted array

Lastly, we print the sorted array.

Insertion Sort Sorted
Sorted Array

This sums up the entire algorithm of Insertion Sort.


Implementation of Insertion Sort in C++

#include<bits/stdc++.h>
using namespace std;

// Function that performs Insertion Sort
void insertion_sort(int arr[], int n){

	// Loop to implement steps for each element (except first)
	for(int i=1; i<n; i++){

		// Element under inspection
		int value = arr[i];

		// Preceding element index
		int j = i-1;

		// Step 1: Compare each element with preceding elements
		while(j >= 0 and arr[j] > value){

			// Step 2: Shift each compared element on the right
			arr[j+1] = arr[j];

			// Move along the preceding elements 
			j--;
		}

		// Step 3: Place the element at the empty spot
		arr[j+1] = value;
	}

	cout<<"The Sorted array:"<<endl;
	// Step 4: Print the sorted array
	for(int i=0; i<n; i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}

// Main Function
int main(){

	// The array to be sorted
	int arr[] = {15, 25, 30, 17, 9, 5, 20, 10, 11, 6};

	// The size of the array
	int n = sizeof(arr)/sizeof(arr[0]);

	// Print the original array
	cout<<"The Original array:"<<endl;
	for(int i=0; i<n; i++)
		cout<<arr[i]<<" ";
	cout<<endl;

	// Function call to implement Insertion Sort
	insertion_sort(arr, n);

	return 1;
}

Output:

The Original array:
15 25 30 17 9 5 20 10 11 6 
The Sorted array:
5 6 9 10 11 15 17 20 25 30

Implementation of Insertion Sort in Java

import java.io.*;
public class InsertionSort
{
    // Function that performs Insertion Sort
    void insertion_sort(int arr[], int n){

        // Loop to implement steps for each element (except first)
        for(int i=1; i<n; i++){

            // Element under inspection
            int value = arr[i];

            // Preceding element index
            int j = i-1;

            // Step 1: Compare each element with preceding elements
            while(j >= 0 && arr[j] > value){

                // Step 2: Shift each compared element on the right
                arr[j+1] = arr[j];

                // Move along the preceding elements 
                j--;
            }

            // Step 3: Place the element at the empty spot
            arr[j+1] = value;
        }

        System.out.println("The sorted array:");        
        // Step 4: Print the sorted array
        for(int i=0; i<n; i++)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
   
    public static void main(String args[]) 
    { 
        // The array to be sorted
        int arr[] = {15, 25, 30, 17, 9, 5, 20, 10, 11, 6};

        // The size of the array
        int n = arr.length;

        // Print the original array
        System.out.println("The original array:");
        for(int i=0; i<n; i++)
            System.out.print(arr[i]+" ");
        System.out.println();

        // Creating object for InsertionSort Class
        InsertionSort is = new InsertionSort();

        // Function call to implement Insertion Sort
        is.insertion_sort(arr, n);    
    } 
}

Output:

The original array:
15 25 30 17 9 5 20 10 11 6 
The sorted array:
5 6 9 10 11 15 17 20 25 30 

Complexities involved in Insertion Sort

There are two complexities involved in the running of Insertion Sort – Time and Space Complexity

Time Complexity

In general, the time complexity depends on the size and arrangement of values within an array. Therefore, the standard terms like “best-case” and “worst-case” complexities are a measure of time-complexities for algorithms.

Worst-Case: O(n^2) – The scenario when the array is in descending order. Meanwhile, the algorithm tries to sort in the ascending order.

Best-Case: O(n) – The scenario when the array is already in a sorted order.

Overall, the time complexity for Insertion Sort is O(n^2).

Space Complexity

In simpler terms, space complexity refers to the amount of excess space or memory used during the running of the algorithm. Since we are only using extra variables like value, i and j, the space complexity is O(1).


Conclusion

Insertion Sort stands out as a very simple sorting technique. However, being a comparison-based sorting, makes its time complexity higher than its contemporary sorting techniques.

We hope this article was easy to follow and helped the reader to understand the underlying concept along with the implementation of Insertion Sort Algorithm. Feel free to comment below for any queries or feedback.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages