CODEWITHSUNDEEP
algorithmsortingquicksort
Joji
Joji

Reputation: 5621

Can someone explain to me this version of quicksort(where pivot is picked in the middle)?

I recently revisited quicksort. I used to do the pivot by picking the last or first item from the list. However the other I came across this snippet where the pivot was picked from the middle. I know that how the pivot is calculated only affects the performance of the algorithm. But I just cannot make sense of this partition algorithm.

I guess the problem for me to understand the partition algorithm is that, I thought it should make the resulting array to be like, all the items smaller than the pivot go to the left and all the items bigger than the pivot go to the right. However this partition algorithm not always achieve that. 

private static void quickSort (int[] array, int left, int right) {
    int index = partition(array, left, right);

    //Sort left half
    if (left < index - 1)
        quickSort(array, left, index - 1);

    //Sort right half
    if (index < right)
        quickSort(array, index , right);
}

private static int partition (int array[], int left, int right) {
    int pivot = array[(left + right) / 2]; //Pick pivot point
    while (left <= right) {
        //Find element on left that should be on right
        while (array[left] < pivot)
            left++;

        //Find element on right that should be on left
        while (array[right] > pivot)
            right--;

        //Swap elements and move left and right indices
        if (left <= right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }
    return left;
}

if I give the partition algorithm an array [1,0,-1,3,5,10,-5], the pivot would be 3, but after the partition the array is [ 1, 0, -1, -5, 5, 10, 3 ]. I just cannot make sense of it because the it doesn't look like the partition is doing anything meaningful. It didn't divide the array into half.

Upvotes: 0

Views: 189

Answers (2)

rcgldr
rcgldr

Reputation: 28828

The code is a variation of Hoare partition scheme where each partition step results in all elements < pivot being to the left of all elements > pivot, but elements == pivot, including the pivot itself, can end up anywhere in the left or right partition, depending on the data pattern. This is why the recursive calls use index-1 and index, since the returned index doesn't correspond to the pivot, so it can't be excluded from the recursive calls.

In the example case, on the first partition step, left is advanced to 3, since array[{0,1,2}] < pivot, and right is not changed, since array[{6}] is not > pivot, resulting in swap(array[3], array[6]), setting array[3] = -5 and array[6] = 3 (the pivot).

Upvotes: 1

Prune
Prune

Reputation: 77837

The pivot is moved to the right, out of the way of the subsequent sorting. The left and right pointers are appropriately adjusted. Reconsider that array in three portions: left, right, and pivot. Rather than

[ 1, 0, -1, -5, 5, 10, 3 ]

you have

[ 1, 0, -1, -5], [5, 10], [ 3 ]

Everything in left is less than the pivot; everything in right is greater.

Upvotes: 0

Related Questions