CIS-3050 Algorithms and Data Structures

Assignment 6

Due:  Monday, Dec. 13 in class!

Your task is to implement two sorting algorithms and collect timings on them.   You need to implement 1 of the quadratic sorts (bubble, selection or insertion), and one sort that is better than quadratic (heap, quicksort, merge sort or radix sort).    Each sort should be run a minimum of 10 times, and you should display both the individual timings, plus the average of all the runs of that sort.

The sorts will work over an int array[] containing integer values between 0 and 1000.    You should run the sorts over arrays with at least 25,000 elements (basically, you are striving for being able to collect reasonable timings for your fastest sort, without having to wait forever for your slower sort.  

Click here to download a zip file of the code I am providing

To get you started, I have provided a Timer class, and a function that will generate a random array of elements for you.   Here is a description of the interfaces:

int * generateArray(int numElements):    call this function with the number of elements you'd like in your array.  It will return a pointer to an allocated array, containing elements between 0 and 1000.   Feel free to play with this function if you'd like to have some negative values, or larger values in the array.   The caller (you!) are responsible for freeing the space in the array returned to you.  Remember when freeing an array, you use the syntax:   delete []  ptr;

spica::Timer:  This class is located in package spica, so references to it must refer to the package  (like std::cout).   You use the timer like so:

spica::Timer  stopwatch;      // creates a timer

stopwatch.start();     // start the timer
// do the stuff you want to time in here
stopwatch.stop();    // stop the timer

int elapsedMillis = stopwatch.time();   // read the timer -- how much time elapsed (in milliseconds) between start and stop.  Remember to divide by 1000 to get seconds!

stopwatch.reset();   // clear the timer before timing anything else

Be sure that when you collect your timings, you are only timing the actual amount of time that the sort is running.  Do not time the period when you are filling the array or doing any other start up or concluding task.

Each sort should be implemented as a separate function, and the timing should be external to the sort function.  In other words, start the timer in main, call your sort, then stop the timer.   Be sure to use constants/variables where appropriate (for example, changing the number of elements in the array should involve changing only one place in your code).  Use good coding practices, and comment your code where appropriate.

As part of your implementation, you will probably want to write a printArray() function so that you can run with a small array and verify that your sort is working correctly.

Reminder:  be sure to document any help you get from other people/resources!

This assignment is due at class on Dec 13.   Please bring a paper copy of your code (a single file), plus a printout of the output of your sorts.  This print should include what the name of each sort is, the number of elements being sorted, plus the timings.   Also submit your source code file on line via blackboard.   Given the end of the semester, this assignment MUST be turned in on time.