Insertion Sort in Java

What is Insertion Sort in Java?

To understand the idea behind insertion sort, let's take an example. Assume that you have a randomly shuffled deck of 10 cards, numbered 1 to 10. You need to arrange them based on their value, let's say, in increasing order.

You pick cards one-by-one from the table and place them correctly. Imagine that you chose the first card with a value of 7, which is already at its correct position. Then you take out the second card with a value of 3 and insert it at its suitable position, i.e., before 7. On picking the third with value 8, you insert it just after 7. You place the remaining cards similarly.

Here, you divided the cards into two sets : The set of sorted cards in your hand, and the unsorted one on the table. You pick cards from a randomly shuffled collection and correctly place them in an already sorted set of cards.

Similarly, you would sort a list of values through insertion sort in Java. The list is split, virtually, into a sorted and an unsorted part. The values from the unsorted part are picked and placed in the correct position in the sorted part.

Generally, the insertion sort technique compares each element with all its previous elements and places it in its proper position. But the first element is sorted already, so we start sorting from the second element.

Working of Insertion Sort Algorithm

Insertion Sort algorithm uses the technique of selecting a key in each iteration starting from the second element. Next, we make the proper position available for the key by shifting all the greater elements before it toward their right for sorting in ascending order. Finally, the selected key is stored before the last shifted greater element.

Let's understand this by sorting an array of integers, given as :

1. First Pass :
   Assume the first element is sorted. Store the second element in the key variable. Compare the key with the first element, and place it before the first element if the first element is greater than the key. Do this by shifting elements before the key towards the right in the array.

   

2. Second Pass :
   Now, store the third element in the key and compare it with the values on the left. Shift values more than the key to their right until you find a value smaller than or equal to the key. Store the key just before the last shifted element.

3. Third Pass :
   Do similarly for the fourth element stored in the key.

4. Fourth Pass :
   Finally, you get a sorted array for the fifth element as the key.

   

Insertion Sort Algorithm

The insertion sort in Java can be achieved through the following algorithm :

1. Iterate for index $1$ to $n-1$ of the list.
2. Now, compare the key (element at current index) with the preceding element.
3. If the key is smaller than the preceding element, compare it to other preceding elements. Shift greater elements one position to their right to make space for placing the key in the proper position.

Simple Java Program to Sort an Array Using Insertion Sort Algorithm

Insertion sort program in Java is :

Output :

Explanation :

The first element is already sorted so sorting starts from the second element (index = 1) in the following way :

• Iteration with i = 1 :

  Inside the inner while loop, 11 is compared with 15 (j = 0), 15 is greater so it is shifted one position to the right and you obtain :

  Control moves out of the while loop with j = -1 and the key is stored just before the last shifted number (at j = 0) resulting in :

• Iteration with i = 2 :

  • j = 1, 7 is compared with 15, and 15 is greater so it is shifted to the right.

  • j = 0, 11 is again greater than 7, 11 is shifted to right.

    Control moves out of the while loop with j = -1, and the key is stored at j = 0, so at the end of iteration 2 :

• Iteration with i = 3 :

  • j = 2, 15 is greater than 10, shift it to its right.

  • j = 1, 11 is greater than 10, shift it to its right.

Control moves out of the while loop at j = 0 because 7 is smaller than 10, and the key is stored at j = 1. At the end of iteration 3 :

• Iteration with i = 4 :

  • j = 3, 15 is greater than 9, shift it to its right.

  • j = 2, 11 is greater than 9, shift it to its right.

  • j = 1, 10 is greater than 9, shift it to its right.

Control moves out of the while loop with j = 0 because 7 is smaller than 9 and the key is stored at j = 1. At the end of the fourth and final iteration, we get the sorted array : The sorted array is [7, 9, 10, 11, 15].

Time and Space Complexities

Time Complexities

• Worst Case Complexity :
  For example, when you want to sort an array of numbers in ascending order and the given sequence is in descending order. Each element, in this case, has to be compared with every element to its left. This means for every $n^{th}$ element there are $n-1$ comparisons. So there are total $n(n-1)$ comparisons. For an input size n, the worst-case complexity is $O(n^2)$.

• Best Case Complexity :
  The outer loop runs for $n$ times and the inner loop does not execute at all when the array is already sorted. So for an input size of $n$, the best case complexity is $O(n)$.

• Average Case Complexity :
  When the array elements are randomly placed, then for an input size of $n$, the average case complexity is $O(n^2)$.

Space Complexity

The only extra variable used is storing the key. Therefore, the space complexity is $O(1)$.

Insertion Sort Applications

The Insertion Sort in Java is used for the following scenarios :

• The array has a small number of elements.
• There are only a few elements left to be sorted.
• It is easier to use Insertion sort on the linked list because they contain pointers to the next element (singly linked list) and previous element (doubly linked list).

Learn More

To learn more about Insertion Sort in Java, you can check out this.

FAQs

1. What are the Boundary Cases of the Insertion Sort Algorithm ?

Ans. Insertion Sort in Java takes minimum time when elements are already sorted. It takes maximum time when elements are in reverse order.

2. Which Algorithmic Paradigm Insertion Sort Algorithm Follows ?

Ans. It follows an incremental approach.

3. Can Insertion Sort be Considered an In-place Sorting Algorithm ?

Ans. Yes because no temporary space for the elements is created. All the operations are carried out within the same input.

4. How to Implement Insertion Sort for Linked List ?

Ans. A simple Insertion Sort algorithm for Linked List is :

1. Create an empty sorted list.
2. Traverse the given list, and do the following for every node :
   • Insert the current node in a sorted way in the sorted list.
3. Change the head of the given linked list to the head of the sorted list.

5. Is Insertion Sort a Stable Sorting Algorithm ?

Ans. Yes, Insertion Sort in Java is a stable sorting algorithm because two equal elements appear in the same order in sorted output as they appear in the input array.

6. What are the Applications of the Insertion Sort Algorithm ?

Ans. Use Insertion sort in Java when :

• input size of the list is small, or
• the list is nearly sorted (contains only a few unsorted elements)

7. How to Optimize Insertion Sort Algorithm ?

Ans. Insertion Sort in Java can be optimized so that the number of comparisons reduces. This optimized version is called Binary Insertion Sort, where the Binary Search finds the correct position for the key. This optimizes sorting for each key from $O(i)$ to $O(log(i))$, where $i$ is the current iteration. Irrespective of optimization, it still has worst-case time complexity of $O(n^2)$ because of the number of swaps required while inserting each of the keys.