Insertion Sort - Coursera Algorithms

Insertion Sort swaps an element with a larger entry to it's left.

It take ~1/4 N2 compares and ~1/4 N2 exchanges.
Best case(already sorted) : N-1 compares and zero exchanges.
Worst case(reverse sorted):  ~1/2 N2 compares and ~1/2 N2 exchanges.
Partially sorted(when number of inversions <= cN): linear time as number of exchanges equal the number of inversions.

Following is the program, it also uses shuffle to make the order as random as possible. This is done by swapping each element with a random index r such that r is between 0 and iteration i. This takes linear time.

	package sorting.insertionSort;
	public class InsertionSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	private static boolean isSorted(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	if(less(a[i],a[i-1]))
	return false;
	}
	return true;
	}
	public void sort(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	for(int j=i;j>0;j--) {
	if(less(a[j],a[j-1]))
	exchange(a,j,j-1);
	else
	break;
	}
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {5,2,4,6,1,3};
	shuffle(a);
	print(a);
	InsertionSort insertionSort = new InsertionSort();
	insertionSort.sort(a);
	print(a);
	}
	}

view raw InsertionSort.java hosted with ❤ by GitHub