Q$5)(25$pts$)$ Come up with a set of $10$ numbers between $1$ and $100,$ let's store these numbers in an array called $\backslash ($ A $\backslash ),$ provide a trace of the call to MaxHeapify $\backslash (($A$,1,10)\backslash ).$ Make sure the set of numbers you chose results in at least $\backslash (\backslash$mathbf$\{2\}\backslash )$ swaps.

Assume you are given a sequence consisting of three types of $\backslash ($ n $\backslash )$ fruits: Apples, oranges, and bananas. The fruits are all mixed in the sequence and we want to order them such that all the apples are at the beginning of the sequence, followed by all the oranges, which are then followed by all the bananas. This arrangement must be done in$-$place, that is you are only allowed to use constant space other than the input sequence containing the fruits. You are allowed to access a fruit at any index i and inspect its type, but you can only do this once. You are also allowed to swap two fruits at any pair of indices i$,$j$.$ Each of these operations cost O$(1)$ time.

$($a$)$ Design an algorithm to do the desired arrangement in $\backslash ($ O$($n$)\backslash )$ time. $($b$)$ Argue why your algorithm has the given bound.

Use only two pointers