Q: In Python, implement both HeapSort and QuickSort that sorts an array of random integers with values ranging from 0 to 100,000. They may be in the same or separate python files. Implement these algorithms:

QuickSort(A,p,r) if p < r q <-- Partition(A, p, r) QuickSort(A, p, q-1) QuickSort(A, q+1, r)

HeapSort(A,n) Build-Heap(A,n) for i <-- n downto 2 do Swap A[1]<-->A[i] Heapify(A,1,i-1)

Use function names and variables that are similar to the pseudo-code above. To make it easier to match the pseudocode, ignore index 0 in your list. For each algorithm, print out the step-by-step sorting operation (e.g. unsorted, after build-heap, after top-level heapify, after partition) for a 10-element list to verify that your algorithm works properly. Both algorithms have theoretical runtimes of O(n lg n). But based on the observed runtime, which algorithm appears to run faster? To answer this question, make plots of the mean of 10 runtimes for n = 10000, 20000, 40000, 80000, 160000, 320000, 640000, 1280000 integers for HeapSort & QuickSort (execution times should be <1 minute, so check your code if they are taking much longer to run). one way time in python is by using the package and calling time.time(). add this plot function c*nlgn where c a constant that places nlgn just above heapsort & quicksort runtime lines. keep y-axis scale reasonable, you may choose such an upper bound for all n> n0. For instance, c may only work for n0 = ~100,000. Plots may be created in any tool of your choosing (e.g. Excel, matplotlib in Python, R). Be sure to include a title and label the axes. Submit this plot as a .png or .jpg file in your a3 directory.