# QuickSort of Comparable[]

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?

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;
}

• 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. – omerkarj Dec 2 '15 at 9:39

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.