Problem $7$: $[8$ points$]$

Improved Selection Sort

The Selection Sort algorithm can be optimized by tracking both the minimum and maximum elements in a single pass. This allows you to sort two elements with each iteration, effectively reducing the number of passes needed through the array. The number of swaps can also be reduced by performing a swap only at the end of each outer loop iteration and if it is needed.

a$.(3$ points$)$ Implement the improved Selection Sort algorithm on a randomly generated list of $n$ integers. Measure the sorting time using and submit your code.

b$.(3$ points$)$ Measure and record the sorting time for the following input sizes for the selection sort and the improved selection sort algorithms. Take the average of at least $5$ measurements for each value of $n.$

$\backslash$table$[[n,100,500,1000,5000,10000,50000,100000,500000],[$Random order,,,,,,,,$],[$Increasing order,,,,,,,,$],[$Decreasing order,,,,,,,,$]]$

c$.(2$ points$)$ Plot a graph of the data you collected in part b for the two algorithms and discuss the results.