First we need to take out one marker element(index:1) and then we need to compare this with left side element. if left side element is higher than marker element then we need to shift the positions. same way we need to continue this process for remaining elements(2,3...n-1) . So after each pass the left hand side will be in sorted order.
package com.algorithms.sorting;
public class InsertionSort {
public int[] sort(int[] arr) {
for (int step = 1; step < arr.length - 1; step++) {
int marker = arr[step];
int index = step;
while(index>0 && arr[index-1]>marker){
arr[index] = arr[index-1];
index--;
}
arr[index] = marker;
}
return arr;
}
public static void display(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
public static void main(String[] args) {
int[] arr = { 299, 499, 199, 10,2,300,400};
System.out.println("before sorting:");
display(arr);
new BubbleSort().sort(arr);
System.out.println("");
System.out.println("after sorting:");
display(arr);
}
}
Time complexity:
on worst case scenario we need
1 comparison in first pass and 2 comparisons in second pass.
Total number of comparisons is = 1 + 2+ 3+4+....n-1 = n * (n-1)/2.
So in average case total number of comparisons = n * (n-1)/4
Insertion sort complexity is O(N square).
In Insertion sort we are not doing swaps. We are doing copy operations, generally copy operation is not expensive when compared with swap operation.
Also if the data is already sorted or almost sorted then in each pass we need only comparison, because while loop condition fails.
In this case complexity is O(N)