7.1 Description of quicksort

7.1-1

Using figure 7.1 as a model, illustrate the operation of $\text{PARTITION}$ on the array $A = \langle 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 \rangle$.

$$ \begin{aligned} \langle 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 \rangle \\ \langle 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 \rangle \\ \langle 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 \rangle \\ \langle 9, 19, 13, 5, 12, 8, 7, 4, 21, 2, 6, 11 \rangle \\ \langle 9, 5, 13, 19, 12, 8, 7, 4, 21, 2, 6, 11 \rangle \\ \langle 9, 5, 13, 19, 12, 8, 7, 4, 21, 2, 6, 11 \rangle \\ \langle 9, 5, 8, 19, 12, 13, 7, 4, 21, 2, 6, 11 \rangle \\ \langle 9, 5, 8, 7, 12, 13, 19, 4, 21, 2, 6, 11 \rangle \\ \langle 9, 5, 8, 7, 4, 13, 19, 12, 21, 2, 6, 11 \rangle \\ \langle 9, 5, 8, 7, 4, 13, 19, 12, 21, 2, 6, 11 \rangle \\ \langle 9, 5, 8, 7, 4, 2, 19, 12, 21, 13, 6, 11 \rangle \\ \langle 9, 5, 8, 7, 4, 2, 6, 12, 21, 13, 19, 11 \rangle \\ \langle 9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12 \rangle \end{aligned} $$

7.1-2

What value of $q$ does $\text{PARTITION}$ return when all elements in the array $A[p..r]$ have the same value? Modify $\text{PARTITION}$ so that $q = \lfloor (p + r) / 2 \rfloor$ when all elements in the array $A[p..r]$ have the same value.

It returns $r$.

We can modify $\text{PARTITION}$ by counting the number of comparisons in which $A[j] = A[r]$ and then subtracting half that number from the pivot index.

7.1-3

Give a brief argument that the running time of $\text{PARTITION}$ on a subarray of size $n$ is $\Theta(n)$.

There is a for statement whose body executes $r - 1 - p = \Theta(n)$ times. In the worst case every time the body of the if is executed, but it takes constant time and so does the code outside of the loop. Thus the running time is $\Theta(n)$.

7.1-4

How would you modify $\text{QUICKSORT}$ to sort into nonincreasing order?

We only need to flip the condition on line 4.