Sample Programming Assignment
Chapter 13
Sorting
Testing Four Sorting Methods

Chapter 13 Assignment

 Grab the file 

www.cs.colorado.edu/~main/projects/sorttests.cxx. Implement the
missing function (quicksort).
Compile and run your sorttests program using the gprof
profiler as described in recitation (see

www.cs.colorado.edu/~main/projects/gprof.html.
Send the results of gprof to a file and examine the times listed
for the testsort function. In particular, make note of the total
amount of time used when testsort called each of the four sorting
functions. Be sure to include both the time used by the sorting function
and the time used by its descendants (i.e., the functions that the
sorting function called). For example, in my gprof report I have this
information for the testsort function:
-----------------------------------------------
                0.03        1.14       4/4           _main [3]
[2]     92.8    0.03        1.14       4         _testsort__FPFPiUi_vPCc [2]
                0.86        0.00       1/1           _selectionsort__FPiUi [4]
                0.00        0.15       1/1           _heapsort__FPiUi [5]
                0.01        0.09       1/1           _mergesort__FPiUi [7]
                ...

The function names in this report contains extra infomration
about the function's parameters (for example
_mergesort__FPiVi means that mergesort is a function
with two parameters, the first of which is a pointer to an integer
(Pi) and the second of which is an ordinary value parameter that is
an integer (Vi). In any case, this report indicates that
the testsort function used 92.8% of the total time taken by the
program. This included 0.03 seconds that testsort used itself
and 1.14 seconds used by functions that testsort called.
For each called functions, there is a list of how
much time it used. For example, mergesort used a total of
0.10 seconds (0.01 seconds that it used itself and another 0.09 seconds
that were used by functions that mergesort called).

Anyway, when you produce this report, make note of how many total
seconds were used by each of the four sorting methods.

Double the array size in the sorttests program and rerun the tests.
Keep doubling the size until total time for the selectionsort exceeds ten 
minutes. Keep track of the time needed for each of the
four functions with each of the array sizes (1000, 2000, 4000, and
so on). 
Make a graph to display your results. The x-axis of your graph
should be the size of the array.
The y-axis of your graph should be the amount of
time taken. You'll have four times recorded for each array size.
Draw a line to connect all the points for the selectionsort, another line for the mergesort, another for the quicksort, and a fourth for the
heapsort. You can use either a linear scale or a log scale.
Submit your sorttests.cxx and one of your gprof report files to
Dora no later than Friday, Dec 15. Bring a printed or hand drawn copy of your
graph to the final exam or give it to Michael before Dec 16.
Because it's the end of the semester, no late submissions will be
accepted.