Insertion sort is one of the sorting technique used to sort a data structure like an array.
The general idea of the insertion sort is to partition the array into two parts
- Sorted Partition
- Unsorted Partition.
As the sorting progress, the sorted partition grows and the unsorted portion shrinks. And finally, we get a sorted array.
Insertion Sort Algorithm
At the start. The array is unsorted.
So we assume the first element (array[0]) to be sorted. And the rest of the elements are unsorted. Now we compare the first element (array[0]) with the second element (array[1]) of the array. And arrange them accordingly.
Now we have the first two elements sorted. Again we repeat the process with the third element of the array.
By doing this sorted partition grows and the array gets finally sorted.
C
|
1 2 3 4 5 6 7 8 9 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <stdio.h> #include <stdlib.h> void insertSort(int[], int); void display(int[], int); int main() { int a[] = {8, 36, -51, 9, 21, 46, 2}; // displaying unsorted array printf("Unsorted array \n"); display(a,7); //sorting insertSort(a, 7); //displaying sorted array printf("Sorted array \n"); display(a,7); return 0; } void display(int a[], int size){ int i; for(i=0;i< size;i++){ printf("%d ",a[i]); } printf("\n"); } void insertSort(int a[], int size){ int temp, i, j, pos; for(i=1; i<size; i++){ temp = a[i]; pos = i; for(j=i-1; j>=0; j--){ if(temp < a[j]){ a[j+1] = a[j]; pos = j; } else { pos = j+1; break; } } a[pos] = temp; } } |
Java
|
1 2 3 4 5 6 7 8 9 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
public class InsertionSort { int a[]; public InsertionSort(int[] a) { this.a = a; } public void sort(int a[]){ int temp, i, j, pos; for(i=1; i<a.length; i++){ temp = a[i]; pos = i; for(j=i-1; j>=0; j--){ if(temp < a[j]){ a[j+1] = a[j]; pos = j; } else { pos = j+1; break; } } a[pos] = temp; } } } public class App { public static void main(String args[]){ int a[] = {8, 36, -51, 9, 21, 46, 2}; InsertionSort is = new InsertionSort(a); // displaying unsorted array System.out.println("Unsorted array "); display(a); //sorting is.sort(a); //displaying sorted array System.out.println("Sorted array "); display(a); } private static void display(int[] a) { for(int i=0;i< a.length;i++){ System.out.print(a[i]+" "); } System.out.println(); } } |
Output
|
1 2 3 4 |
Unsorted array 8 36 -51 9 21 46 2 Sorted array -51 2 8 9 21 36 46 |
Insertion Sort Overview
- In-place algorithm (No need of extra arrays).
- O(n²) time complexity – quadratic.
- Stable algorithm (Doesn’t interchange same values in the array).