Question $1$

$1pts$

PARtition $(A,p,r)$

$x=A[r],//$ the pivot

$i=p-1\frac{,}{\frac{?}{?}}$ highest index into the low side

for $j=p$ to $r-1\frac{,}{\frac{?}{?}}$ process each element other than the pivot

$,$if $A[j]x\frac{,}{\frac{?}{?}}$ does this element belong on the low side?

$,,i=i+1\frac{,}{\frac{?}{?}}$ index of a new slot in the low side

$,,$exchange $A[i]$ with $A[j]//$ put this element there

exchange $A[i+1]$ with $A[r]//$ pivot goes just to the right of the low side

return $i+1//$ new index of the pivot

partition.jpg

If you apply the PARTITION $(A,1,12)$ algorithm on an array $,117,151,116,176,194,155,$ what value would be returned?

Please note that array A index is $1-$based, meaning the first element has index $1.$