Programming assignment 5.
Remember:
You can remove all the variables from the workspace by writing “clear”
Look up the description of all the functions in MATLAB by typing doc in the command window.
Create three functions named build_MaxHeap(a), max_heapify(a,i), heap_sort(a).
1. Request the user to enter a positive integer, and call it n.
2. Generate n random integers between -10000 to 10000 and save them in array a.
3. Call heap_sort(a) function to sort the array. In order to sort the array using heapsort, you need to
follow the below steps:
3.1 Build a max-heap (call the function build_heap(a)). In order to build the max-heap follow the
below pseudocode:
% new_a is the output of the function, if you are using any other programming language, please write
% return new_a at the end of your code.
a = build_MaxHeap(a)
n = length(a);
for i=n:-1:1 % i= n downto 1, Can we start from n/2 instead of n? Why????
% you have the pseudocode for max_heapify in the heap binary pdf file on beachboard
a = max_heapify(a,i);
end
3.2 Remove the root (remove the first element in a): In order to do that, follow the
instructions in the heap binary pdf file on beachboard.
4. Determine the average-running time of heap_sort function for n=10000, and 100 repetitions.
5. Compare your answer with the average-running time of quicksort and selection sort (you need
implement it).
