Java Implementation of Quick Sort

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

    This is O(n log n) not log n

    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)

    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.

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

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

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM