// Example 128 from page 97

//

// Generic quicksort in object-oriented style

class Example128 {

public static void main(String[] args) {

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

qsort(sa, 0, sa.length-1);

for (String s : sa)

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

System.out.println();

}

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

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

if (a < b) {

int i = a, j = b;

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

do {

while (arr[i].compareTo(x) < 0) i++;

while (x.compareTo(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, a, j);

qsort(arr, i, b);

}

}

}