INSERTION SORT ALGORITHM

INTRODUCTION

In this tutorial, we are going to learn about the insertion sort algorithm. It is a simple and efficient algorithm which is widely used for sorting elements. The implementation of the insertion sort algorithm works similarly as we sort out cards, we assume that the first card is already sorted, and then we arrange all the unsorted cards in their respective positions on comparing with the sorted card. 

The implementation of the insertion sort algorithm mainly follows two portions.

1. Sorted portion

2. unsorted portion

Initially, the first element of the array is considered the sorted portion and it is compared with the next element to it. If the next element is placed in a suitable order, then it is not disturbed, otherwise, it is swapped with the left element according to the condition.

Let’s understand the working of the insertion sort with an example.

Let’s consider these are the elements of an array.

Arr= [23 ,56 ,32 ,78 ,12]

in the first pass, 23  is compared with 56. as 23 < 56, both elements are considered to be in ascending order and hence swapping doesn’t occurs. Then 56 is also considered to be in the sorted portion.

23 56 32 78 12
23 56 32 78 12

In the second pass, 56 is compared with 32. as 56>32, swapping occurs. After swapping 56 and 32, the position of elements looks like this.

23 56 32 78 12
23 32 56 78 12

Now, 32 is also compared with 23. since 23<32, swapping doesn’t occur and the elements after the second pass are arranged as follows.

23 32 56 78 12
23 32 56 78 12

In the third pass, 56 is compared with 78. as 56<78, both elements are considered to be in ascending order and hence swapping doesn’t occurs. Then, 78 is also considered to be in the sorted portion

23 12 32 78 56
12 23 32 56 78
12 23 32 56 78
12 23 32 56 78
12 23 32 56 78

In the fourth pass, 78 is compared with 12. as 78>12, swapping of the elements occurs and after swapping, the positioning of the elements looks like this.

23 32 56 78 12
23 32 56 12 78

Now, 12 is compared with 56 too. As 56>12, swapping of the elements is done.

23 32 56 12 78
23 32 12 56 78

Now, 12 is compared with 32 and swapping occurs as 32>12.

23 32 12 56 78
23 12 32 56 78

And 12 is compared with the last element left, 23 and 23>12, so swapping occurs.

23 12 32 56 78
12 23 32 56 78

After the fourth pass, the elements are already in sorted order and after all the traversals, the positioning of the elements of the array looks like this.

The sorted array is 12 23 32 56 78

this is the working of the bubble sort algorithm. Now, let’s look at the algorithm for the Insertion sort.

ALGORITHM

Step 1: Start.

Step 2: Take the first element and compare it with the next element. If the current element is larger than the next element, swap those positions and also compare with the elements on the left side of the current element.

Step 3: If the elements on the left are also larger than the current element, swap those elements one by one until the current element reaches the intended position.

Step 4: Stop.

Let’s look at the code implementing the bubble sort algorithm.

C++ Code:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int a[n];
    for(int i = 0 ; i<n ; i++) cin>>a[i];
    for (int i = 0; i < n ; i++) {
        int j = i;
        while (j > 0 && a[j - 1] > a[j]) {
            int temp = a[j - 1];
            a[j - 1] = a[j];
            a[j] = temp;
            j--;
        }
    }
    for(int i = 0 ; i<n ; i++) cout<<a[i]<<" ";
}

JAVA code:  

import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      int n = s.nextInt();
      int a[];
      a = new int[n];
      for(int i = 0 ; i<n ; i++) a[i] = s.nextInt();
      for (int i = 0; i < n ; i++) {
        int j = i;
        while (j > 0 && a[j - 1] > a[j]) {
            int temp = a[j - 1];
            a[j - 1] = a[j];
            a[j] = temp;
            j--;
        }
    }
      for(int i = 0 ; i<n ; i++) System.out.print(a[i]+" ");
  }
}

Python code

n = int(input())
a = []
for i in range(n):
  x = int(input())
  a.append(x)
for i in range(n):
  j = i
  while (j > 0 and a[j - 1] > a[j]):
    temp = a[j-1]
    a[j-1] = a[j]
    a[j] = temp
    j = j-1
for i in range(n):
  print(a[i],end=' ')

Input: 5
         23 56 32 78 12 

Output: 12 23 32 56 78

The time complexity of the code is O(n2) as here we use the nested for loops.
The space complexity of the code is O(1).

ADVANTAGES

• As the insertion sort algorithm is an in-place algorithm, there is no need for extra space.
• The insertion sort algorithm efficiently works over a small set of elements.

Now let’s look at the disadvantages of the bubble sort.

DISADVANTAGES

• The insertion sort algorithm is very less efficient as it uses nested loops which increases the time complexity of the code.
• Performance of the insertion sort algorithm is also based on the ordering of the elements in the list.
• The insertion sort algorithm is less efficient when we use a large number of elements in the data set for sorting.

CONCLUSION

That’s it from this tutorial. Hope you guys found It interesting. We have learned about the insertion sort algorithm, its implementation, advantages and disadvantages of the insertion sort algorithm and we have solved the insertion sort algorithm in different programming languages. Happy coding!