$1.$ Given the array $\{9,20,14,17,85,3,21,6,4,10\}$ determine the number of comparisons used by:

$$ Bubble Sort

$$ Insertion Sort

$$ Selection Sort

$$ Merge Sort

$$ Quick Sort

$$ Heap Sort

$2.$ Prove that the worst case runtime of any comparison$-$based $($i$.$e$.,$ the only

operations allowed on array elements are comparing two elements and assigning elements$)$ sorting algorithm is $($n lg n$).($This means that the worst case

runtime of any comparison$-$based sorting algorithm cannot be made better than

n lg n$.)$

$3.$ Suppose you have a list of n integers where each integer is guaranteed to be

between $1$ and $100,$ inclusive. Devise an algorithm to sort this list in O$($n$)$ time.

$4.$ In our linear selection algorithm, the input elements are divided into groups

of $5.$ Would the algorithm still run in linear time we divided them into groups

of $7?$ What about $3?$

$5.$ Give a simple algorithm that will find the smallest and largest elements of

an array using at most $3$n$/22$ comparisons, where n is the length of the array.

www