Quicksort: wikipedia-implementation not working out

Question

I just tried to implement the quicksort algorithm from wikipedia (https://en.wikipedia.org/wiki/Quicksort) but something is missing. Here's my code:

public static void quicksort(int[] a, int lo, int hi) {
    if(lo < hi) {
        int p = partition(a, lo, hi);
        quicksort(a, lo, p - 1);
        quicksort(a, p + 1, hi);
    }
}

public static int partition(int[] a, int lo, int hi) {
    //choose pivot element
    int pivotIndex = 0; 
    int pivotVal = a[pivotIndex];

    //put pivot at the end of array
    swap(a, pivotIndex, hi);

    //compare other elements to pivot and swap accordingly
    int storeindex = lo;
    for(int i = lo; i < hi; i++) {
        if(a[i] <= pivotVal) {
            swap(a, i, storeindex);
            storeindex++;
        }
        //set pivot in right place of array
        swap(a, storeindex, hi);
    }

    return storeindex; //return 
}

public static void swap(int[] a, int place1, int place2) {
    int temp = a[place1];
    a[place1] = a[place2];
    a[place2] = temp;
}

And here is an example of what is going wrong:

 int[] a = {1,2,3,4,5};
 quicksort(a, 0, a.length - 1);

returns: 1, 2, 3, 5, 4 instead of what it should: 1, 2, 3, 4, 5

I have been staring on this for quite a while and I would greatly appreciate if someone could help me figure out where I went wrong :) Thank you!

Sergey Grinev · Accepted Answer · 2015-05-05T19:48:19.127

Two problems:

You need to choose pivot value from partition, not just take first element of an array
Last swap should be outside of the loop, you are putting pivot element to it's place after traversing partition. See last two lines:

enter image description here

Fixed partition method:

public static int partition(int[] a, int lo, int hi) {
    //choose pivot element
    int pivotIndex = lo; // ERROR 1 fixed
    int pivotVal = a[pivotIndex];

    //put pivot at the end of array
    swap(a, pivotIndex, hi);

    //compare other elements to pivot and swap accordingly
    int storeindex = lo;
    for (int i = lo; i < hi; i++) {
        if (a[i] <= pivotVal) {
            swap(a, i, storeindex);
            storeindex++;
        }
    }

    //set pivot in right place of array
    swap(a, storeindex, hi); // ERROR 2 fixed
    return storeindex; //return 
}

Choosing the pivot is actually [an interesting question](http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot) in itself. Always using the first or last element of the partition as pivot will mean worst case performance with sorted/nearly sorted arrays (like the data you are using). — Mick Mnemonic, May 05 '15 at 20:17

Quicksort: wikipedia-implementation not working out

1 Answers1