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

/*
 * selection sort
 * SelectionSortAlgorithm.java
 */
public class SelectionSortAlgorithm extends SortAlgorithm 
	{
	/* 
	 * This is a generic version of the selection sort algorithm.  
	 *
	 * Selection sort finds the largest value in the array
	 * and moves it to the bootom of the array.  It then recursively
	 * repeats the process on the rest of the array.
	 * 
	 * @param a		 an integer array
	 * @param lo	left boundary of array partition
	 * @param hi	right boundary of array partition
	 */
	public void SelectionSort (int a[], int lo, int hi) throws Exception
		{
		int h = hi;
		while ( lo < h )
			{
			if (siftDown (a, lo, h, 1) == true)
				break;
			--h;
			}
		}

	public boolean siftDown (int a[], int lo, int hi, int step)
		throws Exception
		{
		int i;
		int maxval = lo;
		boolean sorted = true;

		i = lo+step;
		while ( i <= hi )
			{
			pause (i, hi);
			if ( a[i] > a[maxval] )
				maxval = i;
			else
				sorted = false;
			i += step;
			}
		if (maxval != i-step)
			swap (a, maxval, i-step);

		return sorted;
		} 

	public boolean siftUp (int a[], int lo, int hi, int step)
		throws Exception
		{
		int i;
		int minval = hi;
		boolean sorted = true;

		i = hi-step;
		while ( lo <= i )
			{
			pause (lo, i);
			if ( a[i] < a[minval] )
				minval = i;
			else
				sorted = false;
			i -= step;
			}
		if ( minval != i+step )
			swap (a, i+step, minval);

		return sorted;
		} 

	private void swap(int a[], int i, int j)
		{
		int T;
		T = a[i]; 
		a[i] = a[j];
		a[j] = T;
		}

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