QuickSort of Comparable[]

Question

Here is the code for the QuickSort class that I created.

public class QuickSort {
 public static void sort(Comparable[] a) {
 quicksort(a, 0, a.length-1);
 }
 private static void quicksort(Comparable[] a, int lo, int hi) {
 if(lo >= hi) return;
 int pi = partition(a, lo, hi);
 quicksort(a, lo, pi-1);
 quicksort(a, pi+1, hi);
 }
 private static int partition(Comparable[] a, int lo, int hi) {
 int i = lo + 1;
 int j = hi;
 while(i <= j) {
 if(a[i].compareTo(a[lo]) <= 0) { 
 i++; 
 }
 else if(a[j].compareTo(a[lo]) > 0) { 
 j--;
 }
 else if(j < i) {
 break;
 }
 else
 exchange(a, i, j);
 }
 exchange(a, lo, j);
 return j;
 }
 private static void exchange(Object[] a, int i, int j) {
 Object tmp = a[i];
 a[i] = a[j];
 a[j] = tmp;
 }
}

The code passed some simple tests (including duplicate values). I wonder is any bug in my code? Anywhere to improve?

• abuzittin gillifirca: Friendly reminder that java.util.Arrays has an optimized sort method

Answer 1

Javadoc on every method would be nice.

Change signature to <T extends Comparable<T>> void sort(T[] a).

public static void sort(Comparable[] a) {

Standard method to specify ranges is from inclusive to exclusive.

 quicksort(a, 0, a.length - 1);
}
private static void quicksort(Comparable[] a, int lo, int hi) {

Why not "high" and "low"?

 if (lo >= hi) {

Your code never invokes quicksort with lo > hi. You'd better throw an IllegalArgument exception in this case.

 return;
 }
 int pi = partition(a, lo, hi);
 quicksort(a, lo, pi - 1);
 quicksort(a, pi + 1, hi);
}
private static int partition(Comparable[] a, int lo, int hi) {
 int i = lo + 1;
 int j = hi;

You choose the first element as pivotal. Choosing as a pivot the element at a constant position allows construction of an antitest, an array on which your sort works in O(n^2). In your particular case, the antitest is pretty simple - an array in descending order, e.g. (5, 4, 3, 2, 1).

 while (i <= j) {
 if (a[i].compareTo(a[lo]) <= 0) {
 i++;
 } else if (a[j].compareTo(a[lo]) > 0) {
 j--;
 } else if (j < i) {
 break;
 } else {
 exchange(a, i, j);
 }
 }
 exchange(a, lo, j);
 return j;
}

It's better to name it swap.

private static void exchange(Object[] a, int i, int j) {
 Object tmp = a[i];
 a[i] = a[j];
 a[j] = tmp;
}

• omerkarj: Very nice answer by abra. for future reference, the most important issue here is the O(n^2) time complexity - because of the pivot selection.

Answer 2

Just three quick notes:

1. You could fix the compiler warnings with the following method declarations:

   public static <T extends Comparable<T>> void sort(T[] a)
   private static <T extends Comparable<T>> void quicksort(T[] a, int lo, int hi)
   private static <T extends Comparable<T>> int partition(T[] a, int lo, int hi)
   

2. I'd rename a to input or data for better readability.

3. exchange is usually called swap. I think more developers would find familiar the latter.