HiveBrain v1.2.0
Get Started
← Back to all entries
snippetjavaMinor

Quick Sort Implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
sortimplementationquick

Problem

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) 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.

Solution

Some small notes:

-
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.)

-
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.))

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


-
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.

Code Snippets

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;
void quicksort (final int[] a, final int lowerIndex, final int upperIndex)
h=a[i]; 
a[i]=a[j]; 
a[j]=h;
public void swap(final int[] arr, final int pos1, final int pos2) {
    final int temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
}
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);
}

Context

StackExchange Code Review Q#6939, answer score: 7

Revisions (0)

No revisions yet.