// Arup Guha
// 2/19/2016
// Solution to Junior Knights Java Assignment from 2/12/2016

import java.util.*;

public class sort {

	private int[] array;
	private static Random r = new Random();

	// Creates a sort object with len elements each in between 1 and max, inclusive.
	// Initial object is unsorted.
	public sort(int len, int max) {

		// Allocate space for the array.
		array = new int[len];

		// Fill each array slot with a random number from 1 to max.
		for (int i=0; i<array.length; i++)
			array[i] = r.nextInt(max) + 1;
	}
	
	// Returns true iff this sort object is sorted.
	public boolean isSorted() {
		for (int i=0; i<array.length-1; i++)
			if (array[i] > array[i+1])
				return false;
		return true;
	}

	// Returns a string representation of this object, each item followed by a space.
	public String toString() {
		String res = "";
		for (int i=0; i<array.length; i++)
			res = res + (array[i]+" ");
		return res;
	}

	public void bubbleSort() {

		// i represents how far to run a single pass of bubble sort.
		for (int i=array.length-1; i>0; i--) {

			// j represents the left index of each successive battle.
			for (int j=0; j<i; j++) {
				if (array[j] > array[j+1]) {
					int temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				}
			}
		}
	}

	public void insertionSort() {

		// i represents the current item to be inserted. array[0..i-1] is already sorted.
		for (int i=1; i<array.length; i++) {

			// j represents the location of the inserted item as it hops left.
			int j = i;
			while (j > 0 && array[j] < array[j-1]) {
				int temp = array[j];
				array[j] = array[j-1];
				array[j-1] = temp;
				j--;
			}
		}
	}

	public void selectionSort() {

		// We seek the location of the maximum item from index 0 through index i.
		for (int i=array.length-1; i>0; i--) {

			// maxIndex represents the index of the largest value we've seen so far.
			int maxIndex = 0;
			for (int j=1; j<=i; j++)
				if (array[j] > array[maxIndex])
					maxIndex = j;

			// Swap max element in sublist into place.
			int temp = array[i];
			array[i] = array[maxIndex];
			array[maxIndex] = temp;
		}
	}

	public static void main(String[] args) {
	
		// Basic tests - you can avoid printing when testing larger arrays.

		// Test bubble.
		sort test1 = new sort(20, 100);
		System.out.println(test1);
		test1.bubbleSort();
		if (!test1.isSorted())
			System.out.println("Test failed!");
		System.out.println(test1);
		System.out.println();
		
		// Test insertion.
		sort test2 = new sort(20, 100);
		System.out.println(test2);
		test2.insertionSort();
		if (!test2.isSorted())
			System.out.println("Test failed!");
		System.out.println(test2);		
		System.out.println();
		
		// Test selection.
		sort test3 = new sort(20, 100);
		System.out.println(test3);
		test3.selectionSort();
		if (!test3.isSorted())
			System.out.println("Test failed!");
		System.out.println(test3);

		/*** Various other tests.
		 
		sort small = new sort(10, 100);
		small.print();
		sort medium = new sort(25, 1000);
		medium.print();
		sort large = new sort(100, 1000000);
		large.print();
		System.out.println();

		small.bubbleSort();
		small.print();
		medium.print();
		System.out.println();

		medium.insertionSort();
		large.selectionSort();
		medium.print();
		large.print();

		for (int len=1000; len<=80000; len=len+1000) {

			long start = System.currentTimeMillis();
			sort test = new sort(len, 1000000);
			test.bubbleSort();
			long end = System.currentTimeMillis();
			System.out.println("size = "+len+" time = "+(end-start)+" ms.");
		}

		***/
	}
}