package sorting;

import java.util.Comparator;
import java.util.Random;

public class QuickSort {
	public static <T> T[] quickSort(T[] array, Comparator<T> comparator) {
		return quickSort(array, 0, array.length - 1, comparator);
	}

	private static <T> T[] quickSort(T[] array, int startIndex, int endIndex,
			Comparator<T> comparator) {
		if (startIndex >= endIndex) {
			return array;
		}

		int length = endIndex - startIndex + 1;
		int randomPivotIndex = new Random().nextInt(length) + startIndex;
		T randomPivot = array[randomPivotIndex];
		int actualPivotIndex = partition(array, startIndex, endIndex,
				randomPivot, comparator);
		array = quickSort(array, startIndex, actualPivotIndex - 1, comparator);
		array = quickSort(array, actualPivotIndex + 1, endIndex, comparator);
		return array;
	}

	public static <T> int partition(T[] array, int startIndex, int endIndex,
			T pivot, Comparator<T> comparator) {
		int nextPivotIndex = -1;
		int nextGreaterIndex = -1;
		int nextIndex = startIndex;

		while (nextIndex <= endIndex) {
			int comparison = comparator.compare(array[nextIndex], pivot);
			if (comparison < 0) {
				if (nextPivotIndex != -1) {
					common.ArrayUtils.swap(array, nextPivotIndex, nextIndex);
					nextPivotIndex++;
				}

				if (nextGreaterIndex != -1) {
					common.ArrayUtils.swap(array, nextIndex, nextGreaterIndex);
					nextGreaterIndex++;
				}
			} else if (comparison == 0) {
				if (nextGreaterIndex != -1) {
					common.ArrayUtils.swap(array, nextIndex, nextGreaterIndex);
					if (nextPivotIndex == -1) {
						nextPivotIndex = nextGreaterIndex;
					}
					nextGreaterIndex++;
				} else if (nextPivotIndex == -1) {
					nextPivotIndex = nextIndex;
				}
			} else if (nextGreaterIndex == -1) {
				nextGreaterIndex = nextIndex;
			}

			nextIndex++;
		}

		return nextPivotIndex;
	}

}

@@ -924,29 +924,24 @@
 int next
-Pivot
 Index = 
 -1;%0A%09%09in
@@ -936,39 +936,18 @@
 x = 
--1;%0A%09%09int nextGreaterIndex = -1
+startIndex
 ;%0A%09%09
@@ -950,32 +950,37 @@
 ;%0A%09%09int next
+Pivot
 Index = 
 startIndex;%0A
@@ -967,26 +967,29 @@
 Index = 
-star
+nex
 tIndex
+ - 1
 ;%0A%0A%09%09whi
@@ -1021,28 +1021,32 @@
 ) %7B%0A
-%09%09%09int comparison = 
+                    if (
 comp
@@ -1088,362 +1088,83 @@
 vot)
-;%0A%09%09%09if (comparison
  %3C
+=
  0) %7B%0A
-%09%09%09%09if (nextPivotIndex != -1) %7B%0A%09%09%09%09%09common.ArrayUtils.swap(array, nextPivotIndex, nextIndex);%0A%09%09%09%09%09nextPivotIndex++;%0A%09%09%09%09%7D%0A%0A%09%09%09%09if (nextGreaterIndex != -1) %7B%0A%09%09%09%09%09common.ArrayUtils.swap(array, nextIndex, nextGreaterIndex);%0A%09%09%09%09%09nextGreaterIndex++;%0A%09%09%09%09%7D%0A%09%09%09%7D else if (comparison == 0) %7B%0A%09%09%09%09if (nextGreaterIndex != -1) %7B%0A%09%09%09%09%09
+                        nextPivotIndex++;%0A                        
 comm
@@ -1189,24 +1189,29 @@
 (array, next
+Pivot
 Index, nextG
@@ -1213,23 +1213,16 @@
 next
-Greater
 Index);%0A
 %09%09%09%09
@@ -1221,275 +1221,50 @@
 x);%0A
-%09%09%09%09%09if (nextPivotIndex == -1) %7B%0A%09%09%09%09%09%09nextPivotIndex = nextGreaterIndex;%0A%09%09%09%09%09%7D%0A%09%09%09%09%09nextGreaterIndex++;%0A%09%09%09%09%7D else if (nextPivotIndex == -1) %7B%0A%09%09%09%09%09nextPivotIndex = nextIndex;%0A%09%09%09%09%7D%0A%09%09%09%7D else if (nextGreaterIndex == -1) %7B%0A%09%09%09%09nextGreaterIndex = nextIndex;%0A%09%09%09%7D%0A%0A%09%09%09
+                    %7D%0A                    
 next
@@ -1309,7 +1309,7 @@
 %0A%09%7D%0A
-%0A
 %7D%0A
+%0A

simplify quick sort's partitioning algorithm.