/*
 * Demo of Selection Sort
 */
public class SelectionSortDemo {

	public static void main(String[] args) {
		Integer[ ] list1 = { 
				new Integer( 8), 
				new Integer( 6),
				new Integer(11),
				new Integer( 3),
				new Integer(15),
				new Integer( 5)
		};
		String[ ] list2 = {
				"Carol",
				"Bob",
				"Ted",
				"Alice",
				"Schultzie"
		};
		selectionSort( list1 );		// sort list 1
		print( list1 );
		
		selectionSort( list2 );		// sort list 2
		print( list2 );
	}
	
	/**
	 * Print an array a
	 */
	public static void print( Object[ ] a ) {
		for ( int i = 0; i < a.length; i++ )
			System.out.print( a[i] + "  " );
		System.out.println( );
	}
	
	/**
	 * Sort an array a in increasing order
	 */
	public static void selectionSort( Comparable[ ] a ) {
		for ( int i = 0; i < a.length; i++ ) {
			int j = indexOfMin( i, a );
			swap( i, j, a );
		}
	}
	
	/**
	 * Returns the index of the smallest value among
	 * a[start], a[start+1], ...
	 */
	private static int indexOfMin( int start, Comparable[ ] a ) {
		Comparable min = a[start];
		int minIndex = start;
		for ( int i = start + 1; i < a.length; i++ )
			if ( a[i].compareTo(min) < 0 ) {
				min = a[i];
				minIndex = i;
			}
		return minIndex;
	}
	
	/** 
	 * Swap a[i] with a[j]
	 */
	private static void swap( int i, int j, Comparable[ ] a ) {
		Comparable temp;
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}