// Example 144 from page 115

//

import java.util.*;

// Generic quicksort in functional style (the most efficient one)

class Example144 {

public static void main(String[] args) {

Integer[] ia = { 5, 7, 3, 9, 12, 45, 4, 8 };

qsort(ia, new IntegerComparator(), 0, ia.length-1);

Example144.<Integer>qsort(ia, new IntegerComparator(), 0, ia.length-1);

Example144.qsort(ia, new IntegerComparator(), 0, ia.length-1);

for (int i : ia)

System.out.print(i + " ");

System.out.println();

String[] sa = { "New York", "Rome", "Dublin", "Riyadh", "Tokyo" };

Example144.qsort(sa, new StringReverseComparator(), 0, sa.length-1);

for (String s : sa)

System.out.print(s + " ");

System.out.println();

}

// Generic functional-style quicksort: sorts arr[a..b]

private static <T> void qsort(T[] arr, Comparator<T> cmp, int a, int b) {

if (a < b) {

int i = a, j = b;

T x = arr[(i+j) / 2];

do {

while (cmp.compare(arr[i], x) < 0) i++;

while (cmp.compare(x, arr[j]) < 0) j--;

if (i <= j) {

T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;

i++; j--;

}

} while (i <= j);

qsort(arr, cmp, a, j);

qsort(arr, cmp, i, b);

}

}

}

// Comparators for Integer and String

class IntegerComparator implements Comparator<Integer> {

public int compare(Integer v1, Integer v2) {

return v1 < v2 ? -1 : v1 > v2 ? +1 : 0;

}

}

class StringReverseComparator implements Comparator<String> {

public int compare(String v1, String v2) {

return v2.compareTo(v1);

}

}