24
\$\begingroup\$

This is my implementation of quicksort (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.

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;
    }
}
\$\endgroup\$

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

This question came from our site for professional and enthusiast programmers.

  • 4
    \$\begingroup\$ This is O(n log n) not log n \$\endgroup\$ – smohamed Jan 17 '13 at 16:17
  • \$\begingroup\$ It will not scale due to recursion: the JVM has no tail call optimization, it will simply grow the method call stack to something proportional to the array to sort, and it will fail for too large an array. (and even for languages/platforms that do have tail call optimization I don't think they'd be able to actually apply it to this code) \$\endgroup\$ – Shivan Dragon Dec 12 '13 at 15:54
  • \$\begingroup\$ I think it's worth mentioning that the partition method does not make the pivot end to it's final destination, which is different from the classical QuickSort which you can check on wikipedia. \$\endgroup\$ – Ajk_P Oct 2 '14 at 17:39
21
\$\begingroup\$

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...
}
\$\endgroup\$
  • 3
    \$\begingroup\$ +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). \$\endgroup\$ – Eric-Karl Aug 10 '11 at 23:05
8
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

If you try to sort an already-sorted array size over 20000, it will cause a stack overflow. The partition has problems when encountering a large-sized sorted array.

\$\endgroup\$
6
\$\begingroup\$

It looks really good, but I always recommend these guidelines when someone have to code a Quick sort again:

  1. Randomization: random permuting keys can avoid O(n²) when nearly-sorted data.
  2. Median of tree: use the median of first, middle and last elements to select you pivot. The bigger the data, more samples.
  3. Leave small sub-arrays for Insertion sort: finish Quicksort recursion and switch to insertion sort when fewer then 20 elements:

         // Insertion sort on smallest arrays
         if (rangeIndex < 20) {
             for (int i=pivotIndex; i < rangeIndex + pivotIndex; i++)
                 for (int j=i; j > pivotIndex && x[j-1]>x[j]; j--)
                     swap(x, j, j-1);
             return;
         }
    
  4. Do the smaller partition first: only O(logn) of space is needed for the recursion

All this tips come from the excelent book The Algorithm Design Manual, from Steven Skiena.

\$\endgroup\$
3
\$\begingroup\$

I see another improvement. I think it makes more sense to think that the markers (i and j) should move after the swapping is done. It cleans up the code by a few lines and it makes more sense.

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

    int x = a[p];
    int i = p;
    int j = r;

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

        if (i < j) {
            swap(a, i, j);
            i++;
            j--;
        } else {
            return j;
        }
    }
}
\$\endgroup\$

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