## 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.