Our group would like to implement and test a number of O(nlgn) sorting algorithms. More specifically we would like to design and test how large or small the constants are for heap sort, merge sort, and quicksort relative to each other. For quicksort, we will implement it with three different partition methods, namely Hoare, Lomuto, and randomized. What we are interested is not what these algorithms have to offer from a theoretical standpoint as we already know their runtime complexity, but more about how they perform in actual timing tests, so that we can determine how large the constants are for each of these 5 algorithms. We plan on also creating a helper program to generate inputs of arbitrary size, and of all types: random, sorted, reverse sorted, all unique, some values repeated, etc. The goal of varying the inputs is to observe how efficient these algorithms are in the real world when given some specific type of input. Mainly, our questions are: A. Which algorithm provides the fastest average runtime, and why? B. How does input type affect runtime for each algorithm, and why?
Our group will proceed with this project as such:
-
First, we will create the input generation program, to be able to test our algorithms with small inputs at first. This will allow for testing the scalability of our implementations easily.
-
We will split up development of each of the sorts between the three of us by preference of which sort each person would prefer to do. Each of these sorts will be tested thoroughly to ensure correctness with all sizes of inputs. Each sort will also be code reviewed to ensure they are as effiecient as possible, because we are interested in their performance relative to each other.
-
Third, we will implement timing code in order to measure each of these algorithm's performances over the different inputs. Using the data we obtain, we plan on creating informative powerpoint slides with easy to read charts and answers to our questions.
Sincerely, David Skoda, Benny Mei, Joe Grillo