Assignment
This assignment is divided into two parts, one implementation part and one part that contains a written report.
Part 1
• In this assignment you should implement a sorting algorithm that is based on the use of a heap. The elements to be sorted are integers stored in an array.
• For sorting elements in increasing order using heapsort it is best to use a Max-heap. How to construct a Max-heap is discussed during lecture.
• The sorting should be conducted in place, which means that the integers should be stored in the same array during the entire sorting process. Extra storage (a temporary variable) should only be used when needed for moving an element or for swapping two elements.
• You can choose to use either a normal 2-heap or a 4-heap, like the one in the Lab 2. You decide which alternative you want.
• Re-use code from your class quadHeap (Lab 2) when you can. It can be good idea to save code in this way.
• Sort 50 random integers between 0-999 using your code and print the result. Check that your output is sorted.
Part 2
Explain the Heapsort algorithm stepwise. You should also describe one problem that you faced during the assignment and how you solved this problem. You should submit Part 2 in a written report.