CMPS261 Advanced Data Structures

Problem:

Conduct a study on the behavior of three sorts: bubble sort, heap sort, and quicksort on lists stored in contiguous arrays of n integers for n = 10, n = 100, n = 1000, and n = 10000. For each sorting technique measure the actual number of comparisons and the actual number of exchanges required to sort the elements.

Specifics:

Modify each sorting technique to collect the desired measurements.

Test each sorting technique, for each value of n, at least 10 times for a total of 40 test for each technique. For instance, test bubble sort for 10 different lists of 10 values, for 10 different lists of 100 values, for 10 different lists of 1000 values, and 10 different lists of 10000 values. From these tests, determine the average values for the number of comparisons and the number of exchanges for each sort method.

Use the random number function to generate the values that will be stored in the arrays.  You must use the following two include lines
        #include <time.h>
        #include <cstdlib>
and initialize the random number generater in your main with srand(time(NULL)) before you can call the random number function rand(). You should only initialize the random number generator once.

Your output should display the measure results of the individual runs, the average over all runs for each size and method, and the worst case for each measure.  It should specify the sorting routine being tested, the size of the array being sorted, and values for each of the measures.  The output should be presented in an easy to read format that makes comparisons amoung the various sorts easy. Do not include the actual sorted lists in the output.

After you have collected data for each list size, write up an analysis on the results of your study.  Can you draw any conclusions as to the relative goodness of these algorithms?  Include this analysis as part of your documentation folder.

You will need to implement the bubble sort and the heap sort. You must use the following quickSort code for your quickSort implementation. You will have to modify this code to include the appropriate counters for comparisons and swaps. 
 

Submit the assignment with the following command:

submit  -c mgr5211 -a sorted < filelist >