// Sorts.java
// David Kosbie
// Demonstrates various sorting algorithms,
// along with timing and testing code.

import java.util.*;
import static java.lang.System.out;

////////////////////////////////////////
// Sorts:  Main method to test our sorts
////////////////////////////////////////

class Sorts {
	public static void main(String[] args) {
		new SelectionSorter().testSort();
		new InsertionSorter().testSort();
		new BubbleSorter().testSort();
		new FourLineSorter().testSort();
		new MergeSorter().testSort();
		new QuickSorter().testSort();
		new RadixSorter().testSort();
		new HexRadixSorter().testSort();
		new BuiltInSorter().testSort();
	}
}

////////////////////////////////////////
// SelectionSorter
////////////////////////////////////////

class SelectionSorter extends Sorter {
	public void sort(Object[] x) {
		int n = x.length;
		for (int i=0; i<=n-2; i++) {
			int smallestValueIndex = i;
			for (int j=i+1; j<n; j++)
				if (compare(x,j,smallestValueIndex) < 0)
					// we found a new smaller one
					smallestValueIndex = j;
			swap(x,smallestValueIndex,i);
		}
	}       
}

////////////////////////////////////////
// InsertionSorter
////////////////////////////////////////

class InsertionSorter extends Sorter {
	public void sort(Object[] x) {
		int n = x.length;
		for (int i=1; i<n; i++)
			for (int j=i; j>0; j--)
				if (compare(x,j-1,j) > 0)
					swap(x,j-1,j);
				else
					break;
	}
}

////////////////////////////////////////
// BubbleSorter
////////////////////////////////////////

class BubbleSorter extends Sorter {
	public void sort(Object[] x) {
		boolean didSwap;
		int n = x.length;
		do {
			didSwap = false;
			for (int i=0; i<n-1; i++)
				if (compare(x,i,i+1) > 0) {
					swap(x,i,i+1);
					didSwap = true;
				}
		} while (didSwap);
	}
}

////////////////////////////////////////
// FourLineSorter
////////////////////////////////////////

class FourLineSorter extends Sorter {
	public void sort(Object[] x) {
		for (int i=0; i<x.length; i++)
			for (int j=i+1; j<x.length; j++)
				if (compare(x,i,j) > 0)
					swap(x,i,j);
	}
}

////////////////////////////////////////
// MergeSorter
////////////////////////////////////////

class MergeSorter extends Sorter {
	public void sort(Object[] x) {
		Object[] mergeArray = new Object[x.length];
		mergesort(x,0,x.length-1,mergeArray);
	}
	
	private void mergesort(Object[] x, int lo, int hi, Object[] mergeArray) {
		if (lo >= hi)
			// base case -- singleton or null array, so it is sorted
			return;
		// recursive case:  sort left/right halves, then merge
		int mid = (lo + hi)/2;
		mergesort(x,lo,mid,mergeArray);
		mergesort(x,mid+1,hi,mergeArray);
		merge(x,lo,hi,mergeArray);
	}
	
	private void merge(Object[] x, int lo, int hi, Object[] mergeArray) {
		int mid = (lo + hi)/2;
		int i0  = lo;
		int hi0 = mid;
		int i1  = mid+1;
		int hi1 = hi;
		// copy into mergeArray
		for (int i=lo; i<=hi; i++) {
			if ((i0 > hi0) ||
			    ((i1 <= hi1) && (compare(x,i0,i1) > 0)))
			    mergeArray[i] = x[i1++];
			else
				mergeArray[i] = x[i0++];
		}
		// copy back from mergeArray to original array
		for (int i=lo; i<=hi; i++)
			x[i] = mergeArray[i];
	}
}

////////////////////////////////////////
// QuickSorter
////////////////////////////////////////

class QuickSorter extends Sorter {
	public void sort(Object[] x) {
		quicksort(x,0,x.length-1);
	}
	
	private void quicksort(Object[] x, int lo, int hi) {
		if (lo >= hi)
			// base case -- singleton or null array, so it is sorted
			return;
		// recursive case: place pivot in place, then sort left/right halves
		int pivotIndex = lo;
		int left = lo+1;
		int right = hi;
		while (left < right) {
			while ((left < right) && (compare(x,left,pivotIndex) <= 0))
				left++;
			while ((left < right) && (compare(x,right,pivotIndex) > 0))
				right--;
			if (left < right)
				swap(x,left,right);
		}
		// now left == right.  They either met on the rightmost element of the left
		// (which is what we want), or the leftmost element of the right (in which
		// case we'll decrease the pivotIndex by 1).
		if (compare(x,left,pivotIndex) > 0)
			pivotIndex = left-1;
		else
			pivotIndex = left;
		swap(x,lo,pivotIndex);
		// now recursively sort the left/right halves
		quicksort(x,lo,pivotIndex-1);
		quicksort(x,pivotIndex+1,hi);
	}
}

////////////////////////////////////////
// RadixSorter
////////////////////////////////////////

@SuppressWarnings(value={"unchecked"})
class RadixSorter extends Sorter {	
	public void sort(Object[] x) {
		initBuckets(x);
		int digits = findMaxDigits(x);
		for (int digit=0; digit<digits; digit++)
			sort(x,digit);
		// clear out the bucket storage
		buckets = null;
	}
	
	protected int radix = 10;

	// sort the non-negative integers by their "digit"th digit
	private void sort(Object[] x, int digit) {
		// add each element to the appropriate bucket
		for (Object obj : x) {
			Integer i = (Integer) obj;
			int kthDigit = kthDigit(i,digit);
			buckets[kthDigit].add(i);
		}
		// copy from the buckets back into the main array
		int i = 0;
		for (int bucket=0; bucket<radix; bucket++) {
			for (Object obj : buckets[bucket])
				x[i++] = obj;
			buckets[bucket].clear();
		}
	}
		
	// 10 buckets, one for each digit
	private ArrayList[] buckets;
	
	private void initBuckets(Object[] x) {
		buckets = new ArrayList[radix];
		int initialSize = x.length / (radix/2); // so buckets should not be resized...
		for (int i=0; i<radix; i++) buckets[i] = new ArrayList(initialSize);
	}

	private int[] powersOf10;
	
	public RadixSorter() {
		powersOf10 = new int[12];
		int p = 1;
		for (int e=0; e<12; e++) {
			powersOf10[e] = p;
			p *= 10;
		}
	}
	
	// verifies that x contains only non-negative Integers.
	// returns length, in digits, of largest integer, or
	// -1 if there are any illegal values.
	protected int findMaxDigits(Object[] x) {
		Integer max = 0;
		for (Object obj : x) {
			if (! (obj instanceof Integer)) {
				out.println("NON-INTEGER IN RADIXSORT!");
				return -1;
			}
			Integer i = (Integer) obj;
			if (i < 0) {
				out.println("NEGATIVE INTEGER IN RADIXSORT!");
				return -1;
			}
			else if (i > max)
				max = i;
		}
		return max.toString().length();
	}

	// returns the value of the kthDigit, where:
	// kthDigit(123,0) --> 3
	// kthDigit(123,1) --> 2
	// kthDigit(123,2) --> 1
	// kthDigit(123,3) --> 0
	// To find this, divide by 10 k times, then return remainder mod 10:
	protected int kthDigit(int n, int k) {
		n /= powersOf10[k];
		return n % 10;
	}

	protected int kthDigit1(int n, int k) {
		while (k-- > 0) n /= 10;
		return n % 10;
	}
	
	protected int kthDigit2(Integer n, int k) {
		String s = n.toString();
		int len = s.length();
		if (len <= k) return 0;
		return (int)(s.charAt(len-1-k)) - '0';
	}
}

////////////////////////////////////////
// HexRadixSorter
////////////////////////////////////////

@SuppressWarnings(value={"unchecked"})
class HexRadixSorter extends RadixSorter {	
	public HexRadixSorter() {
		radix = 16;
	}
	
	protected int findMaxDigits(Object[] x) {
		int i = super.findMaxDigits(x);
		if (i >= 0) i = 8;
		return i;
	}

	protected int kthDigit(int n, int k) {
		// 1. divide n by 16^k.  But dividing by 16^k is
		// the same as right-shifting by 4*k.
		n = (n >>> (4*k));
		// 2. Take n % 16, but that's just the bottom 4 bits:
		return n & 0xF;
	}
}

////////////////////////////////////////
// BuiltInSorter
////////////////////////////////////////

class BuiltInSorter extends Sorter {
	public void sort(Object[] x) {
		Arrays.sort(x);
	}
}

////////////////////////////////////////
// Sorter
////////////////////////////////////////

@SuppressWarnings(value={"unchecked"})
abstract class Sorter {
	abstract public void sort(Object[] x);

	private static Random random = new Random();

	// creates and sorts a random array of Integers of size "size",
	// and returns the time in milliseconds required to sort	
	public int runTrial(int size) {
		Object[] a = new Object[size];
		for (int i=0; i<size; i++)
			a[i] = new Integer(random.nextInt(Integer.MAX_VALUE));
		Object[] clone = a.clone();
		long time0 = System.currentTimeMillis();
		this.sort(a);
		long time1 = System.currentTimeMillis();

		Arrays.sort(clone);
		if (!Arrays.equals(a,clone)) {
			out.println("SORT FAILED in " + this.getClass());
			out.println("a: " + Arrays.toString(a));
			out.println("clone: " + Arrays.toString(clone));
			System.exit(1);
		}

		return (int) (time1 - time0);
	}
	
	// repeatedly sorts random arrays of size "size" and returns
	// the average cost of one sort in milliseconds.
	public int testSort(int size) {
		final int TEST_TIME = 200; // minimum milliseconds of testing per size
		int totalTime = 0;
		int trials = 0;
		do {
			trials++;
			totalTime += runTrial(size);
		} while (totalTime < TEST_TIME);
		return totalTime / trials;
	}
	
	// verifies that the given array is in fact sorted
	public void verifySorted(Object[] x) {
		for (int i=1; i<x.length; i++)
			if (compare(x,i,i-1) < 0) {
				out.println("SORT FAILED in " + this.getClass());
				System.exit(1);
			}
	}
	
	// repeatedly tests on larger sizes until the time reaches some limit,
	// and prints out a table of the results
	public void testSort() {
		out.println("\nTesting " + this.getClass());
		int time, size = 1000;
		final int TEST_TIME = 2000; // stop when a single test takes this long
		out.printf("%9s %5s\n","size","time");
		do {
			time = testSort(size);
			out.printf("%9d %5d\n",size,time);
			size *= 2;
		} while (time < TEST_TIME);
	}

	// Because it is used by so many sorts, we'll place "swap" here
	// in the shared superclass.
	public void swap(Object[] x, int i, int j) {
		Object temp = x[i];
		x[i] = x[j];
		x[j] = temp;
	}
	
	// Also a convenience, so we do not have to cast to Comparable,
	// and we do not have to suppress unchecked warnings in all subclasses.
	public int compare(Object[] x, int i, int j) {
		return ((Comparable)x[i]).compareTo(x[j]);
	}

}