Implementing heapsort versus selection sort as a single algorithm - with two different data structures
1 Project
You are going to implement a program that implements two sorting algorithms: selection sort and heapsort. But you are not going to implement two different sorting algorithms. Instead, you are going to implement a single algorithm with two different data structures:
• A vector. In this implementation the operation FindMaxAndSwap (finding the maximum element and swapping it on the last position) takes Θ(n) time.
• A heap. In this implementation the operation FindMaxAndSwap (finding the maximum element and swapping it on the last position) takes Θ(1) time. Of course, to maintain the heap property you have to call Heapify, which takes a further Θ(logn) time.
2 Guidelines
Your program should have the following basic functionality:
• Create two different classes corresponding to the two different implementations. Each of them should have the needed member functions. Data should be private, and accessible from the main program only through calling member functions.
• The main program will have two identical functions Sort. They will differ through the type of the parameter, corresponding to the two different classes (Heap/Vector)
Note: A better mechanism exists in C++, that allows us to write a single sorting function, but I won’t require this feature in the project.
1
• The main function should call these two functions with two different objects corresponding to the same sequence, and print in both cases the sorted sequence.
2. The source code of your program.
