/*
 * $Id$
 * $Log$
 */

/*
 * shell sort
 * ShellSortAlgorithm.java
 */
public class ShellSortAlgorithm extends DblBubbleSortAlgorithm 
	{
	/* 
	 * This is a generic version of the shell sort
	 * algorithm.
	 *
	 * Shell sort is a 'meta-algorithm' in the sense that
	 * it manages calls to another sorting procedure which
	 * is efficient on almost-sorted arrays. 
	 * 
	 * @param a		 an integer array
	 * @param lo	left boundary of array partition
	 * @param hi	right boundary of array partition
	 */
	public void ShellSortAlgorithm(int a[], int lo, int hi)
		throws Exception
		{
		int l = lo;
		int h = hi;
		int i;
		int step = 1;

		while ( lo+step <= hi )
			step = 3 * step + 1;

		while ( step > 1 )
			{
			step = step / 3;

			i = 0;
			while ( i < step )
				{
				l = lo+i;
				h = hi;
				while ( l < h )
					{
					if ( sift (a, l, h, step) == true )
						break;
					l += step;
					h -= step;
					}
				++i;
				}
			}
		pause (l, h);
		} 

	public void sort(int a[]) throws Exception
		{
		ShellSortAlgorithm(a, 0, a.length - 1);
		}
	}