Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is an in-place comparison-based sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
Various Sorting Algorithm
- Bubble sort
- Modified Bubble Sort
- Selection sort
- Insertion sort
- Quick sort
- Merge sort
- Heap sort
Insertion Sort
0 I 2 3 4 5 6 7 8 9
50 20 37 91 64 18 43 59 72 81
18 20 37 43 50 69 64 72 81 81
The algorithm is as follows:
- Suppose we have an array of elements to be sorted.
- Iterate from arr[1] to arr[n] over the array.
- Compare the current element (key) to its predecessor.
- If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
- Repeat this process until the entire array is sorted.
Algorithm
The insertion sort algorithm is a simple sorting algorithm that builds the final sorted array one item at a time. It is an in-place comparison-based sorting algorithm. The algorithm works as follows:
- Step 1: Start with the second element (assuming the first element is already sorted).
- Step 2: Compare the current element with the largest value in the sorted portion of the array.
- Step 3: If the current element is greater, move it to the right. Repeat this process until you find the right position for the current element.
- Step 4: Repeat steps 2 and 3 until the entire array is sorted.
Here is the step-by-step algorithm of insertion sort:
Let array be arr[] and its size be n.
Loop from i = 1 to n-1:
a. Pick element arr[i] and
insert it into the sorted sequence arr[0…i-1].
(This step shifts all the
elements greater than arr[i]
to one position ahead.)
Working Of Insertion Sort Algorithm
Sure, let’s go through the working of the Insertion Sort algorithm with an example and corresponding diagrams. Consider the following array:
5,2,4,6,1,3
- Initially, the first element is considered as sorted. Start with the second element, 2.
Compare 2 with 5, since 2<5, we swap them:
2,5,4,6,1,3
Now, consider the third element, 4. Compare it with the elements to its left and swap until it finds the correct position:
2,4,5,6,1,3
Consider the next element, 6. It is greater than all elements to its left, so it remains in its place. The array remains:
2,4,5,6,1,3
Consider 1, swap it until it finds the correct position:
1,2,4,5,6,3
Consider 3, swap it until it finds the correct position:
1,2,3,4,5,6
Each iteration of the algorithm expands the sorted portion of the array until the entire array is sorted.
5, 2, 4, 6, 1, 3 [Initial array]
2, 5, 4, 6, 1, 3 [After the first iteration]
2, 4, 5, 6, 1, 3 [After the second iteration]
2, 4, 5, 6, 1, 3 [After the third iteration]
1, 2, 4, 5, 6, 3 [After the fourth iteration]
1, 2, 3, 4, 5, 6 [After the fifth iteration]
Insertion Sort Complexity
The time complexity of heap sort in different cases along with its space complexity is as follows:
| Case | Time Complexity |
|---|---|
| Best Case | O(n) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
- Best Case Complexity – It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of insertion sort is O(n).
- Average Case Complexity – It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of insertion sort is O(n2).
- Worst Case Complexity – It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of insertion sort is O(n2).
Implementation Of Insertion Sort
Certainly! Below is a simple implementation of the Insertion Sort algorithm in Java:
import java.util.Arrays;
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
System.out.println("Original array: "
+ Arrays.toString(arr));
insertionSort(arr);
System.out.println("Sorted array: "
+ Arrays.toString(arr));
}
}
