public class SortArray
{
	public static void main (String[] args)
	{







	}

	/**
	The algorithm for a selection sort:
	For each array subscript, up to but not including the last,
	find the subscript of the smallest value in the subarray starting at
	subscript anArray[ fill ] and swap it with the one at subscript
	anArray[ fill ].
	*/
	public static void selectionSort(int[] anArray)
	{
		int minPos;
		int temp;
		for( int fill = 0; fill < anArray.length-1; fill++ )
		{
			minPos = fill;
			for( int i = fill; i < anArray.length; i++ )
			{
				if( anArray[ i ] < anArray[ minPos ] )
					minPos = i;
			}
			temp = anArray[ fill ];
			anArray[ fill ] = anArray[ minPos ];
			anArray[ minPos ] = temp;
		}
	}



	/**
	BubbleSort Algorithm
	Beginning at the first element, compare values with the next
	higher element. If the 'left' value is higher, swap the values;
	compare elements 2 to 3, 3 to 4, etc swapping as necessary
	until the largest value is in the last element.
	Repeat for the second largest, third largest, n largest...
	*/
	public static void bubbleSort(int[] anArray)
	{
		//controls passes through the list
		for( int pass = 0; pass < anArray.length-1; pass++ )
		{
			//controls comparisons of elements
			for( int i = 0; i < anArray.length-1-pass; i++ )
			{
				if( anArray[ i ] > anArray[ i + 1 ] )
				{
					//swap values
					int temp = anArray[ i ];
					anArray[ i ] = anArray[ i + 1 ];
					anArray[ i + 1 ] = temp;
				}
			}
		}
	}


	/**
	quickSort is a recursive sort; a method that calls itself
	with a smaller version of the original problem so that,
	eventually, the calls end because the problem is trivial
	and now solved (easily).
	The algorithm places one value in its correct sorted
	location 	with each call to the quickSort method;
	(all values left of it are < and all values right are >;
	this is called partitioning) and then performs the same
	operation on the left subarray ( 0 -> current position -1),
	then on the right subarray (current position +1 -> last);

	To partition the array, the algorithm first compares the
	first value to the last value, if it is smaller, it compares
	the first value to the next to last value, etc until it finds
	a 'left' value greater than the 'right' value; if left is > right,
	swap; if left[position] == right return the present position
	*/
	public static void quickSort(int[] arr, int low, int high)
	{
		// Purpose		:	Sort values using recursion
		// Postcondition:	The array values are sorted.

		int hi = high;
		int lo = low;

		if (high > low)
		{
			// create sub-arrays by placing the first value
			//	in its correct, sorted position in the array.
			int pivot = (high + low)/2;
			int mid = arr[pivot];

			while (lo <= hi)
			{
				while (lo < high && arr[lo] < mid)
				{
					++lo;
				}

				while (hi > low && arr[hi] > mid)
				{
					--hi;
				}

				if (lo <= hi)
				{
					//swap the values
					int temp = arr[lo];
					arr[lo] = arr[hi];
					arr[hi] = temp;
					++lo;
					--hi;
				}
			}

			if (low < hi)
			{
				// call QuickSort on the left sub-array.
				quickSort(arr, low, hi);
			}

			if (lo < high)
			{
				// call QuickSort on the right sub-array.
				quickSort(arr, lo, high);
			}
		}

	}

}