Quicksort: wikipedia implementation not working

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's an example of what's 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've been looking at this for quite some time and I would really appreciate it if someone could help me figure out where I went wrong :) Thanks!

+3


source to share


1 answer


Two problems:

  • You need to select the rotation value from the section, not just take the first element of the array

  • The last swap must be outside the loop, you put a pivot element on it after you go through the section. See the 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 
}

      

+4


source







All Articles