CLRS Solutions | Exercise 7.1-4

How would you modify $\textsc{Quicksort}$ to sort into nonincreasing order?

To sort in nonincreasing (descending) order instead of nondecreasing (ascending) order, we need to change how $\textsc{Partition}$ divides elements around the pivot. The key is to reverse the comparison in the partitioning step.

The standard $\textsc{Partition}$ places elements $\leq pivot$ on the left and elements $> pivot$ on the right. For nonincreasing order, we want elements $\geq pivot$ on the left and elements $< pivot$ on the right.

This requires changing only one character in the $\textsc{Partition}$ procedure:

$$\textsc{Partition}'(A, p, r)$$$$\begin{aligned} 1& \quad x\,=\,A[r] \\ 2& \quad i\,=\,p\,-\,1 \\ 3& \quad \textbf{for }\,j\,=\,p\textbf{ to }\,r\,-\,1 \\ 4& \quad \qquad \textbf{if }\,A[j]\,\geq\,x\quad \textbf{/\!/} \text{ Changed}\,\text{ from}\,\text{ ≤}\,\text{ to}\,\text{ ≥}\, \\ 5& \quad \qquad \qquad i\,=\,i\,+\,1 \\ 6& \quad \qquad \qquad \text{exchange}\,A[i]\,\text{with}\,A[j] \\ 7& \quad \text{exchange}\,A[i + 1]\,\text{with}\,A[r] \\ 8& \quad \textbf{return }\,i\,+\,1 \\ \end{aligned}$$

The $\textsc{Quicksort}$ procedure itself remains completely unchanged:

$$\textsc{Quicksort}(A, p, r)$$$$\begin{aligned} 1& \quad \textbf{if }\,p\,<\,r \\ 2& \quad \qquad q\,=\,\textsc{Partition}'(A, \, p, \, r) \\ 3& \quad \qquad \textsc{Quicksort}(A, \, p, \, q - 1) \\ 4& \quad \qquad \textsc{Quicksort}(A, \, q + 1, \, r) \\ \end{aligned}$$

For example, with the array $\langle 2, 8, 7, 1, 3, 5, 6, 4 \rangle$ and pivot 4, the modified partition places elements $\{8, 7, 5, 6\}$ (those $\geq 4$) on the left and $\{2, 1, 3\}$ (those $< 4$) on the right, with 4 in between. Recursive sorting then produces the final nonincreasing sequence $\langle 8, 7, 6, 5, 4, 3, 2, 1 \rangle$.