Quicksort Help - Partition

Question

I'm implementing my own quicksort iteratively and with recursion.

It gets the first partition fine where numbers on the right side of pivot are greater than and left side less than.

However my partition doesn't seem to partition the right side and only the left.

int[] data = {3,5,2,7,11,9,1,88,22};

public void qSort(int[] data, int left, int right){
    int pivot = partition(data,left,right);
    pivot = partition(data,pivot,data.length-1); // Test example for right side only
}

public int partition(int[] data, int left, int right){
    int pivot = left;
    left++;

    while (left <= right){
        while ((left <= right) && (data[left] <= data[pivot])) {
            left++;
        }

        while ((left <= right) && (data[right] >= data[pivot])){
            right--;
        }

        if (left < right){
            int temp = data[left];
            data[left] = data[right];
            data[right] = temp;
            left++;
            right--;
        }          
    }

    if (data[right] < data[pivot]){
        int temp = data[right];
        data[right] = data[pivot];
        data[pivot] = temp;
        pivot = right;
    } 

    return pivot;
}

Any help would be appreciated, i'm stumped :(

shizhz shizhz · Accepted Answer · 2017-03-23T06:02:53

Actually your partition implementation works fine, you pass the wrong left parameter to partition in:

pivot = partition(data, pivot, data.length - 1); // Test example for right side only

It should be:

pivot = partition(data, pivot + 1, data.length - 1); // You need to exclude the pivot itself.

Because in your implementation, you choose the left most element as pivot, so if you pass pivot as left parameter when you try to partition the right part, everything will retain the same because it's already partitioned.

Quicksort Help - Partition

1 Answers