In this section of the tutorial, we will discuss the Insertion Sort in Data Structure and its concept and the algorithm of insertion sort for performing different sorting operations in detail. We will understand the working principle behind the Insertion Sort with the help of solving a real world problem.

What is Insertion Sort in Data Structure?

Insertion Sort is one of the most common type of sorting method used in solving Data Structure problems. For example, insertion sort can be used in while playing card game where we can insert a card into a proper sequence in the stack of cards. The concept used in insertion sort is further discussed in detail.

• Insertion sort is used to pick any element that is not in sequence and insert it at a location where it is properly sequenced in a list of elements.
• After every sort pass, one or more elements are inserted in a corrected location in an ordered list.
• There are two categories of insertion sorts in Data Structure, i.e. Straight Insertion Sort and Shell Sort.

Now, we will discuss the concept of Straight Insertion Sort, also known as Insertion Sort in general.

Concept used in Insertion Sort

The core concept of Insertion Sort is similar to the other sorting techniques such as Bubble Sort. Later we pick an element and insert it in a location to make the list sequenced eventually.

We will look into the diagram given below to understand the concepts involved in the Insertion Sort.

The concepts used in the insertion sort is discussed in the points given below.

• Firstly, the entire list is divided into two sublists, i.e. unordered list and ordered list.
• After every sort pass, the first element of the unsorted list is picked and inserted in the sorted list at a sequenced order.
• For n number of elements, the number of sort pass will be n-1.
• There is wall between the sorted and unsorted list which continues to shift from one element to the other until the whole list of elements are sorted.

Now that we are familiar with the core concept used in Insertion Sort, we can write its algorithm to solve a sorting problem.

Insertion Sort Algorithm

Now, we will write the Algorithm of Insertion Sort before we implement it in a programming language to perform operations.

Algorithm Insertion_Sort (list, last)
1 set current to 1
2 loop (till last element is sorted)
    1 move current element to hold
    2 set walker to current - 1
    3 loop (walker >= 0 AND hold key < walker key)
        1 move walker element right one element
        2 decrease walker
    4 end loop
    5 move hold to walker + 1 element
    6 increase current
3 end loop
end Insertion_Sort

• Here, we have to sort the list using insertion sort.
• The array containing the list is divided into two sublists, i.e. unsorted list and sorted list.
• After every sort pass, the first element present in the unsorted list is inserted into the sorted list in a sequenced manner.
• list must contain at least one element in it.
• last specifies the index value to the last element in the list.
• After the n-1 sort passes for n number of elements in the array, the array is sorted.

Working of Insertion Sort

The working of Insertion Sort can be explained by reading the algorithm. Further, when solving a problem based on insertion sort, it becomes more clear that insertion sort works in solving real-world problems.

Likewise, we will try to understand the working of insertion sort using an example given below.

Example:

Suppose we have a list of six numbers(n=6). So, the total number of sort passes will be n-1 = 6-1 = 5. In each sort pass, the wall moves one element to the right because, in each pass, the first element is removed from the sorted list and inserted into the sorted list while maintaining the sequenced form.

Now, we will first understand the example given above in an illustrated example and then we will solve it using insertion sort.

• Here, the design of the insertion sort algorithm is reflected in the sorting technique used.
• After each pass, the outer loop inserts the first element from the unsorted list into the sorted list.
• Then, the inner loop activates inside the sorted list and search for the correct location, from the higher to lower end, to insert the element that maintains the sequence order of the sorted list.

Time and Space Complexity of Algorithm

Insertion Sort Implementation

Now that we understand the concept of Insertion Sort and also we have written the algorithm of Insertion Sort, now we can implement Insertion Sort in a programming language to perform the operation. Here, we will implement Insertion Sort in C and C++.

Implementation in C

Code:

#include<stdio.h>
void InsertionSort(int [] , int);
int main()
{
    int arr[]={8,5,10,54,-1,67,9};
    int n=sizeof(arr)/sizeof(arr[0]);
    InsertionSort(arr, n);
    for(int i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}
void InsertionSort(int arr[], int n)
{
    for(int pos=1; pos<n; pos++)
    {
        int tobesort=arr[pos];
        int j=pos-1;
        while(j>=0 && arr[j]>tobesort)
        {
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=tobesort;
    }
}

Output:

-1 5 8 9 10 54 67

Implementation in C++

Code:

#include<iostream>
using namespace std;
void InsertionSort(int [] , int);
int main()
{
    int arr[]={8,5,10,54,-1,67,9};
    int n=sizeof(arr)/sizeof(arr[0]);
    InsertionSort(arr, n);
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" " ;
    }
    return 0;
}
void InsertionSort(int arr[], int n)
{
    for(int pos=1; pos<n; pos++)
    {
        int tobesort=arr[pos];
        int j=pos-1;
        while(j>=0 && arr[j]>tobesort)
        {
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=tobesort;
    }
}

Output:

-1 5 8 9 10 54 67

In the next section of the tutorial, we will discuss the Shell Sort in Data Structure and its concept and the algorithm of Shell sort for performing different sorting operations in detail. As we have learnt that shell sort if a form of insertion sort, we shall discuss the algorithm and working principle in the same as done in this article using real-world examples.