Shell sort.

0-shellsort.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Shellsort

####Concept

• sequence of H-Sorts (with differing h values) which result in a fully sorted array.
• sequence of h values must be well chosen as it has a significant effect on the runtime and efficiency of the operation

#####Choosing h Formulaic
It is possible to choose a sequence according to a formula. An example of a simple bad choice is sequence that follows the form 2^x (powers of two):

2 4 8 16 ...

There are only even values of h meaning that even values are never compared against odd values.

A better formula, 3x + 1, was proposed by Knuth and produces better values of h.

4 7 10 13 ...

Emperical
A series may also be found empirically/heuristically. Segwick proposed a sequence of h-values was found empirically as:

1, 5, 19, 41, 109, 209, 505, 929...

This sequence is very good in practice.

####Implementation

• loop which changes values of h
• H-Sort implemented in the loop

So Shellsort is relatively easy to program and has very little code all in all. Because of this, Shellsort is often used in hardware and embedded systems where space is still problematic.

####Analysis The mathematical analysis of Shellsort is non-trivial, as it differs with different sequences of h.
Formulaic sequences can sometimes be analyzed e.g. 3x+1 is bounded approximately by O(N^(3/2)).
Emperical sequences can rarely be characterized mathematically, and thus analyzed.

In all, very few h-value sequences in use have proper analysis today. Analysis of Shellsort is still a topic under being researched.

####Verdict Fast and compact, but hard to fully characterize.

1-hsort.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##H-Sort

####Concept

• Insertion Sort of items which are h spaces away.
  • Insertion Sort technically has h = 1 and is also known as a 1-sort
• for h > 1 does not fully sort arrays - used instead to create partially sorted arrays
• methods which work faster on partially sorted arrays - such as Insertion Sort - can then be used to their full potential
  • this then requires multiple passes: h-sort, then the method that uses a partially sorted array

####Implementation

• same as an Insertion Sort, but:
  • the j index is decremented by h each time.

HSort.java

public class HSort{

	public static void sort (Comparable[] a, int h)
	{
		int N = a.length;
		for (int i = 0; i < N; i++){
			for (int j = i; j > h - 1; j -= h){
				if (less(a[j-h], a[j]))
					break;
				exch(a, j-h, j);
			}
		}
	}

	public static boolean less(Comparable a, Comparable b)
	{
		return a.compareTo(b) < 0;
	}

	public static void exch (Comparable[] a, int i, int j)
	{
		Comparable tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	public static void main(String[] args)
	{
		int N = Integer.parseInt(args[0]);
		int h = Integer.parseInt(args[1]);
		Integer[] array = new Integer[N];

		for (int i = 0; i < N; i++){
			array[i] = (int)(Math.random() * 100);
			System.out.print(array[i] + " ");
		}
		System.out.println();

		HSort.sort(array, h);

		for (int i : array)
			System.out.print(i + " ");
		System.out.println();
	}

}

Shell.java

public class Shell{

	public static void sort (Comparable[] a, int[] seq)
	{
		for (int h : seq)
			HSort.sort(a, h);	
	}

	public static boolean isSorted(Comparable[] a)
	{
		for (int i = 1; i < a.length; i++)
			if (HSort.less(a[i], a[i-1]))
				return false;
		return true;
	}

	public static void main(String[] args)
	{
		int N = Integer.parseInt(args[0]);
		Integer[] array = new Integer[N];

		// using Knuth sequence
		// create in descending order
		int x = (N - 1)/3;
		int[] seq = new int[x];

		for (int i = x-1; i >= 0; i--)
			seq[(x-1) - i] = 3*i + 1;

		// create array
		for (int i = 0; i < N; i++){
			array[i] = (int)(Math.random() * 100);
			System.out.print(array[i] + " ");
		}
		System.out.println();

		Shell.sort(array, seq);

		for (int i : array)
			System.out.print(i + " ");
		System.out.println();

		System.out.print(Shell.isSorted(array));
	}

}