public class QuickSort {
	private static int comparisonCount = 0;
	
	public static void main(String[] args) {
		for (int i = 0; i < args.length; i++) {
			System.out.print(args[i] + " ");
		}
		System.out.println();
		quicksort(args, 0, args.length - 1);
		System.out.println("Comparison count: " + comparisonCount);
		for (int i = 0; i < args.length; i++) {
			System.out.print(args[i] + " ");
		}
	}
	
	public static void quicksort(String[] list, int start, int end) {
		if (end > start) {
			int pivotIndex = (int)(Math.random() * (end - start + 1)) + start;
			int newPivotIndex = partition(list, start, end, pivotIndex);
			quicksort(list, start, newPivotIndex - 1);
			quicksort(list, newPivotIndex + 1, end);
		}
	}
	
	private static int partition(String[] list, int start, int end, int pivotIndex) {
		String pivotValue = list[pivotIndex];
		System.out.print("Pivot: " + pivotValue + " Unsorted: ");
		for (int i = start; i <= end; i++) {
			System.out.print(list[i] + " ");
		}
		swap(list, pivotIndex, end);
		int storeIndex = start;
		for (int i = start; i < end; i++) {
			if (list[i].compareTo(pivotValue) < 0) {
				swap(list, i, storeIndex);
				storeIndex++;
			}
			comparisonCount++;
		}
		swap(list, end, storeIndex);
		System.out.print(" Sorted: ");
		for (int i = start; i <= end; i++) {
			System.out.print(list[i] + " ");
		}
		System.out.println();
		return storeIndex;
	}
	
	public static void swap(String[] list, int first, int second) {
		String temp = list[first];
		list[first] = list[second];
		list[second] = temp;
	}
}