import java.util.Random;

/**
 * 
 * @author KAKANAKOU MIGUEL
 *
 */
public final class QuickSort {

	/**
	 * Use the Quicksort method to sort the given array A
	 * 
	 * @param A Array of Comparable that contains the object to sort
	 */
	public static void sort(Comparable[] A) {
		if (A == null)
			return;
		shuffle(A);
		sort(A, 0, A.length - 1);
	}

	private static void sort(Comparable[] A, int lo, int hi) {
		if (lo >= hi)
			return;
		int k = partition(A, lo, hi);
		sort(A, lo, k - 1);
		sort(A, k + 1, hi);
	}

	private static int partition(Comparable[] A, int lo, int hi) {
		int i = lo + 1;
		int j = hi;
		while (true) {
			while ((i < j) && !less(A[lo], A[i]))
				i++;
			while (less(A[lo], A[j]))
				j--;
			if (i >= j)
				break;
			swap(A, i, j);
			i++;
			j--;
		}
		swap(A, lo, j);
		return j;
	}

	private static void shuffle(Comparable[] A) {
		Random rdm = new Random();
		int r = 0;
		for (int i = 0; i < A.length; i++) {
			r = rdm.nextInt(i + 1);
			swap(A, i, r);
		}
	}

	private static void swap(Comparable[] A, int i, int j) {
		Comparable k = A[i];
		A[i] = A[j];
		A[j] = k;
	}

	private static boolean less(Comparable a, Comparable b) {
		int cmp = a.compareTo(b);
		if (cmp < 0)
			return true;
		return false;
	}

	private static boolean equals(Comparable a, Comparable b) {
		int cmp = a.compareTo(b);
		if (cmp == 0)
			return true;
		return false;
	}
}