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.
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.
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.
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)
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.
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.
Please leave your question in comments box.
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.
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.
Example Simulation:
A graphical example of insertion sort.
Program:
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.
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)
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.
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.
Please leave your question in comments box.
0 Comments