Description
1 Overview
This project asks you to evaluate four of the sorting algorithms we have discussed in class on various inputs and relate their theoretical run time to their empirical (actual) behavior. These algorithms are SelectionSort, InsertionSort, MergeSort, and QuickSort. In the interests of time, you have been provided with code that implements all four algorithms and can run them on inputs of varying sizes and types.
2 Running the provided program
Along with this document, you have been provided with source code and a Makefile for the various sorting algorithms and input types to test in this project. This program will run the specified algorithm (SelectionSort, InsertionSort, MergeSort, or QuickSort) on a sorted, random, or constant input array of a given size. I expect that you can use an IDE or the Linux make utility in order to compile the code. Once compiled, the program should be run from the command line, as it expects three arguments. If fewer than three arguments are specified, the program will assume default values for any unspecified arguments.
The first of these three arguments represents the size of the input array. The program only accepts sizes between 1 and 1,000,000,000, inclusive (default 10,000). The second argument represents the sorting algorithm you wish to run. Valid algorithms include SelectionSort, InsertionSort, MergeSort, and QuickSort (default MergeSort), or you can abbreviate the algorithms by their first letter (‘s,’ ‘i,’ ‘m,’, or ‘q’). The last argument represents the type of input to sort. Valid input types are sorted, random, and constant (or ‘s,’ ‘r’, ‘c’; default ‘r’), where ‘random’ is an unsorted array, ‘sorted’ is a sorted array (in increasing order), and ‘constant’ is an array where every entry is identical.
3 Project report
Your project report should be divided into two parts, Results and Analysis. For the Results section, you will need to prepare a data file describing the performance of your algorithms, and in the Analysis portion, you will need to prepare a table describing their complexity, as well as a response to these results.
3.1 Results
Run each of the four sorting algorithms on constant, sorted, and random arrays of different sizes. For each of the twelve cases, you should record the following:
1. nmin: the smallest array size that takes 30 milliseconds or more per run to sort;
2. tmin: the time to sort an array of size nmin;
3. nmax: the largest array that you sorted
4. tmax: the time required to sort nmax elements.
When trying to find nmin and nmax, I recommend starting with an arbitrary input size and multiplying or dividing the array size by something like 10 or 2, as this should quickly get you to arrays that are large or small enough. For nmax, I recommend you stop the program if it takes longer than 30 minutes (˜5–10 minutes per call) and try something smaller. Note that for some of the experiments the time will not get close to 30 minutes; just use the largest inputs that you were able to sort in these cases.
nmin tmin nmax tmax
SC
SS
SR
IC
IS
IR
MC
MS
MR
QC
QS
QR
3.2 Analysis
In this section, you will estimate the complexity of the four algorithms by comparing the ratio between tmin and tmax to ratios representing the complexity of the algorithm. Specifically, you should compute f(nmax)/f(nmin) for f1(n) = n, f2(n) = nln(n), and f3(n) = n2. You should round to the nearest integer when computing these ratios. Finally, you should label each experiment according to the ratio tmax/tmin most resembles.
For example, if one of your experiments resulted in nmin = 100 and nmax = 10,000,000, your ratios would be:
f1(nmax)/f1(nmin) = 10,000,000/100
= 100,000
f2(nmax)/f2(nmin) = 10,000,000ln(10,000,000)/(100ln(100))
= 350,000
f3(nmax)/f3(nmin) = 10,000,0002/1002
= 10,000,000,000
As part of your report, you should create a chart that includes the computed ratios as well as the behavior of the algorithm (Linear, nlgn, or Quadratic), across all 12 experiments. An example chart appears below:
tmax/tmin n ratio nln(n) ratio n2 ratio Behavior
SC
SS
SR
IC
IS
IR
MC
MS
MR
QC
QS
QR
In addition to the table, you should write a brief summary of (1) how your results compare to the theoretical analysis for the four algorithms (below), and (2) why your results make sense or are surprising. You should write a summary for each experiment. You should spend more time explaining your results when they are unusual or unexpected.
Best-case Average-case Worst-case
complexity complexity complexity
SelectionSort Θ(n2) Θ(n2) Θ(n2)
InsertionSort Ω(n) Θ(n2) O(n2)
MergeSort Θ(nlgn) Θ(nlgn) Θ(nlgn)
QuickSort Ω(nlgn) Θ(nlgn) O(n2)
4 Submission
For this project, you should submit a zip archive containing (1) a CSV file containing your results (described in Section 3.1), and (2) your tables and analysis (described in Section 3.2), in PDF format.
5 Grading
Data file containing results 15 points
Table with ratios 15 points
Analysis 20 points
Requirements for each portion of the grade are described in Sections 3.1 and 3.2.
