package org.psjava.algo.sort;

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

import org.psjava.ds.array.ArraySwapper;
import org.psjava.ds.array.MutableArray;

public class RandomizedQuickSort implements Sort {

	// TODO rename to RandomizedQuickSort

	private static Random RANDOM = new Random();

	// TODO do heap sort when level becomes deep

	@Override
	public <T> void sort(MutableArray<T> a, Comparator<T> comparator) {
		sortInRange(a, 0, a.size(), comparator);
	}

	private <T> void sortInRange(MutableArray<T> a, int start, int end, Comparator<T> comp) {
		if (end - start >= 2) {
			int pivotIndex = RANDOM.nextInt(end - start) + start;
			ArraySwapper.swap(a, start, pivotIndex);
			int pos = start;
			for (int i = start + 1; i < end; i++) {
				int c = comp.compare(a.get(i), a.get(start));
				// To prevent big cluster in uniform array, use random.
				if (c < 0 || c == 0 && RANDOM.nextBoolean())
					ArraySwapper.swap(a, i, ++pos);
			}
			ArraySwapper.swap(a, start, pos);
			sortInRange(a, start, pos, comp);
			sortInRange(a, pos + 1, end, comp);
		}
	}

}
@@ -218,48 +218,8 @@
  %7B%0A%0A
-%09// TODO rename to RandomizedQuickSort%0A%0A
 %09pri
@@ -260,16 +260,16 @@
 ndom();%0A
+
 %0A%09// TOD
@@ -548,28 +548,37 @@
 art 
-%3E= 2) %7B%0A%09%09%09int pivot
+%3C= 1)%0A%09%09%09return;%0A%09%09int random
 Inde
@@ -620,17 +620,16 @@
 tart;%0A%09%09
-%09
 ArraySwa
@@ -652,21 +652,22 @@
 rt, 
-pivot
+random
 Index);%0A
 %09%09%09i
@@ -662,17 +662,16 @@
 Index);%0A
-%09
 %09%09int po
@@ -681,17 +681,16 @@
  start;%0A
-%09
 %09%09for (i
@@ -726,17 +726,16 @@
 +) %7B%0A%09%09%09
-%09
 int c = 
@@ -772,17 +772,16 @@
 tart));%0A
-%09
 %09%09%09// To
@@ -831,17 +831,16 @@
 random.%0A
-%09
 %09%09%09if (c
@@ -883,17 +883,16 @@
 ())%0A%09%09%09%09
-%09
 ArraySwa
@@ -917,20 +917,18 @@
 pos);%0A%09%09
-%09
 %7D%0A
-%09
 %09%09ArrayS
@@ -953,25 +953,24 @@
 rt, pos);%0A%09%09
-%09
 sortInRange(
@@ -991,17 +991,16 @@
  comp);%0A
-%09
 %09%09sortIn
@@ -1029,17 +1029,13 @@
  comp);%0A
-%09%09%7D%0A
 %09%7D%0A%0A%7D

make code pretty