## Quicksort

    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.)

• 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?