Quick Sort Implementation

Question

I have written the below code for quick sort in Java:

void quicksort (int[] a, int lo, int hi)
    {
 //  lo is the lower index, hi is the upper index
 //  of the region of array a that is to be sorted
 int i=lo, j=hi, h;

 // comparison element x
 int x=a[(lo+hi)/2];

 //  partition
 do
 {    
     while (a[i]<x) i++; 
    while (a[j]>x) j--;
    if (i<=j)
    {
        h=a[i]; 
        a[i]=a[j]; 
        a[j]=h;
        i++; 
        j--;
    }
 } while (i<=j);

 //  recursion
  if (lo<j) quicksort(a, lo, j);
 if (i<hi) quicksort(a, i, hi);
}

Please review and possibly offer a better solution.

Answer 1

Some small notes:

1. Instead of commenting here:

   void quicksort (int[] a, int lo, int hi) {
       //  lo is the lower index, hi is the upper index
       //  of the region of array a that is to be sorted
       int i=lo, j=hi, h;
   

   rename the variables:

   void quicksort (final int[] a, final int lowerIndex, final int upperIndex)
   

   It's easier to read.

   (Check Clean Code by Robert C. Martin, page 53-54 also.)

2. Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method.

   (Effective Java, Second Edition, Item 45: Minimize the scope of local variables. (Google for "minimize the scope of local variables", it's on Google Books too.))

3. This:

   h=a[i]; 
   a[i]=a[j]; 
   a[j]=h;
   

   can be extracted out to a swap method:

   public void swap(final int[] arr, final int pos1, final int pos2) {
       final int temp = arr[pos1];
       arr[pos1] = arr[pos2];
       arr[pos2] = temp;
   }
   

4. Maybe you should provide an easier to use helper method too for the clients:

   public void quicksort(final int[] data) {
       if (data == null) {
           throw new NullPointerException("data cannot be null");
       }
       if (data.length == 0) {
           return;
       }
       quicksort(data, 0, data.length - 1);
   }
   

   Note the input validation.

Answer 2

Extract smaller methods

Methods should only do one thing. In other answers it was already pointed out that for example the swapping mechanism can be extracted into its own method. This couldn't be more true, the quicksort method has no business knowing about how to swap two variables in an array.

Variable declaration

Refrain from declaring multiple variables on a single line. It's less readable and you're making one line do multiple things. Declare each variable on its own line.

Give your variables more meaningful names and declare them in the innermost scope possible, as demonstrated by palacsint. Variable names that are only one or two characters long are bad as a rule.

Comments

Do document your code, particularly public or package-restricted methods. See the following example:

/**
 *
 * @param array An array of integers that is to be sorted.
 * @param lowerBound The lower index of the region of the array that is to
 * be sorted.
 * @param upperBound The upper index of the region of the array that is to
 * be sorted.
 */
void quicksort(int[] array, int lowerBound, int upperBound) {

Don't rely on comments to make it clear what your code does. Methods should be short, simple and only do one thing. With the help of meaningful variable and method names and good documentation, it shouldn't be hard to figure out what the method does. You will not need comments.

Brackets

With if-statements or loops that have only one line in their body, it's sometimes tempting to omit brackets. Do use them anyway. It will make your code a few lines longer, but it will help readability. Also, it'll be easier to add more lines to the body afterwards.

Answer 3

You shorten the code a little bit, but it might hurt readability:

    a[i]=a[j]; 
    a[j]=h;
    i++; 
    j--;

    //can be written as:

    a[i++]=a[j]; 
    a[j--]=h;