In this assignment, your task is to create and perform an experiment that compares the number of comparisons done by these four different sorting algorithms:

The standard C++ STL sort function (not the C qsort function!). Of course, this sort is already pre-made, so you dont need to implement it. But you do need to find a way to count the number of comparisons it does.

Selection sort, using a priority queue (see below) implemented as an unordered vector.

Insertion sort, using a priority queue (see below) implemented as a sorted vector.

Heapsort, using a priority queue (see below) implemented as a heap.

You must implement sorts 2, 3, and 4 yourself, and they should each follow this basic structure:

// Pre-condition: // none // Post-condition: // v is re-arranged into ascending sorted order void sort(vector& v) { // // Step 1: put all elements of v into an empty // priority queue // // // Step 2: remove all elements in PQ and put them back // into v (from smallest to biggest) } 

The only difference between sorts 2, 3, and 4 is how they implement the priority queue. For example, if the priority queue is implemented as an unordered vector, then the code outline above will result in a version of selection sort.

Important: For selection sort and insertion sort, dont use a traditional implementation (which is not based on a priority queue). Use this (unusual!) priority queue implementation.

You will need to #include (to use vector), (to get the STL sort), cmpt_error.h (for cmpt::error), and Priority_queue.h (see below). Other than that, you should not use any other pre-made data structures from the C++ standard library (or elsewhere) for your priority-queue based sorts. Implement them entirely on your own using only basic C++ features.

The Priority Queue ADT

For this assignment, your three different priority queues must implement this abstract base class:

// Priority_queue.h class Priority_queue { public: // C++ base classes should always provide a virtual destructor so that // deriving classes can over-ride if they need to. virtual ~Priority_queue() { } // Pre-condition: // none // Post-condition: // Returns true if there are 0 items in this priority queue. virtual bool empty() const = 0; // Pre-condition: // none // Post-condition: // Puts x into this priority queue. If x is already in the priority // queue, then nothing is added (i.e. duplicates are not allowed). virtual void insert(int x) = 0; // Pre-condition: // !empty() // Post-condition: // Removes and returns the smallest element from this priority queue. virtual int pop_min() = 0; }; // class Priority_queue