Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have written 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 can there be any better solution.

share|improve this question
1  
If this is homework, it should be tagged as 'homework'. If it is not homework, then it should be tagged as 'reinventing-the-wheel'. – Mike Nakis Dec 17 '11 at 16:19

2 Answers

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.

share|improve this answer

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;
share|improve this answer
I agree, this does make things harder to follow, although I'm curious... what performance advantage might this have at runtime. I suspect this will result in fewer instructions to execute, is that right? – JoeGeeky Dec 17 '11 at 10:13
2  
I doubt it will have any effect on the runtime. Both the java-to-bytecode compiler and the bytecode-to-machine-code jit of the vm know very well how to optimize simple things like that as best as possible, no matter how you code them. – Mike Nakis Dec 17 '11 at 16:17

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.