Insertion Sort

Real-Life Sorting Algorithm

Insertion Sort is a technique in which a list is virtually split into a sorted and an unsorted part. In each iteration an element from the unsorted part is picked and placed at its correct position in the sorted part.

How does insertion sort work?

• The first element in the list is assumed to be sorted.
• Take the second element and store it in key. Compare key, with the ​​first element. When the first element is greater than the key, the key is placed in front of the first element.
• Take the next element and store it in the key. If the key element is smaller than its predecessor, compare it to the elements before and move greater elements to the right to make space for the key.
• Repeat the above process until it reaches the last element.

Here’s the code:

public static void insertionsort(int[] arr) { // Taking array as parameter
   int i,j; //declaring variables
   int l=arr.length;
   int key;
   for(i=1;i<=l-1;i++) { //Loop for taking elements from unsorted part
     key=arr[i];
     j=i-1;
     //Loop for finding correct position of key in sorted part
     while(j>=0 && arr[j]>key) { 
      arr[j+1]=arr[j];
      j--;
     }
     arr[j+1]=key; 
   }
   
   //printing array after sorting
   System.out.println("array after sorting");
   for(i=0;i<arr.length;i++) {
    System.out.print(arr[i]+" ");
   }
}

Let us take the help of a diagram to understand:

Consider an unsorted array of 5 elements as shown in the picture, we would be sorting this array with the help of insertion sort:

Source

In each pass, the element is placed at its correct position. Source

The number of sorted elements keep on increasing till the entire array is sorted. Source

What do we observe from this example?

If the number of elements to be sorted are n, then the maximum passes required to sort it are n-1.

What are the features of Insertion Sort?

• Insertion Sort is a Stable sorting algorithm because we only move the key forward when the predecessor element is greater than the key so when equal elements are present their relative order is maintained.
• Insertion Sort is an In-place algorithm meaning it does not need an extra space and produces an output in the same memory that contains the data.
• Insertion sort is used when the number of elements required to sort is small. It can also be useful when the input list is partially sorted.
• Worst case time complexity of insertion sort is O(N²).

What are the real-life applications of insertion sort?

• While sorting playing cards we assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right, otherwise, to the left. In the same way, other unsorted cards are taken and are placed in their right place.
• Shirts are always kept in sorted order of size in shops. While inserting new shirts at the right position, other shirts are moved forward to find the right place for a new shirt.

Upcoming topics for the blog:

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.