Using Figure 7.1 as a model, illustrate the operation of \(\textsc{Partition}\) on the array \(A = \langle 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 \rangle\).
The \(\textsc{Partition}\) procedure selects the last element (11) as the pivot and rearranges the array so that elements smaller than or equal to 11 are on the left, and elements greater than 11 are on the right. Let’s trace through each step of the algorithm.
The procedure maintains two regions: elements at or before index \(i\) are \(\leq 11\), and elements between \(i+1\) and \(j-1\) are \(> 11\). The pointer \(j\) scans through the array from left to right.
Here’s how \(\textsc{Partition}\) processes the array, starting with \(i = 0\), \(j = 1\), and \(x = 11\) (pivot).
The procedure returns \(q = 8\). The final array has all elements \(\leq 11\) in positions 1–7, the pivot 11 in position 8, and all elements \(> 11\) in positions 9–12.