This tutorial shows how to write Insertion sort program in Java. Insertion sort is considered the best among the three simple sorting algorithms, the other two simple sorting algorithms are Bubble sort and Selection sort. Though the time complexity of Insertion sort is also O(n2) but it is considered much faster than bubble sort because of less number of swaps and faster than Selection sort in most scenarios.
Insertion sort algorithm
Insertion sort works on the concept of “partially sorted”, at any given point elements on the left hand side of the current index are considered sorted. Note that those elements are considered sorted among themselves as they are not yet at their final position that is why term “partially sorted”. Any remaining element (element at the current index or the remaining elements on the right side) may have to inserted in between the previously sorted elements which will require shifting of the elements to the right to make place for the inserted element.
For example if current index is 3 in an array then element at index 0..2 are considered sorted amongst themselves.
Now element at the current index has to be inserted as the leftmost element means shifting elements at index 0..2 to the right to make place for the insertion making the array as [1 3 5 7 12 10]
Insertion sort example
Here is an example with an array of length 4 to understand insertion sort algorithm. Suppose the passed array is [6, 4, 2, 9].
- In first iteration element at index 1 i.e. 4 is compared with element on its left which is 6. Since 4 is smaller so it has to be inserted at the index 0. To make place for it elements have to be shifted right which temporarily makes the array as [6, 6, 2, 9] then 4 is inserted to make the array as [4, 6, 2, 9] after first iteration.
- In second iteration element at index 2 is compared with elements on its left (index 1 and 0). Since 2 is smaller than 6 so shifting happens making the array temporarily as [4, 6, 6, 9], 2 is smaller then 4 too so again shifting happens making the array temporarily as [4, 4, 6, 9]. Now 2 is inserted to make the array as [2, 4, 6, 9] after second iteration.
- In third iteration element at index 3 is compared with elements on its left (index 2, 1 and 0). Since 9 is greater than all the elements so no swapping required in this iteration. Thus the sorted array is [2, 4, 6, 9].
Insertion sort Java Program
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {25, 34, 10, 7, 15, 92, 53, 72, 39, 45};
System.out.println("Original array- " + Arrays.toString(arr));
int[] sortedArray = insertionSort(arr);
System.out.println("Sorted array- " + Arrays.toString(sortedArray));
}
private static int[] insertionSort(int[] arr){
int j;
for(int i = 1; i < arr.length; i++){
int temp = arr[i];
j = i;
// from current index move left
while(j > 0 && arr[j - 1] > temp){
// shift elements to right
arr[j] = arr[j - 1];
--j;
}
// insert element at the new index position
arr[j] = temp;
}
return arr;
}
}
Output
Original array- [25, 34, 10, 7, 15, 92, 53, 72, 39, 45] Sorted array- [7, 10, 15, 25, 34, 39, 45, 53, 72, 92]
Insertion sort space and time complexity
If you notice the algorithm in first iteration at most 1 comparison is required, in second 2 and for last element at most N-1 comparisons are required making the total number of comparisons as N*(N-1)/2
Thus the average and worst case time complexity for Insertion sort is O(n2).
Insertion sort is an in place sorting algorithm requiring no auxiliary space thus the space complexity of Insertion sort is O(1).
That's all for the topic Insertion Sort Java Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment