import java.util.Arrays;
import java.util.Random;
public class QuickSort {
private static void swap
(Object[] array,
int i,
int j
) {
array[i] = array[j];
array[j] = tmp;
}
private static <E extends Comparable<? super E>> int partition(E[] array, int begin, int end) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++i) {
if (array[i].compareTo(pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private static <E extends Comparable<? super E>> void qsort(E[] array, int begin, int end) {
if (end > begin) {
int index = partition(array, begin, end);
qsort(array, begin, index - 1);
qsort(array, index + 1, end);
}
}
public static <E extends Comparable<? super E>> void sort(E[] array) {
qsort(array, 0, array.length - 1);
}
// Example uses
public static void main
(String[] args
) {
Integer[] l1
= { 5,
1024,
1,
88,
0,
1024 };
QuickSort.sort(l1);
String[] l2
= { "gamma",
"beta",
"alpha",
"zoolander" };
QuickSort.sort(l2);
}
}
Analogously to the Erlang solution above, a user
-supplied
{{Javadoc
:SE
|java
/util
|Comparator}} determines the partial ordering of array elements
:
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
private static void swap
(Object[] array,
int i,
int j
) {
array[i] = array[j];
array[j] = tmp;
}
private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) {
int index = begin + RND.nextInt(end - begin + 1);
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public static <E> void sort(E[] array, Comparator<? super E> cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
//java/4529