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

/*
 * double bubble sort
 * DblBubbleSortAlgorithm.java
 */
public class DblBubbleSortAlgorithm extends BubbleSortAlgorithm 
	{
	/* 
	 * This is a generic version of the double (or bidirectional)
	 * bubble sort algorithm.  
	 *
	 * @param a		 an integer array
	 * @param lo	left boundary of array partition
	 * @param hi	right boundary of array partition
	 */
	public void DblBubbleSortAlgorithm(int a[], int lo, int hi)
		throws Exception
		{
		int l = lo;
		int h = hi;
		while ( l < h )
			{
			if (sift (a, l, h, 1) == true)
				break;
			--h;
			++l;
			}
		pause (l, h);
		}

	public boolean sift(int a[], int lo, int hi, int step) throws Exception
		{
		if (siftDown (a, lo, hi, step) == true)
			return true;
		if (siftUp (a, lo, hi-1, step) == true)
			return true;
		return false;
		}

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