Understanding the Insertion Sort

Introduction

Insertion sort is a sorting algorithm in which the elements are transferred one at a time to their correct position. It can be considered as shifting around and inserting elements in the right order to sort an unsorted array of any size.

The array is searched sequentially on a fundamental level, and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets. 

Let us have a look at a few examples to get a clear understanding of insertion sort.

Examples of Insertion Sort

Consider an array in the below diagram = [ 7, 5, 4, 2 ]

In step 1:
Since 7 is the first element and has no other element to be compared with, it remains at its position. 

In step 2:
On moving towards 4, 7 is the largest element in the sorted list and is greater than 4. So, move 4 to its correct position, i.e. before 7. 
Now our array is [4,7,5,2].

In step 3:
Similarly with 5, as 7 (largest element in the sorted list) is greater than 5, we will move 5 to its correct position. 
Now our sorted array is[4,5,7,2]. 

In step 4: Finally, for 2, all the elements on the left side of 2 (sorted list) are moved one position forward as all are greater than 2, and then 2 is placed in the first position. 
Finally, the given array will result in a sorted array [2,4,5,7]

Let us look at one more example:

In the image shown above, we have an unsorted list = [ 54,26,93,17,77,31,44,55,20] 

Step 1:
We take the first element 54 from the unsorted list and add it to our new sorted list.

Step 2:
Then we move on to the next element in the unsorted list that is 26. We will compare it to the element which already exists in our sorted list.                                            
26 <  56, so we will push 56 by one position and add 26 to our sorted list.

Step 3:
We then move on to the next element, which is 93. Since it is larger than the sorted list element, it will stay at its current position, and we will move to the next element, i.e. 17, compare it with all the elements of the sorted list, and find its correct place. 

We will keep on doing these repeated insertions until we get the sorted list as [17,20,26,31,44,54,55,77,93]

How does Insertion sort work?

Insertion sort algorithm has two primary and essential aspects associated with it.

•  The first one has to do with how this is structured. 
• The second aspect has to do with the way it iterates and sorts the list of elements given.

In some way, we will find that insertion sort is similar to other sorting algorithms that we have already explored. So, now let’s have a look at the algorithm of insertion sort:

Algorithm For Insertion Sort:

Step 1 −
If it is the first element, then it is already sorted.

Step 2 −
For every next element, compare the elements in the sorted sub-list and find the correct position i.e shift all the elements in the sorted sub-list while they are greater than the value that needs to be sorted. 

Step 3 −
Insert the value at the position found in step 3. It is to be noted that no shift of elements in the sorted sublist takes place if the value to be sorted is already greater than or equal to the last element of the sorted sublist.

Step 4 −
Repeat the entire process until the list is sorted.

Pseudo-Code

For i = 1 to A.length - 1
Current = A[i] 
J = i - 1
While j > 0 && A[J] > current
A[j + 1] = A[J] 
J = J - 1
A[J + 1] = current

Let us now see how this algorithm can be formulated in our programs.

Implementation in Java

public class InsertionSort 
{
void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
 }
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]
{
int arr[] = { 28,18,8,11,7,2 };
InsertionSort ob = new InsertionSort();
ob.sort(arr);
printArray(arr)
    }
}

The output of the code is: 

2 7 8 11 18 28 

Implementation in C++

#include <iostream>            using namespace std;
void printArray(int array[], int size) 
{
for (int i = 0; i < size; i++) 
{
cout << array[i] << " ";
}
cout << endl;
}
void insertionSort(int array[], int size)
{
for (int step = 1; step < size; step++)
{
int key = array[step];
int j = step - 1;
while (key < array[j] && j >= 0) 
{
array[j + 1] = array[j];
--j;
}
array[j + 1] = key;
}
}
int main() 
{
int data[] = {11,28,19,12,30,18,4};
int size = sizeof(data)               / sizeof(data[0]);
insertionSort(data, size);
printArray(data, size):,
}

The Output of the code is:

4,11,12,18,19,28,30

Implementation in Python:

def insertion_sort(list):
for i in range(1, len(list)):
value = list[i]
j = i - 1
while j >= 0 and value < list[j]:
list[j + 1] = list[j]
j -= 1
list[j + 1] = value
return list
list = [11,12,28,30,19,20,1]
print(insertion_sort(list))

The Output of the code is:
[1, 11, 12, 19, 20, 28, 30]

Time Complexity Analysis:

Even though insertion sort is efficient, still, if we provide an already sorted array to the insertion sort algorithm, it will execute the outer for loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n. 

Whereas for an unsorted array, it takes an element to compare with all the other elements, which means every element is compared with all the previous elements, thus, making it for n x n, i.e., n2 comparisons. 

Worst Case Time Complexity [ Big-O ]: O(n^2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n^2)

Relation With Other Sorting Algorithms:

Insertion sort is somewhat similar to selection sort. After k passes in the array, the first k elements are in sorted order in the selection sort. 

However, the critical difference between the two algorithms is that insertion sort scans backward from the current position while selection sort scans forwards. This results in selection sort making the first k elements the k most minor elements of the unsorted input, while in insertion sort, they are simply the first k elements of the input.

Advantage of Insertion Sort

The advantage of insertion sort over selection sort is that selection sort scan the remaining elements to find the absolute smallest element in the unsorted portion of the list, while insertion sort requires only a single comparison when the (k + 1) th element is greater than the kth element; when this is frequently true, insertion sort is distinctly more efficient compared to selection sort. 

On average, insertion sort will compare and shift half of the previous elements, which means it will perform half the number of comparisons as the selection sort.

Difference between Selection, Bubble, and Insertion Sort:

Time & Space Complexity:

All three sorts have O(n2) time complexity. But via the flag variable, we can reduce the time complexity of Insertion and insertion to O(n) is the best case i.e when the array is already sorted. Space Complexity is the same for all, i.e., O(1).

Frequently Asked Questions

Key Takeaways

This blog thoroughly discussed how Insertion Sort works in programming languages like Python, Java, and C++.

Insertion sort isn’t an efficient algorithm for large datasets, but it is one of the easiest sorting approaches. In insertion sort, we keep shifting the elements from the unsorted section one by one until an appropriate location is found for that element in the sorted section. We keep on doing this until we get the sorted array.

Well-versed that practice makes a man perfect! So what are you waiting for?

Practice a wide range of interview questions, frequently asked, on all the Data Structures and algorithms topics on Codestudio and master your skills.

Go on, readers! Happy Learning!