In this tutorial you will learn about insertion sort in Java with example and program.
Insertion Sort Principle
The strategy behind this sorting is much similar to playing cards. In cards playing we used to see that player will hold the cards in sorted manner. Whenever he wants to insert a new card he will put that in such way that again the cards in hand should be in sorted manner only. The below image can illustrate the phenomenon. When he is inserting the card number ‘7’, He is searching for correct position to put it in remaining cards.
Insertion Sort Example
Now we will see insertion sort with one numerical example.
Let us take one array which is having 7 elements for easy understanding. Now we want to sort this array in ascending order. And assume array index is from 0.
Step 1: It will start from second element because first element is only one and it is already sorted. Now consider second element which is at index 1 as key in first pass.
Key: 1
It will start searching from previous index of key to downwards until 0th index.
If elements of input are greater than key then they will be shifted to one index greater.
But we reached 0th index so we will replace 0th index with our key element.
After completing first pass, two elements will be sorted in our array form left to right.
Step 2: It will take 3rd element as key which is at index 2.
Key: 5
It will start searching from 2nd element means index 1 to downwards.
Second element is ‘4’ which is less than that key. We already know that it is sorted sub array. So we need not shift the element. We can put our key in its place only.
After 2nd pass 3 elements will be sorted.
Step 3: In pass 3, key element will be 4th element that means index 3.
Key: 2
Now it will start searching from 3rd element that means index 2 to downwards.
3rd element is 5, it is greater than key so it will shift it to one index greater.
2nd element is 4, it is greater than key so it will shift it to one index greater.
1st element is 1, it is lesser than key so it will stop shifting and it will insert in the 2nd position.
After 3rd pass 4 elements will be sorted.
Step 4: In 4th pass key element will be 4th element.
Key: 3
It will start searching from 4th element that means 3rd index to downwards.
4th element is ‘5’, it is greater than key so it will be shifted to one index greater.
3rd element is ‘4’, it is greater than key so it will be shifted to one index greater.
2nd element is ‘2’, it is lesser than key so we will stop shifting.
Insert the key into the index next to the 2nd element.
After 4th pass 5 elements will be sorted.
Step 5: In 5th pass key is 6th element that means 5th index .
Key: 6
Now we start searching from 5th element means 4th index to downwards.
5th element is 5 which is less than the key so we will stop shifting.
We will insert our key in the next index.
After 5th pass 6 elements will be sorted.
Step 6: In 6th pass, 7th element means which is at index ‘6’ will be key.
Key: 7
It will start searching from 6th element means from index ‘5’ to downwards.
6th element is 6 which is less than the key so we will stop shifting.
We will insert our key in the next index to the index where we stopped shifting.
After 6th pass 7 elements will be sorted.
If total input size is ‘N’ then it will be sorted in ‘N-1’ passes.
Complexity of Insertion Sort Algorithm
It is taking N-1 steps to solve entire array.
In each step it is checking for correct place to insert the key element by comparing. In worst case it is comparing with N-1 elements.
So total time complexity is (N-1)*(N-1) which will give us O(N^2) worst case time complexity.
But in best case means if array is already sorted then it won’t check entire array to place the key. So in best case it is Ω(N).
Now we will see program for insertion sort.
Program for Insertion Sort in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
public class InsertionSort { public void insertionSort(int[] arr) { int i,j,n=arr.length; int key; //this code is for finding correct place to insert key for(i=1;i<n;i++) { key=arr[i]; //it will start searching from previous index to the index of the key j=i-1; //search will be continued until just small element than key is found while(j>=0 && key<arr[j]) { arr[j+1]=arr[j]; j=j-1; } //after finding small element we will insert our key in the next index. arr[j+1]=key; } } public static void main(String args[]) { int a[]={4,1,5,2,3,6,7},i; int n=a.length; InsertionSort obj=new InsertionSort(); System.out.print("before sorting\n"); for (i=0;i<n;i++) { System.out.print(a[i]+" "); } //here we are calling insertion sort on our input array. obj.insertionSort(a); //now our input is sorted using insertion sort System.out.print("\nafter sorting\n"); for (i=0;i<n;i++) { System.out.print(a[i]+" "); } } } |
Output
before sorting
4 1 5 2 3 6 7
after sorting
1 2 3 4 5 6 7
Advantages
- Suits well for smaller inputs. Even asymptotically faster algorithms like merge sort, quick sort also using insertion sort when threshold (reached some small size) is reached to improve performance. Because they have recursion overhead.
- If input is already sorted then it will exhibit best running time.
- It is in place algorithm space efficient.
- Stable algorithm.
Comment below if you have any queries regarding above tutorial for insertion sort in Java.
