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.
up vote 3 down vote favorite
1

This is my implementation of quick sort (algorithm taken from Cormen book). This is an in place implementation.Please let us know issues with this or any ideas to make it better. It performs at logN at it works.

import java.util.ArrayList;

public class MyQuickSort {

    /**
     * @param args
     */
    public static void main(String[] args) {

        //int[] a = { 1, 23, 45, 2, 8, 134, 9, 4, 2000 };
        int a[]={23,44,1,2009,2,88,123,7,999,1040,88};
        quickSort(a, 0, a.length - 1);
        System.out.println(a);
        ArrayList al = new ArrayList();
    }

    public static void quickSort(int[] a, int p, int r)
    {
        if(p<r)
        {
            int q=partition(a,p,r);
            quickSort(a,p,q);
            quickSort(a,q+1,r);
        }
    }

    private static int partition(int[] a, int p, int r) {

        int x = a[p];
        int i = p-1 ;
        int j = r+1 ;

        while (true) {
            i++;
            while ( i< r && a[i] < x)
                i++;
            j--;
            while (j>p && a[j] > x)
                j--;

            if (i < j)
                swap(a, i, j);
            else
                return j;
        }
    }

    private static void swap(int[] a, int i, int j) {
        // TODO Auto-generated method stub
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
share|improve this question
1  
This is O(n log n) not log n – Sherif Maher Eaid Jan 17 at 16:17

migrated from stackoverflow.com Aug 10 '11 at 18:33

3 Answers

up vote 5 down vote accepted

If the algorithm was taken from a book, then chances are it will be as good as it could possibly be. So as long as you followed it to the letter, there really shouldn't be any issues in your implementation.

There is however one thing I think could be improved upon, the interface to initiate the sort. When I think of sorting a collection, I'd expect to provide a couple of things, the collection of course and possibly a comparer. Anything else that requires passing implementation specific values just feels "wrong" to me. It might be ok if these indices represented the start and stop range of values to sort, but I would still make that as a separate overload.

Your implementation on the other hand requires the collection and indices necessary for the algorithm to work. This would not be an ideal interface to work with since you have to remember to pass in certain values to perform the sort when instead they could be calculated for me. I would expose an overload which only accepts the collection to sort which would call the actual implementation with the right arguments.

Also, even though this is the well known quick sort algorithm, I'd still provide better variable names. Not really a problem here, personal preference.

// this overload is the public interface to do the sort
public static void quickSort(int[] collection)
{
    quickSort(collection, 0, collection.length - 1);
}

// note: method is now private
private static void quickSort(int[] collection, int pivotIndex, int rangeIndex)
{
    // etc...
}
share|improve this answer
+1 for the variable names this would make the code clearer. The code is pretty well separated into functions instead of the usual jumble we often seen (this is directed at no one in particular). – Eric-Karl Aug 10 '11 at 23:05
up vote 1 down vote

I see one small improvement. Instead of...

i++;
while ( i< r && a[i] < x)
  i++;
j--;
while (j>p && a[j] > x)
  j--;

...you can write:

do {
  i++;
} while (i < r && a[i] < x);
do {
  j--;
} while (j > p && a[j] > x);

And Jeff is right about the public interface.

share|improve this answer
up vote 0 down vote

try to sort a already sorted array size over 20000, it will stackoverflow... the partition has problems when encounter large size sorted array...

share|improve this answer

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.