Project 4 sorting algorithm

For this project, you will sort the 1000 objects from your data set. You will modify each sorting
algorithm to collect data. You will analyze the results from the different sorting algorithms.
Implement
- You should have your 1000+ objects stored in a vector, initially unsorted.
- Choose five sorting algorithms:
1. Bubble Sort
2. Selection Sort or Insertion Sort
3. Merge Sort or Quick Sort
4. Heap Sort
5. Two-sort: sort by any algorithm (one of the above or a different one), then sort on a
different attribute using a stable sorting algorithm (again, one of the above or a different one).
- Use each sorting algorithm to sort a vector of the first 100 objects from your dataset. Record
the number of reads (the number of times you retrieve and use an object from the vector) and
writes (the number of times you assign an object into the vector). Then do the same for a
vector of size 200, 300, 400, 500, 600, 700, 800, 900, and 1000. Each of the five sorting
algorithms should be given identical unsorted vectors to begin with.
- Analyze the data. Graph the number of reads and writes for each sorting algorithm and look
at how the number of reads and writes grows when the size of the data set grows. Compare
and contrast the different sorting algorithms and draw conclusions about which sorting
algorithms are more efficient. Discuss complexities and their effects. All of this will go in your
writeup.
- In your writeup, also include answers to the following questions: If you need to sort a contacts
list on a mobile app, which sorting algorithm(s) would you use and why? What about if you
need to sort a database of 20 million client files that are stored in a datacenter in the cloud?
- You must submit your .cpp file(s), your data file(s), and your writeup. Please submit your
writeup in PDF format.
Extra Credit
To earn up to 10 extra credit points (at the grader’s discretion), you can get more thorough
results. This can include:
- Setting timers to record how long it takes you to sort the objects with each algorithm
- Performing the same experiment, except double the size of the data set each time (instead of
having it grow linearly)
- Using more sorting algorithms
Grading
The project is out of 90 points.
5 pts Program compiles and runs.
5 pts Code style. Readable, naming style is consistent, comments where appropriate.
5 pts Used five sorting algorithms according to the directions above.
15 pts Sorted the 100, 200, … 1000 objects according to the directions above.
40 pts Recorded the number of reads and writes for each sort.
15 pts Analyzed the results.
5 pts Writeup: professional, grammatically correct, cites sources, at least 500 words.