How to Write a Java program for Insertion Sort in java?

By | June 9, 2020

Hello Friends,
In this post, we will talk and learn about How to Write a Java program for Insertion Sort in java?

Insertion sort is usually considered good for sorting for a small set of elements. Out of the three simpler sorting algorithms bubble sort, insertion sort, and selection sort insertion sort is considered a better choice in most of the scenarios.

How Insertion sort work?

In insertion sort we take one element at a time and the elements on the left side of the current element are considered temporarily sorted for example if we are at 4th index then elements at index 1 to 3 are sorted among themselves but that is not yet the final position because any other element may have to be inserted in between these temporarily sorted elements, That means elements have to shift right to make a place for the insertion of the element that is why the name insertion sort.

In each iteration, the elements on the left of the current element are sorted and the current element is compared with all the elements on its left, if it is smaller than any of these elements then it has to be inserted at that index and the elements have to be shifted right to make a place for it.

For example, if we have an array [50, 20, 60, 10] then we will start with 20 (2nd element) and compare it with elements on its left.

In the first iteration, 20 is compared with 50. Since it is smaller so it has to be inserted in the place of 50 and other elements have to shift right. Which gives the array as [20, 50, 60, 10] after the first iteration.

In the second iteration, 60 is compared with 50 since 60 is greater than 50 so nothing needs to be done. So array is still [20, 50, 60, 10].

In the third iteration, 10 is compared with 60 since it is smaller so elements have to be shifted right which makes the array as [20, 50, 60, 60]. Note that there are more elements on the left to be compared so 10 is still not inserted as its final insertion point is still not sure at this point.

Then 10 is compared with 50 since 10 is smaller so elements have to be shifted right which makes the array as [20, 50, 50, 60].

Then 10 is compared with 20, since 10 is smaller so elements have to be shifted right which makes the array as [20, 20, 50, 60].

At this point left most index is reached so we know that 1 is the smallest element so it is inserted at this index making the array as [10, 20, 50, 60].

Logic to write the insertion sort is as follows-

We take one element (starting from the second element) at a time starting from left to right in the outer loop. Also, assign this element to a temporary variable.

In the inner loop, which starts at the same number as the outer loop and moves toward left, we compare the temp variable with all the previous elements (element on the left of the current index element).

This comparison goes on until both of these conditions hold true –

Elements on the left side are greater than the element at the current index.

The leftmost element is reached.

In each iteration within this inner loop we also have to shift right by assigning the previous element to the element at the current index within the inner loop.

Below is the complete source code.

Sample input/output of the above program

Enter 6 Array Elements:
123
23
45
67
10
29
Original Array::
[123, 23, 45, 67, 10, 29]
Sorted Array::
[10, 23, 29, 45, 67, 123]

Time and space complexity of Insertion sort:

If you have noticed in the program each time, the number of elements that are to be compared, increases in progression; in the first iteration, only one element has to be compared, in the second iteration two elements have to be compared and so on. That usually makes the Insertion sort time complexity as O(n2).

In the best-case scenario, if the array is already sorted or almost sorted the for loop condition will return false making the time complexity of O(n) if it is already sorted.

Insertion sort is “in place” sorting algorithm because apart from the input array there is no auxiliary space required so the space complexity of Insertion sort is O(1)

You May Also Like:

How to convert number to words in java
How to swap two numbers with or without temporary variable in java
Java Program to Swap two numbers using Bitwise XOR Operator?
How to reverse a number in Java
How to check Armstrong number java program
Java program to find factorial of a number
Java Program to Calculate the Power of a Number?

That’s all about How to Write a Java program for Insertion sort using in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published. Required fields are marked *