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:
public class Quicksort { public static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static int partition(int[] arr, int left, int right) { int pivot = arr[left + (right - left) / 2]; // Pick a pivot point. Can be an element while (left <= right) { // Until we've gone through the whole array // Find element on left that should be on right while (arr[left] < pivot) { left++; } // Find element on right that should be on left while (arr[right] > pivot) { right--; } // Swap elements, and move left and right indices if (left <= right) { swap(arr, left, right); left++; right--; } } return left; } public static void quickSort(int[] arr, int left, int right) { int index = partition(arr, left, right); if (left < index - 1) { // Sort left half quickSort(arr, left, index - 1); } if (index < right) { // Sort right half quickSort(arr, index, right); } } public static void main(String[] args) { int[] arr = AssortedMethods.randomArray(20, 0, 6); AssortedMethods.printIntArray(arr); quickSort(arr, 0, arr.length - 1); AssortedMethods.printIntArray(arr); } }
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
:
public static int partition(int[] arr, int left, int right) { int mid = left + (right - left) / 2; int pivot = arr[mid]; int store = right--; swap(arr, mid, store); while (left <= right) { if (arr[left] < pivot) { left++; } else if (arr[right] > pivot) { right--; } else if (left < right) { swap(arr, left, right); left++; right--; } else { return left; } } swap(arr, left, store); return left; } public static void quickSort(int[] arr, int left, int right) { if (left < right) { int index = partition(arr, left, right); quickSort(arr, left, index - 1); quickSort(arr, index + 1, right); } }
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.