/*
 * Created on Aug 4, 2005
 * 
 * CPS 006 - Summer 05
 * Sam Slee
 * Selection.java
 * 
 * 
 */

public class Selection {

	//---------------------------------------------------------------------------------
	// Demonstrates the Selection Sort algorithm.
	public static void main(String[] args) {
		int[] random = {8, 36, 27, 25, 15, 13, 19, 5, 9, 34, 10, 11, 7, 
				33, 6, 30, 14, 3, 18, 22, 32, 16, 1, 20, 24, 
				26, 2, 4, 17, 23, 29, 31, 12, 21, 28, 35};

		int[] reverse = {36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25,
				24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
				12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		
		int[] input = random;
		int goal = 0;
		
		System.out.println("Array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
		
		System.out.println("\n\nSorting with Selection Sort \n");
		
		selectionSort(input);
		
		System.out.println("Sorted array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
	}
	
	
	//---------------------------------------------------------------------------------
	// Sorts the given array entries in ascending order
	// using Selection Sort - O(n^2) time
	public static void selectionSort(int[] input){
		
		int minIndex;		// index of entry holding min. value in a given search 
		int temp;			// temporary holding variable for swaps
		int sortedIndex=0;	// all array entries before this index are sorted
		
		// find the proper value to go in
		// all "n" array entries
		for(int i=0; i<input.length; i++){
			
			minIndex = sortedIndex;
			
			// find the proper value to go into the array
			// entry we're currently working on (input[sortedIndex])
			for(int j=sortedIndex+1; j<input.length; j++){
				if(input[j] < input[minIndex])
					minIndex = j;
			}
			
			//swapping the next minimum value into the next sorting spot
			temp = input[sortedIndex];
			input[sortedIndex] = input[minIndex];
			input[minIndex] = temp;
			
			// updating so that we can look at the next index
			// on the next loop through
			sortedIndex++;
		}
	}
}