Implement the following algorithms in Java or Python:

$1\mathrm{.}1.$ Selection sort

$1\mathrm{.}2.$ Insertion sort

$1\mathrm{.}3.$ Merge sort

$1\mathrm{.}4.$ Quick sort

$1\mathrm{.}5.$ Heap sort

$2.(5$ points$)$ State their worst$-$case time efficiency using the Big$-\backslash$theta notation.

$3.(5$ points $-1$ point each$)$ Generate random sample inputs $($of integer numbers between $–100$ and

$100)$ of the following sizes:

$3\mathrm{.}1.10000$

$3\mathrm{.}2.20000$

$3\mathrm{.}3.40000$

$3\mathrm{.}4.80000$

$3\mathrm{.}5.160000$

$4.(10$ points$)$ Test the $5$ sorting algorithms on the five input sizes and record the running time $($in

seconds$).$

$5.(5$ points$)$ Repeat steps $3$ and $4$ five times and record the average values of each sorting

algorithm. Do we need this step? Justify your answer.

$6.(10$ points$)$ Report the results in a table. Discuss and analyze them.

$7.(10$ points$)$ Compute the ratio t$(2$n$)/$t$($n$),$ where t is the running time of an algorithm and n is the

input size, for each sorting algorithm and compare it to its corresponding time efficiency. Does it

match? Explain.

$8.(10$ points$)$ Use scatter plots $($as in Chapter $2,$ p$.89$ of our textbook$)$ to help in ascertaining the

algorithm$’$s probable efficiency class. Discuss the plots.