Implement the heap$-$sort algorithm. Experimentally compare its running time with insertion sort and the built$-$in Python sorted function. Similar to what did before, you could use dummy functions with O$($n$^2)$ and O$($nlogn$)$ and use them as benchmarks in your graph.

Submission: $1)$ A graph showing the curves for heap$-$sort, insertion sort and built$-$in the sorted function. $2)$ code that generates the data used in the graph.

Tip: create three functions where each would do its sorting algorithm $-$ heap$-$sort algorithm, insertion sort and built$-$in Python sorted function. Three functions would take the same list n and sort it$.$

Ch$9$ Implementation: You would time each function for the same input argument list. You would also have same lists being passed to three functions to sort them. You would also have several lists of different size e$.$g size $3$ to $3000$ but also with different random values in them e$.$g$.$ from $0$ to $10000($Show that increase of list size follows a time$-$complexity increase of Big O$).$ You can automate creation of lists through a custom loop that would be appending a new random value to the list that and be passed to three function for that you can use random python library.

This way, for each sorting you would time and collect the data. Then you would do the same for the increased size list $(+1).$ You would repeat it for all the lists with sizes and plot three lines from the collected data. It would show different time complexity increase O$($n$^2)$ and O$($nlogn$)$

Note $-$ This is an extension of Programming Project $2.$ Submit several files, so I expect two files, one $.$py that would plot the graph

You need to have a code that would plot a graph showing three different lines showing the running time of a heap$-$sort function, Insertion sort and the inbuilt Python sorted function.

I have included the code below for my previous program that is contuning on with this project.

#TO CREATE A LIST OF SIZE

def calculate$\_$sort$\_$time$($size$\_$of$\_$list$)$:

random$\_$records $=[$random$.$randint$(0,25000)$ for $\_$ in range$($size$\_$of$\_$list$)]$

#TIME TAKEN TO SORT THE LIST

beginning$\_$time $=$ time.time$()$

categorized$\_$files $=$ sorted$($random$\_$records$)$ #COMPILE THE LIST AND ORGANIZE THE LIST

finished$\_$time $=$ time.time$()$

return finished$\_$time $-$ beginning$\_$time

def main$()$:

#ARRAY FOR SIZES

sizes $=$ range $(20,20000,10000)$ #LIST SIZE FROM $20$ TO $20000$

#ARRAY FOR TIME

times $=[]$

for size in sizes:

bulk$\_$time $=$ calculate$\_$sort$\_$time$($size$)$

times.append$($bulk$\_$time$)$

print$($f$"$Size: $\{$size$\},$ Time: $\{$bulk$\_$time:$\mathrm{.}6$f$\}$ seconds"$)$

#PLOTTING THE OUTCOME

plot.figure$($figsize$=(10,6))$

# PLOT THE DIFFERENT TIMES

plot.plot$($sizes$,$ times, label$=$'Calculated Time', marker$=\text{'}$o$\text{'})$

#PLOT $0($N LOG N$)$ CURVE

theoretical$\_$times $=[$size $*$ np$.$log$2($size$)/1000000$ for size in sizes$]$ #ADJUST SCALE FOR CLARITY

plot.plot$($sizes$,$ theoretical$\_$times, label$=\text{'}$O$($N log N$)\text{'},$ linestyle$=\text{'}--\text{'})$

plot.xlabel$(\text{'}$List Size'$)$ #X AXIS TITLE

plot.ylabel$(\text{'}$Time $($in seconds$)\text{'})$ #Y AXIS TITLE

plot.title$(\text{'}$Categorized Time vs$.$ List Size'$)$ #TITLE OF GRAPH

plot.legend$()$ #LEGEND FOR GRAPH

plot.grid$($True$)$

plot.show$()$ #TO SHOW THE GRAPH

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

main$()$