Analyzing Sorting Algorithms

Overview

This project is designed to help you deepen your understanding of sorting algorithms. Your goal is to demonstrate analytically what the trade-offs are betweeen different sorting algorithms. This analysis will be analytical based on data you will generate and report on.

Getting Started

You will write all the code needed for this lab from scratch. That said, feel free to reference code and helper functions that have been demonstrated in class, and re-write these functions into your own project code base.

Requirements

1. Write five sorting algorithms

n class, we have already written four algorithms: selection_sort, insertion_sort, quicksort, and merge_sort. Copy the implementations for these algorithms as part of your project. The signature for the algorithms should be the same for all of them:

void algorithm_name(std::vector< int>::iterator begin, std::vector< int>::iterator end, std::function< bool(const int&, const int&)> comparator);

You will need to choose one additional algorithm as well and implement it. It should have the same signature. There are no restrictions on which algorithm you should choose, but please choose something that you will be able to correctly implement we use for the other algorithms. A lot of online examples use raw arrays and indices.

Your algorithms need to work correctly, i.e. they need to sort a std::vector< int> such that after being invoked, the list of integers is in order from least to greatest.

2. Measure runtime

Write code inside of main that measures runtime of the following algorithms:

• Your own selection_sort
• Your own insertion_sort
• Your own quicksort
• Your own merge_sort
• Any other sorting algorithm of your choosing
• std::sort
• std::stable_sort

You will need to generate various sized lists of random integers as explained below.

Please carefully follow these instructions for generating the lists:

• You need to test many different list sizes. Start with a list of size 1000, and increment that number by 1000 until you reach 50000 (fifty thousand). You should not do this manually, write a for-loop that does this for you.
• For each of these list sizes, create a std::vector< int> and fill it with that many random integer values. The of these integer values should be an order of magnitude more than the size of the list. I.e. if the size of the list is 1000, then the numbers in the list should range from 0 to 10000. If the list size is 9000 then the numbers should range between 0 and 90000.
• You will need a of this list for each sorting algorithm. Generate six more copies of the list so that in total you have seven identical lists. If you have a std::vector< int> called list, you can create an identical copy using the copy constructor: std::vector< int> copy{ list };.
• Invoke each of the seven sorting algorithms on its own unsorted copy of the list. Make sure to time each sorting algorithm independently.
  • If you would like, you can invoke the algorithm mulitple times and average the results, but this is not required. If you do choose to take averages, make sure to do so on unsorted copies of the list.

All of these requirements can be written using a few nested for-loops. Please don't try to do this manually where you change a value, then re-compile and re-run the code and record the results. That would end up taking an extremely long time. Write a program that does all of this for you, and then just let the program run. The program will likely take several minutes to run. The program will take much longer than the program you wrote for the previous project that did searching.

4. Measure comparisons

When you run all of these algorithms, you will take advantage of the fact that the third parameter is a callable function that you provide. You can use this to keep track of the number of times that function is called.

For each of the above list sizes in addition to measuring the runtime, measure the number of comparisons that the search algorithm uses by creating a counter variable and incrementing it on each comparison.

5. Produce a graph of your data

For all of the data you generate (runtime data and comparison count data) keep track of the results. You can print out all of the results to a file in order to have access to it when the program is finished running.

For each list size there are 14 data points you need to collect. You should have a run time for each of the 7 sorting algorithms, and a comparison count for each of the 7 sorting algorithms.

I recommend that instead of printing to the console, you print to a file. You can print using the CSV format. This will make it easy to import the data into a spreadsheet and create a graph of the data.

Once you have the data, you need to create two graphs of the results. One graph for runtime, and one graph for comparisons. The should represent the list size, and the should represent the number of seconds for the first graph, and the number of comparisons for the second graph. On the graph, there should be a different line for each sorting algorithm.

You can open the CSV data in a spreadsheet program. You can use Excel, or Google docs, or any of several other free spreadsheet programs. If you have the CSV data formatted as shown above, then it should work well.

6. Report on your findings

Write a one page summary report on your findings. You should discuss what you observe based on the data you gathered and how the different algorithms compare to each other. Which algorithm was fastest?

Use what we learned about theoretical analysis along with the data you gathered to explain the runtime for the additional algorithm that you chose to implement. Your report should include a section explaining your algorithm, how it works, and why it has the runtime it does.

Also include a section explaining what you observe with std::sort and std::stable_sort.

What algorithms do they seem to most closely match?

Please include in your report the graphs you created.