sorting

import java.util.Random;

/**
 * A class defining a number of sorting algorithms.
 *
 * @author fill in your name here
 */
public class SortingAlgorithms {
	int numberOfComparisons;

	public SortingAlgorithms() {
		resetComparisonCounter();
	}

	public void resetComparisonCounter() {
		numberOfComparisons = 0;
	}

	private void increaseComparisonCounter() {
		numberOfComparisons++;
	}

	public int getNumberOfComparisonsMade() {
		return numberOfComparisons;
	}

	private static <T extends Comparable<T>> void exch(T[] array, int a, int b) {
		T temp = array[a];
		array[a] = array[b];
		array[b] = temp;
	}

	private static int charAt(String string, int d){
		if (d < string.length()) return string.charAt(d); else return -1;
	}

	private static Integer[] getArrayOfNSubsequentElements(int n) {
		Integer[] array = new Integer[n];
		for (int i = 0; i < n; ++i)
			array[i] = i;
		return array;
	}

	private <T extends Comparable<T>> boolean less(T v, T w) {
		increaseComparisonCounter();
		return v.compareTo(w) < 0;
	}



	private static <T extends Comparable<T>> void randomPermutation(T[] array) {
		Random randomGenerator = new Random();
		int randomIndex;
		// This loop makes sure we don't leave any elements untouched. Elements
		// can be swapped back to their original position, but that is of course
		// part of randomness.
		for (int i = 0; i < array.length; ++i) {
			randomIndex = randomGenerator.nextInt(array.length);
			exch(array,i,randomIndex);
		}
	}

	private static String[] getMRandomStringsOfLengthN(int m, int n) {
		Random randomGenerator = new Random();
		String output[] = new String[m];
		for (int i = 0; i < m; ++i) {
			String o = "";
			for (int j = 0; j < n; ++j) {
				o += randomGenerator.nextInt(10);
			}
			output[i] = o;
		}
		return output;
	}

	/**
	 * Sorts the given array using selection sort.
	 *
	 * @return The number of comparisons (i.e. calls to compareTo) performed by the algorithm.
	 */
	public <T extends Comparable<T>> int selectionSort(T[] array) {
		int len = array.length;
		for (int i = 0; i < len; i++) {
			int min = i;
			for (int j = i+1; j < len; j++) {
				if (less(array[j],array[min]))
					min = j;
			}
			exch(array, i, min);
		}
		return getNumberOfComparisonsMade();
	}

	/**
	 * Sorts the given array using insertion sort.
	 *
	 * @return The number of comparisons (i.e. calls to compareTo) performed by the algorithm.
	 */
	public <T extends Comparable<T>> int insertionSort(T[] array) {
		int len = array.length;
		for (int i = 1; i < len; i++) {
			for (int j = i; j > 0 && less(array[j], array[j-1]); j--)
				exch(array, j, j-1);
		}
		return getNumberOfComparisonsMade();
	}

	/**
	 * Sorts the given array using (2-way) merge sort.
	 *
	 * HINT: Java does not supporting creating generic arrays (because the compiler uses type erasure for generic types).
	 * For example, the statement "T[] aux = new T[100];" is rejected by the compiler.
	 * Use the statement "T[] aux = (T[]) new Comparable[100];" instead.
	 * Add an "@SuppressWarnings("unchecked")" annotation to prevent the compiler from reporting a warning.
	 * Consult the following url for more information on generics in Java:
	 * http://download.oracle.com/javase/tutorial/java/generics/index.html
	 *
	 * @return The number of comparisons (i.e. calls to compareTo) performed by the algorithm.
	 */
	@SuppressWarnings("unchecked")
	public <T extends Comparable<T>> int mergeSort(T[] array) {
		T[] aux = (T[]) new Comparable[array.length];
		mergeSort(array, aux, 0, array.length - 1);
		return getNumberOfComparisonsMade();
	}

	private <T extends Comparable<T>> void mergeSort(T[] array, T[] aux, int low, int high) {
		if (high <= low) return;
		int mid = low + (high - low)/2;
		mergeSort(array, aux, low, mid);
		mergeSort(array, aux, mid+1, high);
		merge(array, aux, low, mid, high);
	}

	private <T extends Comparable<T>> void merge(T[] array, T[] aux, int low, int mid, int high) {
		int i = low, j = mid + 1;

		for (int k = low; k <= high; k++)
			aux[k] = array[k];

		for (int k = low; k <= high; k++) {
			if (i > mid)
				array[k] = aux[j++];
			else if (j > high)
				array[k] = aux[i++];
			else if (less(aux[j], aux[i]))
				array[k] = aux[j++];
			else
				array[k] = aux[i++];
		}
	}

	/**
	 * Sorts the given array using quick sort. Do NOT perform a random shuffle.
	 *
	 * @return The number of comparisons (i.e. calls to compareTo) performed by the algorithm.
	 */
	public <T extends Comparable<T>> int quickSort(T[] array) {
		quickSort(array, 0, array.length-1);
		return getNumberOfComparisonsMade();
	}

	/**
	 * Sorts the given part of the array using quick sort.
	 *
	 * @return The number of data moves, used for kWayMergeSort.
	 */
	private <T extends Comparable<T>> int quickSort(T[] array, int low, int high) {
		if (high <= low)
			return 0;
		int[] values = partition(array, low, high);
		int j = values[0];
		quickSort(array, low, j-1);
		quickSort(array, j+1, high);
		return values[1];
	}

	private <T extends Comparable<T>> int[] partition(T[] a, int low, int high) {
		int i = low, j = high+1, exch = 0;
		T v = a[low];
		while (true) {
			while (less(a[++i], v))
				if (i == high) break;
			while (less(v, a[--j]))
				if (j == low) break;
			if (i >= j) break;
			exch += 2;
			exch(a, i, j);
		}
		exch += 2;
		exch(a, low, j);
		int[] returnValues = new int[2];
		returnValues[0] = j;
		returnValues[1] = exch;
		return returnValues;
	}

	/**
	 * Sorts the given array using k-way merge sort. The implementation can assume that k is at least 2.
	 * k is the number of the number of subarrays (at each level) that must be separately sorted via a recursive call and merged via a k-way merge.
	 * For example, if k equals 3, then the array must be subdivided into three subarrays that are each sorted by 3-way merge sort. After the 3 sub-
	 * arrays, these sub-arrays are combined via a 3-way merge.
	 *
	 * Note that if k is larger than the length of the array (or larger than the length of a sub-array in a recursive call),
	 * then the implementation is allowed sort that sub-array using quick sort.
	 *
	 * @return An non-null array of length 2. The first element of this array is the number of comparisons (i.e. calls to compareTo) performed by
	 *         the algorithm, while the second element is the number of data moves.
	 */
	@SuppressWarnings("unchecked")
	public <T extends Comparable<T>> int[] kWayMergeSort(T[] array, int k) {
		T[] aux = (T[]) new Comparable[array.length];
		int numberOfMoves = kWayMergeSort(array, aux, k, 0, array.length - 1);
		int[] returnValue = { getNumberOfComparisonsMade(), numberOfMoves };
		return returnValue;
	}

	private <T extends Comparable<T>> int kWayMergeSort(T[] array, T[] aux, int k, int low, int high) {
		int numberOfMoves = 0;
		if (k > (high - low + 1))
			numberOfMoves = quickSort(array, low, high);
		else if (high - low > 1) {
			int position = low, length;
			int[] startingElements = new int[k];
			int[] endElements = new int[k];
			for (int i = k; i > 0; i--) {
				length = (high - position + 1) / i;
				startingElements[k-i] = position;
				numberOfMoves += kWayMergeSort(array, aux, k, position, position + length - 1);
				position = position + length;
				endElements[k-i] = position;
			}
			numberOfMoves += kWayMerge(array, aux, low, high, startingElements, endElements);
		}
		return numberOfMoves;
	}

	private <T extends Comparable<T>> int kWayMerge(T[] array, T[] aux, int low, int high, int[] startingElements, int[] endElements) {
		int numberOfMoves = high - low + 1; // To avoid doing +1 every time in the following loop
		for (int i = low; i <= high; ++i)
			aux[i] = array[i];

		for (int i = low; i <= high; ++i) {
			T valueOfLowest = null;
			int elementCounter = 0;
			for (int j = 0; j < startingElements.length; ++j) {
				int positionInArray = startingElements[j];
				if (positionInArray >= endElements[j])
					continue;
				if (valueOfLowest == null || less(aux[positionInArray], valueOfLowest)) {
					valueOfLowest = aux[positionInArray];
					elementCounter = j;
				}
			}
			numberOfMoves++;
			array[i] = valueOfLowest;
			startingElements[elementCounter]++;
		}
		return numberOfMoves;
	}

	/**
	 * Sorts the given array of strings using LSD sort. Each string in the input array has length W.
	 *
	 * @return the number of arrays accesses performed by the algorithm
	 */
	public int lsdSort(String[] array, int W) {
		int len = array.length;
		int alphabetSize = 256;
		String[] aux = new String[len];
		for (int d = W-1; d >= 0; d--) {
			int[] count = new int[alphabetSize+1];
			for (int i = 0; i < len; i++)
				count[charAt(array[i],d) + 1]++; // charAt() gives the ascii value, so we have to do -48.
			for (int r = 0; r < alphabetSize; r++)
				count[r+1] += count[r];
			for (int i = 0; i < len; i++)
				aux[count[charAt(array[i],d)]++] = array[i];
			for (int i = 0; i < len; i++)
				array[i] = aux[i];
		}
		return len + W * (alphabetSize + len * 2 + alphabetSize * 2 + len * 3 + len * 2);
	}

	/**
	 * Sorts the given array of strings using MSD sort. Do NOT use a cutoff for small subarrays.
	 *
	 * @return the number of characters examined by the algorithm
	 */
	public int msdSort(String[] array) {
		int N = array.length;
		String[] aux = new String[N];
		return msdSort(array, aux, 0, N-1, 0);
	}

	private int msdSort(String[] array, String[] aux, int low, int high, int d) {
		if (high <= low)
			return 0;
		int charsExamined = 0;
		int alphabetSize = 256;
		int[] count = new int[alphabetSize+2];
		for (int i = low; i <= high; i++)
			count[charAt(array[i], d) + 2]++;
		for (int r = 0; r < alphabetSize+1; r++)
			count[r+1] += count[r];
		for (int i = low; i <= high; i++)
			aux[count[charAt(array[i], d) + 1]++] = array[i];
		for (int i = low; i <= high; i++)
			array[i] = aux[i - low];
		charsExamined = (high - low + 1);
		for (int r = 0; r < alphabetSize; r++)
			charsExamined += msdSort(array, aux, low + count[r], low + count[r+1] - 1, d+1);
		return charsExamined;
	}

}