5
\$\begingroup\$

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?

\$\endgroup\$
10
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – omerkarj Dec 2 '15 at 9:39
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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