C++ Sorting Comparison

We’ve seen the big-Oh notations for comparing the different sorting methods, but how do they really perform? Often when you devise some new algorithm (and publish it), you include the run-time estimate (big-Oh) as well as real statistics, e.g. “execution of the World’s Greatest Sorting Algorithm was 0.35s on 10 bazillion elements”, or something like that.

So let’s see how these sorting methods really perform on different types of data. I’ve included in Blackboard four files:

• Random.txt,
• Reversed.txt,
• NearlySorted.txt,
• FewUnique.txt.

Each file contains 10,000 integers (between the values of 1-10,000) which are randomly distributed, in descending order, nearly sorted in ascending order, and very few unique values, respectively.

Your task is to refer to the code in the slides (as well as resources online and the textbook) to implement:

• Bubble sort
• Insertion sort
• Quick sort
• Shell sort
• Merge Sort

For each of these sorting strategies you will execute the sort and determine the time (in seconds) that it took to sort each of the file types.

More specifically, what do you need to do:

• Create a function to read in the integer data from the supplied files.
• Implement the five sorting strategies.
• Verify using small test sets (create them yourself) that they are in fact sorting the data correctly. (Check out http://www.random.org/integers/ to help generate random numbers.)
• Implement code needed to calculate the duration of a function. (For an example, see: http://www.cplusplus.com/reference/ctime/clock/). Make certain you can get enough significant digits (or do the math yourself with respect to CLOCKS_PER_SEC). Some of these sorting strategies work superfast. Zero is not an acceptable time.
• Execute the code and record the times.

Your submission will include 3 things:

• Your source code. Please put all of the necessary functions as well as the main function in one *.cpp file. There is no need to create a class or header files.
• The table which includes your time trials. (See “HW8_results.pptx”) Note that not only the # of seconds are to be recorded but also the speed up relative to Bubble Sort (i.e., how much faster is Quick Sort than Bubble Sort?) For instance, say that with the Random data set, Bubble Sort takes 5s while Quick Sort only takes 1s. Thus, in the cell for Quick and “Speed-up” in the table, I would put 5x because Quick Sort works 5 times faster than Bubble Sort.
• Report which will include:
  • The IDE you used to develop your code
  • A screen-shot of your final code compiled (showing no errors) in your IDE
  • A 1 paragraph summary of how your code works. (Think of this as some documentation for the user.)
  • A 1 paragraph discussion of how the different sorting methods performed on the different types of data. Who was fastest with the random data set? Who was the slowest? Did one do well on one type of data set but not the others? Etc.

Important things to consider:

• Make certain that you measuring the execution time of just the sort function not anything that may precede or succeed it (like reading in the file or writing out the results, etc.)
• The code supplied in the slides and in the textbook changes the order in the array A (which is a parameter). For example, if I were to execute both the Insertion Sort immediately followed by the Shell Sort
  • InsertionSort(A,n);
  • ShellSort(A,n);

After the Insertion Sort is completed, A would be sorted so Shell Sort would be “sorting” an already sorted file. Thus, make certain you are sorting the un-sorted array.