Skip to content
Advertisement

Why is the pivot element included while sorting the left partition in Quicksort?

I am learning Quicksort from the implementation given in the famous book Cracking the Coding Interview. I understand that the partition function chooses the middle element as the pivot and returns the index where the right partition just starts (inclusive) so the quickSort function will next perform Quicksort recursively on right partition i.e. quickSort(arr, index, right). So far it is good.

The problem is that the left partition now contains the pivot element (at index – 1 location exactly) as well which is already sorted so why is it not doing quickSort(arr, left, index – 2) instead of quickSort(arr, left, index – 1) to skip the pivot element. I tried skipping the pivot but some elements were not sorted properly e.g. with this array: [29, 99, 27, 41, 66, 28, 44, 78, 87, 19, 31, 76, 58, 88, 83, 97, 12, 21, 44]

The complete code is given below:

JavaScript

Advertisement

Answer

The partition function does not necessarily return the index of the pivot. The actual pivot value may be at the left of it or at the right. It really depends when it was encountered and swapped. This can happen some time before left and right cross each other.

For this reason you cannot skip the value at index.

If you want partition to return the index of the pivot value, should swap the pivot value to one side of the current partition before the loop starts, and swap it back into place after the loop finishes — and then you know its index. In that case you can exclude it in the recursive calls. As the pivot value is thus excluded from the loop (unless it is duplicate), the loop condition should be checked at every change of left and right:

JavaScript

The targeted benefit of excluding the value at index from the recursive calls comes with the cost of the extra swaps of the pivot value and more evaluations of the loop condition.

User contributions licensed under: CC BY-SA
8 People found this is helpful
Advertisement