Mergesort and quicksort Solution

Description

goal

In this project you will translate Python implementations of mergesort and quicksort into C⁺⁺. To keep things as simple as possible, the C⁺⁺ versions will only sort vectors of type int.

We will use C⁺⁺ vectors as the containers for integers to be sorted. Such vectors are declared as follows:

s t d : : v e c t o r <int> x ;

You will not actually need to declare any vectors, unless you want to extend the test driver. The requisite set of vector declarations already exists in the code I am giving you.

what you are given

You are given working Python versions of mergesort and quicksort in mergesort.py and quicksort.py, respectively. This code contains a test driver. If you wish to test code on arrays of length 10000000, say, then you would invoke the code with

Using this Python code as a model, you will complete the code in sortchen.cpp. The only routines you will need to nish are msort() and qsort()|the other functions are complete and correct.

A test driver is provided in testchen.cpp, and a make le in Makefilechen. You can either rename the latter to Makefile or you can invoke it using

make f M a k e f i l e c h e n

If you insist on not using make, you can build the executable (name sort here) with

g++ O3 g s t d=c++11 Wall p e d a n t i c o s o r t mainchen . cpp s o r t c h e n . cpp

What you are to do

public API

The user will call one of the following routines:

void m e r g e s o r t ( s t d : : v e c t o r <int> &x ) ;

void q u i c k s o r t ( s t d : : v e c t o r <int> &x ) ;

In this call x is a reference to the vector being sorted.

Here we are using C⁺⁺ vectors from the Standard Template Library (STL). Some methods associated with vectors that will prove helpful include size() and resize(). Two functions will be useful:

std::swap(x,y), which swaps the values of x and y, and std::min(x,y), which returns the minimum of x and y.

Otherwise you should not use other STL containers and methods.

under the hood

The auxiliary storage in mergesort is a vector of type int. It is allocated once per user call mergesort() and is passed to the routines that do the work. This avoids the tremendous amount of unnecessary overhead we would see if we allocated space in every call to merge().

In both mergesort and quicksort you are to switch to insertion sort once the data being sorted are not very numerous. I have found that a threshold between 35 and 55 works pretty well. The best value for the C⁺⁺ implementation may di er from that for the Python implementations.

where to start

In your gitlab.com repository create a new directory sorting. You should place your code in this directory.

what to turn in, and how

Submit your code in sortchen.cpp.

grading

No credit will be given for

code that does not compile and link, code that opens any les,

code that includes an active main(),

code that spews output to cout or cerr (so be sure to disable all debugging i/o!!). Here are other problems that will have a negative e ect on your grade.

Your program crashes during testing.

Code that appears to work but nevertheless has memory access errors. Code that is incorrect.

Memory leaks.

Code that is unnecessarily ine cient.

tips

Be sure to test your code on large vectors (e.g., length at least 100,000,000. A reasonable gure to sort 10,000,000 ints on one of the CS lab machines would be

{ about a second or less, if you enable optimization when you compile (the -O3 option); { about 2{4 seconds, if you do not turn enable optimization.

If your code takes a lot longer than this, there is something wrong.

Be sure to check your code with valgrind! It will detect memory access errors that otherwise might be invisible, and make debugging a LOT easier.

Be sure that not only is the vector sorted upon return, but that it’s the same vector. A common error is to return values that don’t correspond to the original inputs. (I.e., if we return an vector of all zeros, it’s sorted, but it’s probably not the correct result.)

The Python quicksort is based on Program 6 in the paper \Engineering a sort function” posted in the notes section of the Blackboard site may be helpful here. Read the section \The opportunity of equal elements” so that you understand what this version of quicksort does.

3