In this assignment, you will compare the performance of the heap sort algorithm (to sort an array of integers in the increasing order of the values) using the Max heap-based approach and the Min heap-based approach.
In the lecture, we saw the Max heap-based heap sort algorithm. For this assignment, you are also given the code for Max heap-based heap sort.
Your tasks for this assignment are as follows:
Task 1: Develop a Min heap-based heap sort algorithm to sort the integers of an array in increasing order of the values. As part of this task, you are required to do the following:
Task 1.1: Briefly explain your logic for the Min heap-based heap sort algorithm (to sort an array in the increasing order of the values)
Task 1.2: Illustrate the working of your Min heap-based heap sort algorithm of Task 1.1 with an example of an arbitrary array of 8 integers
Task 1.3: Discuss the time and space complexity of your algorithm of Task 1.1.
Task 1.4: Modify the code given for the Max heap-based heap sort algorithm by changing the rearrangeHeapArray(...) function as well as by including additional code to the main function, if needed. You should not add or use any other function.
Task 2: Set up the timers as well as a trials loop for the code provided for Max heap-based heap sort algorithm as well as for the code you developed in Task 1 for the Min heap-based heap sort algorithm to determine the average sorting time for array sizes of 1000, 10000 and 100000 integers with the maximum value of an element in each case being 50000 and the number of trials for each case being 50.
You should remove all the print (cout) statements that you had in the provided code as well as in the code your developed for Task 1.4. Your code for this Task should just print the run time (I suggest in milli or micro seconds) for an array size.
Task 2.1: Develop an Excel bar chart comparing the performance of the Max heap vs. Min heap based heap sort algorithms for the above mentioned three array sizes.
Task 2.2: Provide an explanation for the rate of increase in the run times of the two algorithms with increase in the array size as well as on the difference in the performance numbers for the two algorithms, if any observed.
