Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
Friendly reminder that java.util.Arrays has an optimized sort method –  abuzittin gillifirca Feb 26 at 14:38
add comment

2 Answers

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;
}
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.