Homework: Algorithmic Analysis

Sort Battle!

Empty repo, you will submit these files for this homework (details in the next section). You don't need to split the functions into separate .h and .cpp files, but you can if you want to.

• util.h: functions for working with int arrays and linked lists
• selection.h: your array-based selection sort function (and helper functions)
• merge.h: your linked-list-based merge sort function (and helper functions)
• quick.h: your array-based quick sort function (and helper functions)
• main.cpp: your main function that runs all the tests
• Your 2-page report (the table of values and a page of explanation)

https://cssvn.utrgv.edu/svn_etomai/201720_2380/hw02_sort/<your username>

Sort, Sort, Sort

In this homework, which is absorbing the last lab, you will implement three different ways to sort a list of numbers. We'll stick with simple lists of int, to make your lives easier.

• Selection Sort in an array (the simple one)
• Merge Sort in a linked list (the one with no extra memory)
• Quick Sort in an array (the quick one (duh))

These are standard sorts that everyone should write on their own at least once. You should absolutetly look up the algorithm, but be careful that you don't end up copying someone else's code. The point is not to produce these specific sorts, its to learn how to implement clear, somewhat complex algorithms yourself.

As always, if you need help, get it. But then when you're done, go back to a blank page and write it again yourself with no supports.

All About That Main

In your main.cpp, test each sorting function on a short list (array or linked list) to prove it works. You'll want to write some list and array helpers like printing, appending, finding length and generating large random data sets.

Then, perform the following experiment for each of the three sorting functions.

• Time the function sorting 1000, 10000 and 100000 random numbers (that's n)
• For each value of n, report three results:
  1. Time the function on 100 different random lists and take the average performance
  2. Time the function on the best case list (already sorted)
  3. Time the function on the worst case list (sorted in reverse order)
     (Yep! Time to use those reverse functions we kept messing with!)

Help!

For your reviewing pleasure, here is a code example for random number generation and timing.

#include <ctime>
#include <string>
#include <ctime>
...

// call this ONCE at the beginning of main to seed the random generator
srand(static_cast(time(NULL)));

// begin timing example
clock_t begin = clock();

// whatever it is you want to time...let's say making a random number
int r = rand();

// ending timing and display how much time has passed
clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
cout << "Generating a random number took " << elapsed_secs << " seconds" << endl;

I Have to Report You

Write a report! Fill out this table with values, then take about a page to explain the complexity of each of the functions, and how the results reflect that.

Random List (Average time over 100 trials)
n	1000	10000	100000
selection sort
merge sort
quick sort
Already Sorted List
n	1000	10000	100000
selection sort
merge sort
quick sort
Reverse Sorted List
n	1000	10000	100000
selection sort
merge sort
quick sort