Assignment 9, due Thursday April 27 at noon.

You must submit your program electronically via gsubmit on csa.

Under no circumstances will late assignments be accepted.

The code you submit must conform with the programming guidelines.

Program Description

In this final assignment, you will:

Correctness Testing

To test the correctness of your sorting routine, you must choose a small (n about 20) set of randomly chosen data and then sort the data using each routine on that set.  To generate an array of random integers, use the library function rand().

Performance Testing

For both your sort and the system qsort, characterize the average number of comparisons made. To count comparisons, you will need to write a function compare(...) as explained on the qsort man page.  You can use a global variable to count the number of comparisons.

To characterize performance, your program must generate large data sets of randomly chosen numbers and run qsort and your sort routine on the same data sets. Choose at least five different sizes (such as n=1000, 2000, 3000, 4000, 5000). Measure the average number of comparisons made for each size of n. Take the average performance over 100 trials at each size n.

Make sure that dataset size is large enough so that the time used clearly grows with n, but not so large that you swamp your memory or that it takes inordinately long (so the range of n used very much depends on which machine you use).

While doing your programming assignment, you should also think about the complexity of the sorting algorithm you implement.

What You Turn In

For this assignment you will not do electronic submission. Instead you must hand in a printed report that includes:
  1. A written description of what your program is doing along with a discussion of the complexity of sorting algorithm that you implemented.
  2. A well documented source code of all your program including header files, program code, main test driver, etc. The code you submit should conform with the program assignment guidelines.
  3. A test result printout that shows the correctness testing of your program.
  4. A graph plotting average number of comparisons for both qsort and your sort as a function of data set size. This should allow for direct comparison of qsort vs. your sort.

Extra Credit

Extra credit will be given for anyone who can develop a sorting routine that has average performance better than qsort for large n. Your routine should on average provide fewer comparisons for randomly generated test datasets of size greater than 1000.

If you successfully complete the extra credit, explain how you did it in your report. You must also electronically submit your code in the usual way so that we can confirm your claim.  Write and submit three files:

  1. sort.cpp -- implementation of your sorting routine
  2. sort.h -- header file for your sorting routine
  3. main.cpp -- the main program

Academic Honesty and Collaboration

Cooperation is recommended in understanding various concepts and system features. But the actual solution of the assignments, the programming and debugging must be your individual work, except for what you specifically credit to other sources. (Your grade will be based on your own contribution.) For example, copying without attribution any part of someone else's program is plagiarism, even if you modify it and even if the source is a textbook. The University takes acts of cheating and plagiarism very seriously: first time violators are routinely suspended for a semester.