Insertion Sort
Insertion Sort
Insertion sort is one of the simplest method to sort an array. In this method the element are inserted at their appropriate place .Hence is the name insertion sort.
An example of an insertion sort occurs in evryday life while playing cards. To sort the card in your hand you extract a card. shift the remaining cards. And then insert the extracted card in the correct place.This process repeated until all the cards are in the correct sequence.
Algorithm of Insertion sort
insertionSort(array)
mark first element as sorted
for each unsorted element X
'extract' the element X
for j <- lastSortedIndex down to 0
if current element j > X
move sorted element to the right by 1
break loop and insert X here
end insertionSort
Working of Insertion sort algorithm
Suppose the elements of array are –
Firstly, the first two elements are compared im sort.
Here, 12 is smaller than 31. That is both elements are in ascending order. So, 12 is stored in a sorted sub-array.
Now, move to the next 2 elements and compare between them.
Here, 31 is greater than 25. So, 31 is at incorrect position. Now, replace 31 with 25. Along with swapping, it will check it with all elements in the sorted array.
For now, the sorted array has only one element, i.e. 12. So, 12 is smaller than 25. So, the sorted array remains sorted after the swapping.
Now, 2 elements in the sorted array are 12 and 25. Move forward to the next elements 31 and 8.
Both 31 and 8 are unsorted. So, swap them.
After swapping, elements 25 and 8 are not sorted.
So, swap them.
Now, elements 12 and 8 are not sorted.
So, swap this two elemnt
Now, the sorted array has three elements that are 8, 12 and 25. Move to the next element they are 31 and 32.
Hence, they are already sorted. Now, the sorted array contains 8, 12, 25 and 31.
Move forward to the next elements they are 32 and 17.
32 is greater than 17. So, swap them.
Swapping makes 31 and 17 not sorted. So, swap the both element.
Now, swapping makes 25 and 17 not sorted. So, perform swapping.
Now, the array is completely sorted.
Insertion sort complexity
1. Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(n) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
2. Space Complexity
| Space Complexity | O(1) |
| Stable | YES |
Program of insertion sort in C
#include <stdio.h>
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
void insertionSort(int arr[], int size) {
for (int step = 1; k < size; k++) {
int key = array[k];
int j = k - 1;
// For descending order, change key<arr[j] to key>arr[j].
while (key < arr[j] && j >= 0) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
// Driver code
int main() {
int data[] = {9, 5, 1, 4, 3};
int size = sizeof(data) / sizeof(data[0]);
insertionSort(data, size);
printf("Sorted array in ascending order:\n");
printArray(data, size);
}
Output
Sorted array in ascending order: 1 3 4 5 9
Program of insertion sort in C++
#include <iostream>
using namespace std;
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void insertionSort(int arr[], int size) {
for (int k = 1; k < size; k++) {
int key = arr[k];
int j = k - 1;
// For descending order, change key<arr[j] to key>arr[j].
while (k < arr[j] && j >= 0) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
// Driver code
int main() {
int data[] = {9, 5, 1, 4, 3};
int size = sizeof(data) / sizeof(data[0]);
insertionSort(data, size);
cout << "Sorted array in ascending order:\n";
printArray(data, size);
}
Output
Sorted array in ascending order: 1 3 4 5 9
Program of insertion sort in Python
def insertionSort(array):
for step in range(1, len(array)):
key = arr[k]
j = k - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
data = [9, 5, 1, 4, 3]
insertionSort(data)
print('Sorted Array in Ascending Order:')
print(data)
Output
Sorted Array in Ascending Order: [1, 3, 4, 5, 9]
Program of insertion sort in Java
import java.util.Arrays;
class InsertionSort {
void insertionSort(int arr[]) {
int size = arr.length;
for (int k = 1; k < size; k++) {
int key = arr[k];
int j = k - 1;
// For descending order, change key<arr[j] to key>arr[j].
while (j >= 0 && key < arr[j]) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
// Driver code
public static void main(String args[]) {
int[] data = { 9, 5, 1, 4, 3 };
InsertionSort is = new InsertionSort();
is.insertionSort(data);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}
Output
Sorted Array in Ascending Order: [1, 3, 4, 5, 9]