#$2)$ Study algorithm $8\mathrm{.}3\mathrm{.}1$ & Figure $8\mathrm{.}3\mathrm{.}2,$ illustrate execution of the

inPlacePartition Algorighm on the list:

$\{12,36,17,86,50,32,15,46,30\}.$

Algorithm $8\mathrm{.}3\mathrm{.}1$: In$-$place randomized quick$-$sort for an array, S$.$

Algorithm inPlacePartition $(S,a,b)$ :

Input: An array, $S,$ of distinct elements; integers a and $b$ such that $ab$

Output: An integer, $l,$ such that the subarray $S[a..b]$ is partitioned into $1$ and $S[l..b]$ so that every element in $S[a..l-1]$ is less than each element in $S[l..b]$

Let $r$ be a random integer in the range $a,b$

Swap $S[r]$ and $S[b]$

plarrS$[b],//$ the pivot

llarra$\frac{,}{\frac{?}{?}}l$ will scan rightward

rlarrb$-1\frac{,}{\frac{?}{?}}r$ will scan leftward

while $lr$ do $//$ find an element larger than the pivot

while $lr$ and $S[l]p$ do

llarrl$+1$

while $rl$ and $S[r]p$ do $//$ find an element smaller than the pivot rlarrr$-1$

if $S[l]S[r]S[l]S[b],l(S,a,b)SabS[a..b]a$bllarr$(S,a,b)(S,a,l-1)(S,l+1,b)TTTl$ then

Swap $S[l]$ and $S[r]$

Swap $S[l]$ and $S[b],\frac{?}{?}$ put the pivot into its final place return $l$

Algorithm inPlaceQuickSort $(S,a,b)$ :

Input: $An$ array, $S,of$ distinct elements; integers a and $b$

Output: The subarray $S[a..b]$ arranged $in$ nondecreasing order

$ifab$ then return$\frac{\frac{?}{?}}{s}$ubrange with $0or1$ elements

llarr inPlacePartition $(S,a,b)$

inPlaceQuickSort $(S,a,l-1)$

inPlaceQuickSort $(S,l+1,b)$

Like merge$-$sort, $we$ can visualize quick$-$sort using a binary recursion tree, called the quick$-$sort tree. Figure $8\mathrm{.}3\mathrm{.}2$ visualizes the quick$-$sort algorithm, showing example input and output sequences for each node $of$ the quick$-$sort tree.

Figure $8\mathrm{.}3\mathrm{.}2$: Quick$-$sort tree $T$ for $an$ execution $of$ the quick$-$sort algorithm $on$ a sequence with eight elements: $(a)$ input sequences processed $at$ each node $ofT$; $(b)$ output sequences generated $at$ each node $ofT.$ The pivot used $at$ each level $of$ the recursion $is$ shown $in$ bold.