Java Program To Insertion Sort With Example. Shown the example simulation along with the time complexity.
1. Introduction
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much more efficient than Bubble Sort and less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
We can implement Insertion sort using iterative and recursive approach. We will do in this post using Iterative approach. It is easy to understand when compared to recursive.
The insertion sorts repeatedly scans the list of items, each time inserting the item in the unordered sequence into its correct position.
2. Insertion sort Algorithm:
Algorithm is prepared based array and array index starts from 0.
Iterate from index i –> 1 to length -1
Assign key = A[i];
j = i – 1;
Loop j >= 0 and A[j] > key
A[j + 1] = A[j];
j = j – 1;
End Loop
A[j + 1] = key;
End Iterate.
This algorithm works based on cards deck. Pick one card put that card in your hand and pick second card. Then compare second number with first number. If it is greater than first then place second card right side. if less than place second card at left side. Please go through the below example simulation for better understanding.
3. Example Simulation:
A graphical example of insertion sort.
4. Java Program To Insertion Sort
01 02 03 04 05 06 07 08 09 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 | package com.adeepdrive.data.structures.sorting;public class InsertionSortProgram { public static void main(String[] args) { // input array int[] inputArray = { 6, 5, 3, 1, 8, 7, 2, 4 }; int length = inputArray.length; int j = 0; System.out.print("Before Sorting: "); printArray(inputArray); System.out.print("\nValues for each Iteration"); for (int i = 1; i < length; i++) { j = i - 1; int key = inputArray[i]; while (j >= 0 && inputArray[j] > key) { inputArray[j + 1] = inputArray[j]; j = j - 1; } inputArray[j + 1] = key; System.out.println(); printArray(inputArray); } System.out.print("\nAfter sorting: "); printArray(inputArray); } private static void printArray(int[] inputArray) { for (int value : inputArray) { System.out.print(value + " "); } }} |
Output:
Before Sorting: 6 5 3 1 8 7 2 4
Values for each Iteration
5 6 3 1 8 7 2 4
3 5 6 1 8 7 2 4
1 3 5 6 8 7 2 4
1 3 5 6 8 7 2 4
1 3 5 6 7 8 2 4
1 2 3 5 6 7 8 4
1 2 3 4 5 6 7 8
After sorting: 1 2 3 4 5 6 7 8
We are storing current iterating index value in key because if we do swapping value on a condition. In swapping activity, we may loss original value at that index. To avoid loss of data, we store in temporary variable.
In code, We are starting from index 1, ignoring index 0 because index o is already sorted.
i = 1, key = 5
Compare key = 5 with left side values. i.e. 5. condition 6 > 5 –> true. Swap them.
5 6 3 1 8 7 2 4
now i = 2, key = 3
compare key with its left side values and swap them
6 > 3 –> true –> swap –> 5 3 6 1 8 7 2 4
5 > 3 –> true –> swap –> 3 5 6 1 8 7 2 4
now i = 3, key = 1
compare key(1) with its left side values and sort them.
6 > 1 –> true –> swap –> 3 5 1 6 8 7 2 4
5 > 1 –> true –> swap –> 3 1 5 6 8 7 2 4
3 > 1 –> true –> swap –> 1 3 5 6 8 7 2 4
now i = 4, key = 8
compare key(8) with its left side values and sort them.
6 > 8 –> false –> no swap. that means all left side values are already sorted.
now i = 5, key = 7
compare key(7) with its left side values and sort them.
8 > 7 –> true –> swap –> 1 3 5 6 7 8 2 4
6 > 7 –> false –> no swap. All left side values are already sorted.
now i = 6, key 2
compare key(2) with its left side values and sort them.
8 > 2 –> true –> swap –> 1 3 5 6 7 2 8 4
7 > 2 –> true –> swap –> 1 3 5 6 2 7 8 4
6 > 2 –> true –> swap –> 1 3 5 2 6 7 8 4
5 > 2 –> true –> swap –> 1 3 2 5 6 7 8 4
3 > 2 –> true –> swap –> 1 2 3 5 6 7 8 4
1 > 2 –> false –> no swap. that means all left side values are already sorted.
now i = 7, key4
compare key(4) with its left side values and sort them.
8 > 4 –> true –> swap –> 1 2 3 5 6 7 4 8
7 > 4 –> true –> swap –> 1 2 3 5 6 4 7 8
6 > 4 –> true –> swap –> 1 2 3 5 4 6 7 8
5 > 4 –> true –> swap –> 1 2 3 4 5 6 7 8
3 > 4 –> false –> no swap. that means all left side values are already sorted.
Reached end of array and stops processing.
5. Insertion Sort Time complexity:
Worst case Time Complexity: O(n*n)
when all values are not sorted. E.g. 9 8 7 6 5 4 3 2 1
Best case Time Complexity: O(n)
when
all are already input is sorted E.g. 1 2 3 4 5 6 7 8 9
Auxiliary Space: O(1)
6. Insertion Sort Advantages:
The main advantages of the insertion sort are
1) its simplicity.
2) It also exhibits a good performance when dealing with a small list.
3) The insertion sort is an in-place sorting algorithm so the space requirement is minimal.
7. Insertion Sort Disadvantages:
The disadvantages of the insertion sort are
1)It does not perform as well as other, better sorting algorithms.
2) With n-squared steps required for every n element to be sorted, the insertion sort does not deal well with a huge list.
3) Therefore, the insertion sort is particularly useful only when sorting a list of few items.
Published on Java Code Geeks with permission by Venkatesh Nukala, partner at our JCG program. See the original article here: Java Program To Insertion Sort Opinions expressed by Java Code Geeks contributors are their own. |
