Insertion Sort in Data Structure

Insertion sort is a sorting algorithm that most of us use in daily life. For example, while arranging a set of answer sheets in ascending order or arranging a deck of cards. After the examination, the answer sheets are collected randomly.

Now, let’s say you need to arrange the answer sheets according to enrolment no. For this, take the first sheet and place it at the first index. Now keep on taking the new sheet and keep it inserting at its correct location in the currently arranged set of sheets. This is how an insertion sort works.

In this article, we will see in detail the working and implementation of insertion sort.

Insertion sort

The array is split into sorted and unsorted parts. The elements from the unsorted part of the array are inserted at the correct position in the sorted part. Hence, the name is insertion sort, since elements are inserted at the correct position.

Insertion sort is a stable algorithm. The same elements in the unsorted dataset appear in the same order in the sorted dataset. It is not suitable for very large datasets.

Insertion Sort Pseudocode

procedure insertionSort( Array )
   int insertposition
   int insertvalue
  
   for i = 1 to length(Array) :
        
      insertvalue = Array[i]
      insertposition = i
      	
      while insertposition > 0 and Array[insertposition-1] > insertvalue:
         Array[insertposition] = Array[insertposition-1]
         insertposition = insertposition -1
      end while

      Array[insertposition] = insertvalue
   end for
end procedure

Insertion Sort Algorithm

Step 1: For i = 1 to n-1
Step 2: Set temp = Array[i]
Step 3: Set j = i - 1
Step 4:  while temp <=Array[j]
             Set Array[j + 1] = Array[j]
             Set j = j - 1
             [end of step 4]
Step 5:  Set Array[j + 1] = temp
             [end of step 1]
Step 6: stop

Working of insertion sort

Let’s Sort the characters in the word “DATAFLAIR” by insertion sort technique.

Iteration 1

Iteration 2

Iteration 3

Iteration 4

Iteration 5

Iteration 6

Iteration 7

Implementation of Insertion Sort in C

#include <stdio.h>

void insertionSort(int array[], int size) 
{
  for (int pos = 1; pos < size; pos++) 
  {
    int val = array[pos];
    int j = pos - 1;

    while (val < array[j] && j >= 0) 
    {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = val;
  }
}

int main() 
{
  int array[] = {54,23,78,92,35,7,84,46,60};
  int len = sizeof(array) / sizeof(array[0]);
  insertionSort(array, len);
  printf("Sorted array:\n");
  for (int i = 0; i < len; i++) 
  {
    printf("%d ", array[i]);
  }
  printf("\n");
}

Insertion Sort Implementation in C++

#include <iostream>
using namespace std;

void insertionSort(int array[], int size) 
{
  for (int pos = 1; pos < size; pos++) 
  {
    int val = array[pos];
    int j = pos - 1;

    while (val < array[j] && j >= 0) 
    {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = val;
  }
}

int main() 
{
  int array[] = {54,23,78,92,35,7,84,46,60};
  int len = sizeof(array) / sizeof(array[0]);
  insertionSort(array, len);
  cout << "Sorted array:\n";
  for (int i = 0; i < len; i++) 
  {
    cout << " " << array[i];
  }
  cout << "\n";
}

Implementation of Insertion Sort in JAVA

public class InsertionSort 
{

  void insertionSort(int array[]) 
  {
    int len = array.length;

    for (int pos = 1; pos < len; pos++) 
    {
      int val = array[pos];
      int j = pos - 1;

      while (j >= 0 && val < array[j]) 
      {
        array[j + 1] = array[j];
        --j;
      }
      array[j + 1] = val;
    }
  }

  public static void main(String args[]) 
{
    int data[] = {54,23,78,92,35,7,84,46,60};

    InsertionSort is = new InsertionSort();
    is.insertionSort(data);

    System.out.println("Sorted Array: ");

    for (int i=0;i<data.length; i++)
    System.out.print(data[i] + " ");
  }
}

Insertion Sort Implementation in Python

def insertionSort(array):

    for position in range(1, len(array)):
        element = array[position]
        j = position - 1
        
        while j >= 0 and element < array[j]:
            array[j + 1] = array[j]
            j = j - 1
        
        array[j + 1] = element

Arr = [54,23,78,92,35,7,84,46,60]
insertionSort(Arr)
print('Sorted Array:')
print(Arr)

Complexity of Insertion Sort

Applications of insertion sort

1. Insertion sort is best suitable for fewer inputs.

2. Also suitable when only a few elements are left for sorting 

Conclusion

Insertion sort is another sorting algorithm suitable for small data sets. We have seen the implementation of insertion sort in different programming languages. We also discussed the working of insertion sort.

Insertion sort can be used in combination with binary search to find the correct position to insert the element in the sorted part. The number of comparisons might reduce but worst-case complexity still remains the same.