Assignment 4: Four Sorts of Sorts¶

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 don’t 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<int>& 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, don’t use a traditional implementation (which is not based on a priority queue). Use this (unusual!) priority queue implementation.

You will need to #include <vector> (to use vector), <algorithm> (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

Generating Data¶

Write code that counts the number of comparisons done by the 4 different sorts for data sets of n unique integers, where n = 5000, 10000, 15000, …, 100000. When this is done, you will have exactly 4*20 = 80 different counts, one for each sort and value of n.

Using a graphing program (e.g. Excel, or Google sheets), create a good-looking and clearly labeled line chart that shows how the instruction counts for each sort increases as n gets bigger. Put all the information onto one line chart, and use different color/textures to distinguish the lines. Make sure to give the graph a name and label the axes, as well as providing a legend explaining the four lines.

What to Submit¶

Submit just the file a4.zip, and nothing else. It should contain a file called a4.cpp, that, when make a4 is called, creates an executable file named a4 that, when run, generates all the 80 different values for our sorts. You can include other .cpp or .h files, as long as you wrote them and they are needed to generate the data.

Please do not include Priority_queue.h. The marker will supply a copy of that file when they run your code.

Also include your line chart as an image file or PDF file, i.e. a file format that can be easily read by anyone.

See Canvas for the exact due date and marking scheme.

Hints¶

Unlike previous assignments, you need to include a main function in a4.cpp that generates all your test data when the marker runs these commands:
```
$ make a4
// ...

$ ./a4
// ...
```
You may want to build your program using the -B option with make to force it to re-compile your program every time, e.g.:
```
$ make -B a4
```
Use valgrind to help ensure your program has no memory leaks or other memory errors, e.g.:
```
$ make -B a4

$ valgrind ./a4

// ... lots of output ...
```
A program is considered to have no memory leaks or problems if:
- In the LEAK SUMMARY, definitely lost, indirectly lost, and possibly lost must all be 0.
- The ERROR SUMMARY must report 0 errors.
- It is usually okay if still reachable reports a non-zero number of bytes.
Use only new and delete to allocate and de-allocate memory. Do not use malloc and free.
Do not use C++ smart pointers, such as unique_ptr or shared_ptr. Stick to raw pointers, and use new and delete (or delete[]) and constructors/destructors (plus valgrind) to manage memory.
The only pre-defined data structure you can use for this assignment is vector. Don’t use any other pre-defined data structures or algorithms.

You must include this comment at the start of a4.cpp:

/////////////////////////////////////////////////////////////////////////
//
// Student Info
// ------------
//
// Name : <put your full name here!>
// St.# : <put your full SFU student number here>
// Email: <put your SFU email address here>
//
//
// Statement of Originality
// ------------------------
//
// All the code and comments below are my own original work. For any non-
// original work, I have provided citations in the comments with enough
// detail so that someone can see the exact source and extent of the
// borrowed work.
//
// In addition, I have not shared this work with anyone else, and I have
// not seen solutions from other students, tutors, websites, books,
// etc.
//
/////////////////////////////////////////////////////////////////////////

If your a4.cpp does not have this, then we will assume your work is not original and it will not be marked.

If your program meets all these basic requirements, then it will graded using the marking scheme on Canvas.

Table Of Contents

Previous topic

Next topic

Assignment 4: Four Sorts of Sorts¶

The Priority Queue ADT¶

Generating Data¶

What to Submit¶

Hints¶