// Arup Guha
// Written on 7/17/07 in BHCSI Intermediate Class
// Illustrates a couple standard sorts.

import java.util.*;

public class sort {

	// Test our sorts.	
	public static void main(String[] args) {
		
		Random r = new Random();
		int[] myvals = randArray(r, 30, 100);
		print(myvals);
		othersort(myvals);
		//print(myvals);
		
	}
	
	// This is an insertion sort. It inserts each value into
	// an already sorted list.
	public static void sort(int[] vals) {
		
		// Insert element i.
		for (int i=1; i<vals.length; i++) {
			
			int spot = i;
			while (spot > 0 && vals[spot] < vals[spot-1]) {
				sort.swap(vals, spot, spot-1);
				spot--;
			}
			print(vals);
		}
	}
	
	// Swaps the values stored in vals[i] and vals[j].
	public static void swap(int[] vals, int i, int j) {
		int temp = vals[i];
		vals[i] = vals[j];
		vals[j] = temp;
	}
	
	// Utility method to print out the contents of an array.
	public static void print(int[] vals) {
		for (int i=0; i<vals.length; i++)
			System.out.print(vals[i]+" ");
		System.out.println();
	}
	
	// Returns the index that stores the maximum value
	// amongst the terms vals[0], vals[1], ..., vals[size-1].
	public static int findMax(int[] vals, int size) {
		
		int maxindex = 0;
		
		for (int i=1; i<size; i++) {
			if (vals[i] > vals[maxindex])
				maxindex = i;
		}
		return maxindex;
	}
	
	// This is a selection sort. It finds the max of the set of
	// unsorte values and moves that into its correct location.
	// It repeats this until the whole list is sorted.
	public static void othersort(int[] vals) {
		
		// Finding the element for index i-1.
		for (int i=vals.length; i>1; i--) {
			int largestindex = findMax(vals, i);
			swap(vals, largestindex, i-1);
			print(vals);
		}
	}
	
	// Returns an array randomly filled with ints of size size
	// with values in between 0 and maxvval-1.
	public static int[] randArray(Random r, int size, int maxval) {
		int[] tmp = new int[size];
		for (int i=0; i<tmp.length; i++)
			tmp[i] = r.nextInt(maxval);
		return tmp;
	}
}