answer two questions in 4a

The Heapsort algorithm sorts an array A using (1) memory, by making A heap-ordered, and then moving values to their correctly sorted positions. 4a i) Write a procedure that implements Heapsort, sorting its input array into ascending order. Procedures to add and remove values from a heap can be called in HEAPSORT without giving code for them. Describe the properties of the subarrays created within A and how they are maintained. Given an input array of size N, what will be the running time of your HEAPSORT procedure, in notation? Explain your answer. Include an explanation of the performance of the heap operations. ii) The Quicksort algorithm presented in this course uses the Lomuto partitioning scheme, which divides the data into three parts: elements less than the pivot, the pivot element, and elements greater than or equal to the pivot. The following algorithm implements the alternative Hoare partitioning scheme. b