public static void quicksort(int[] items) {
quicksort(items, 0, items.length - 1);
}
private static void quicksort(int[] items, int left, int right) {
int pivotindex = (left + right) / 2;
// curr will be the final position of the pivot item.
int curr = partition(items, left, right, pivotindex);
if ((curr - left) > 1) {
quicksort(items, left, curr - 1); // Sort left partition
}
if ((right - curr) > 1) {
quicksort(items, curr + 1, right); // Sort right partition
}
}
private static int partition(int[] items, int left,
int right, int pivotindex) {
int pivot = items[pivotindex];
swap(items, pivotindex, right); // Stick pivot at end
pivotindex = right; // remember where it is.
right--;
while (left <= right) { // Move bounds inward until they meet
while (items[left] < pivot) {
left++;
}
while ((right >= left) && (items[right] >= pivot)) {
right--;
}
if (right > left) {
swap(items, left, right); // Swap out-of-place values
}
}
swap(items, left, pivotindex); // Put pivot in place
return left; // Return first position in right partition
}Trace the execution of the partition algorithm (not the quicksort algorithm!) on the following array. Show the state of the array after each swap.
\([3, 9, 2, 64, 8, 11, 21, 1, 7]\)
Here is an example of tracing a full execution of the quicksort algorithm above:
\([4, 9, 8, 10, 3, 11]\)
The star indicates the pivot…
4 9 8* 10 3 11
4 9 11 10 3 8* (swap pivot to end)
4 3 11 10 9 8* (swap 3 and 9)
4 3 8* 10 9 11 (swap pivot back)
/ \
/ \
4* 3 10 9* 11
3 4* 10 11 9*
3 4* 9* 11 10
\
\
11* 10
10 11*
10 11*Show the steps of sorting \([4, 9, 11, 7, 3, 8]\)
Write recurrences expressing both the best-case and worst-case number of comparisons performed by quicksort, assuming that the partition operation requires \(n-1\) comparisons.
Write recurrences expressing both the best-case and worst-case number of array assignments performed by quicksort. (Each swap operation requires two assignments.)
Trace the execution of quicksort on the following array. In this case, the key is the number, and the superscript indicates the record.
\([1^a, 1^b, 1^c, 1^d]\)
How many comparisons did quicksort perform for the previous input. (Don’t try to count. You should be able to determine it analytically.)
Is quicksort stable? Justify your answer.
Recall that merge sort performs exactly \(n\log_2 n - n + 1\) comparisons in the worst case. Which is strictly fewer than the number of comparisons performed by quicksort in the average case: \(A(n) \approx 1.39 (n +1) \log_2 n\). How can quicksort be faster?