Shell Sort - Coursera Algorithms

Shell sort moves entries by more than one position at a time. It is basically insertion sort with a stride length h - it considers h interleaved sequences and sorts them using insertion sort. When the increment(h) is big, the sub-arrays are smaller and when the increment gets shorter in subsequent iterations, the array is already partially sorted. In both cases, insertion sort works great and hence, it's the best option here.

The optimal value for h is provided by Knuth as 3X+1, but no accurate model has been found for this algorithm yet.

It takes O(N3/2) compares in worst case. It's fast unless array size is large and it has less footprint for code. These make it a perfect choice for hardware sort prototype, linux/kernel, embedded systems etc.

Following is the program:

	package sorting.shellSort;
	public class ShellSort {
	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;
	int h=1;
	while(h<n/3) {
	h = 3*h + 1;
	}
	while(h>=1) {
	for(int i=h;i<n;i++) {
	for(int j=i;j>=h && less(a[j],a[j-h]);j-=h) {
	exchange(a,j,j-h);
	}
	}
	h = h/3;
	}
	}
	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 main(String[] args) {
	//Comparable[] a = {5,7,2,4,6,8,1,3,9};
	Comparable[] a = {5,2,4,6,1,3};
	print(a);
	ShellSort insertionSort = new ShellSort();
	insertionSort.sort(a);
	print(a);
	}
	}

view raw ShellSort.java hosted with ❤ by GitHub

Related Posts: 

Insertion Sort