Insertion Sort
Insertion sort works similar to the sorting of playing cards in hands. In the card game, it is assumed that the first card is already sorted, and then we select an unsorted card.
It will be placed at the right side if the unsorted card is greater than the first; otherwise, it will be placed at the left side. A similar procedure is followed for all unsorted cards.
Insertion sort follows the same approach. In the insertion sort, the idea is to take one element and iterate through the array of elements that are sorted in ascending or descending order.
It is simple to use, but not recommended for large data sets, because time complexity of insertion sort in the average case and worst case is O(n2), where n is the number of elements.
It is less efficient than other sorting algorithms such as heap sort, quick sort, merge sort, etc.
Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(n) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
- Best Case O(n):It occurs when there is no sorting needed, i.e. the array is already sorted.
- Average Case O(n): The array elements are in a jumbled order that is not properly ascending and descending.
- Worst Case O(n): This occurs when the array elements need to be sorted in reverse order. In other words, suppose you have to sort an array in ascending order, but its elements are arranged in descending order.
Space Complexity
| Space Complexity | O(1) |
| Stable | Yes |
- A insertion sort required extra variables for swapping. Hence, the space complexity of insertion sorting is
O(1).
Insertion Sort
#include <stdio.h>
/* function to sort an array with insertion sort */
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int temp = a[i];
int j = i - 1;
/* Move the elements greater than temp to one position ahead from their current position*/
while(j >= 0 && temp <= a[j]) {
a[j+1] = a[j];
j = j-1;
}
a[j + 1] = temp;
}
}
/* function to print the array */
void print(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main() {
int a[] = {50, 20, 32, 13, 30, 18};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
print(a, n);
insertion_sort(a, n);
printf("\nAfter sorting array elements are - \n");
print(a, n);
return 0;
} public class InsertionSort {
/* function to sort an array with insertion sort */
static void insertion_sort(int a[]) {
for (int i = 1; i < a.length; i++) {
int temp = a[i];
int j = i - 1;
/* Move the elements greater than temp to one position ahead from their current position*/
while(j>=0 && temp <= a[j]) {
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
/* function to print the array */
static void print(int a[]) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
}
public static void main(String[] args) {
int a[] = {50, 20, 32, 13, 30, 18};
System.out.println("\nBefore sorting array elements are - ");
print(a);
insertion_sort(a);
System.out.println("\n\nAfter sorting array elements are - ");
print(a);
System.out.println();
}
}