In this tutorial, we will what is Insertion Sort Algorithm and understand with the a help of a Practical example. Suppose you have a group of students sitting in a classroom. The teacher wants the students to sit as per their heights, so that the shortest person is at the front desk, followed by taller one on the second desk, and so on. A method or technique, which can help in a systematic way to solve this task of arranging the seating of all students, is called the sorting method.

Thus, in general, any methodology which aids in arranging the elements in some order of a given parameter, can be termed a sorting method. There are several different methods, and one of them is ‘Insertion sort‘.

What is Insertion Sort Algorithm [Explained with Practical example]

Also Read: Dynamic Memory Allocation with malloc(), calloc(), free() and realloc() functions in C

Now, suppose all the students were made to sit in increasing order of their height. And a new girl student joins them in the subsequent class. It would now be a waste of time to rearrange all the students again. Better methodology would be to ask the new entrant to find a proper place in the class as per her height. This can be done by comparing her height sequentially with each student already sitting in class. When she finds a person of a height greater than her, she knows that she has to occupy that place. So
she can ask the person at that location to shift one place, and then this new entrant can take up that place. Thus, the new entry is ”inserted” into the proper place in the already sorted data. This logical way of getting a sorted dataset is called the ‘‘insertion sorting” technique.

 

Algorithm

• Input: A list of ”n” elements to be sorted based on their key(k) values. And the order required. i.e., ascending or descending.
• Output: A list of ”n” elements sorted as per the ordering criteria.
• Assume total ”n” data is to be sorted.
• Assume the region storing the data is split into two sub-regions, namely sorted and unsorted.
• Assume, initially, all the data is in the unsorted region.

Algorithm to solve the data in ascending order:-

• If n is ”1”, the sorted and unsorted regions are same. Data is already sorted, so stop. Else go to next step.
• Repeat following steps for elements from 1st element to nth element in sequence.
• Compare the current element (key) to its predecessor.
• If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
• Insert the element in the free space made. And restart from step 2, for next element(if any).

 

Algorithm Trace

Assume there are 5 persons to be arranged in ascending order of their age. The five persons are as follows [teenage boy of 20 age, young boy of age 10, young girl of age 8, aged male of 80 age, infant kid of age 1 year]

The two sections are marked with green background and pink background. The green area indicates the region having all data in that region sorted, while the data(images) in the pink area are not arranged as per their ages.

Step 1:-

Total persons(n)= 5

Initially all the persons are considered unordered. Now the first person is put in the green zone and as he is the only person in that zone, obviously he is in proper place.

Step  2:-

Now the young boy is to be included in the green zone. He is removed from his place. So there are two places to be filled in. The first area is already filled by teenage boy. His age is compared with currently person in that zone i.e. teenage boy. And as his age is small than him, the teenage boy is made to shift one to right empty space. Now as no more persons are in the green zone and free space is found, the boy is placed on that location.

Step 3:-

Next the area of sorted data is considered to be of 3 locations. The third person (girl) is picked out and tried to be placed in appropriate place in this area of 3 places. When girl’s age is compared with last person from her current place, i.e. the teenage boy, as he is having bigger age key value, he is shifted by one location. Continuing, the young boy also is shifted one place and when no more persons to be checked and free space is found, the girl is given the appropriate position in the sorted region of 3 data.

Step 4:-

Next the aged person is the fourth person and his age is compared with the last person to his left, but it is already smaller than his age. So no need to check any more, his place is fixed at current position itself in the sorted zone.

Step 5:-

At end, now the area of sorted is total 5 places. The fifth place is currently taken up by infant. We try to find his proper place and insert him in his appropriate place. So the algorithm compares his age with current latest person on the left of him. i.e the person on fourth place. As infants age is smaller than the fourth age, the data (person) on fourth location is shifted to fifth place. The same process is repeated for other data and all result in same outcome, of shifting the data. Ultimately the 1st place is found which is now vacant, and we assign that place to infant. Now as all five data are in proper places, process stops.

 

Code Snippet

// Insertion sort in C
#include <stdio.h>

// Function to print an element
void displaylistofelements(int element [] , int size) {
   for(int i = 0 ; i < size ; i++) {
      printf (”%d ”, element [i]);
   }
   printf (”\n”);
}
void insertionSort(int element[] , int size , int order) {
   for(int step = 1; step < size; step++) {
      int key = element [step];
      int j = step − 1;
      // Compare key with each element until its proper place is not found
      if (order == 2) // For descending order
      {
        while (key > element [j] && j >= 0) {
        element [j + 1] = element [j] ;
        j=j−1;
      }
    }
    else {// For ascending order
    while (key < element [j] && j >= 0) {
       element [j + 1] = element [j] ;
       j=j−1;
      }
    }
     element [j + 1] = key ;
   }
}
// Driver code
int main() {
    int data[] = {10, 3, 4, 2, 3};
    int order;
    int size = sizeof(data)/sizeof(data[0]) ;
    printf (”Data to be sorted in ascending order(1) or descending order(2) ? Enter your choice (1) or (2)−−>”) ;
    scanf (”%d”,&order) ;
    insertionSort(data, size, order) ;
    if (order == 1)
       printf (”Sorted element in ascending order is :\n”) ;
    else
       printf (”Sorted element in descending order is :\n”) ;
    displaylistofelements(data , size) ;
}

 

Time complexity

To sort an unsorted list with ’n’ number of elements, we need to make (1+2+3+......+n-1) = (n (n-1))/2 number of comparisons in the worst case. If the list is already sorted, then it requires ’n’ number of comparisons.

• Worst Case : O(n2)
• Best Case :Ω(n)
• Average Case :Θ(n2)

 

Conclusion

In this tutorial, we have seen what is Insertion Sort Algorithm and how it works with the help of a practical example. Insertion sort algorithm is known to be the stable algorithm as it does not change the relative order of elements with equal keys. It is known to be more efficient than other sorting algorithms like selection sort or bubble sort. This can be understood from the example and code snippet we saw in this tutorial.