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.
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:
Adding 11 to the above 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.
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.
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.
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.
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.
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:
However, no effect on the array since it is already sorted.
After third iteration:
Step 4: Print the sorted array
Lastly, we print the 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.