The running time of the Quick Sort algorithm depends on the partition function. Consider the general partition algorithm we described, and suppose that we always choose the first element in the sub$-$array, $A[lo],$ as our pivot. Suppose also that we implement the partition algorithm so that the relative order between the elements in each partition is maintained. For example, if elements $x$ and $y$ are less than $A[lo]$ and $x$ occurred before $y$ in the original array, then $x$ occurs before $y$ after the partition step, and they both occur before the pivot. This adaptation does not change the asymptotic running time of the function, but it does change its memory footprint. We are not concerned with that issue here. $($Note that our given code for partition does not maintain the relative order of the elements.$)$

Suppose the array that you would like to sort includes the following elements in some order:

$\left[\begin{array}{ccccccc}75& 73& 59& 40& 47& 4& 8\end{array}\right]$

Give three different arrangments of these elements, each of which would induce worst case running time for quick sort, using our most recent version of partition.

$A=$

$59$

$A=$

$A=$

$73$

$59$

$40$

$8$