[Solved] CSCI2720 Assignment5-Selection sort, Merge sort, Heap sort and Quicksort in C++

For this project, you will implement Selection sort, Merge sort, Heap sort and Quicksort in C++ and you will write a 1 to 3 page analysis report. For quicksort, you should provide two implementations. One implementation should use the first element of the array as the pivot. The second implementation should use a random pivot. All of your sorting algorithms need to keep track of the number of comparisons used by the sorting algorithm. The sorting algorithms should sort a set of integers in the ascending order.

Start early on this assignment as you need to submit a report along with your code. Note most of the code is already provided in the slide so you are free to use that code (just cite it in your read me file) only thing you need to do is calculate the number of comparisons each algorithm is making (something similar to what is explained in the lecture). For comparison you need to count when you compare two data elements not the comparison for i in a for loop.

Additional Requirements

1. You can do this assignment by writing your own classes with required data members and methods. You have full freedom on how you want to build your classes.
2. The program must include a makefile that compiles your source files into an executable file called main. The makefile should also have a clean directive to clean compiled artifacts. You will require a separate Sorting.cpp file for implementing all four sorting algorithms.
3. As the program is run (with input filename as a command line argument as shown below), it should ask for which sorting algorithm to be used for sorting. Sorted result should then be generated using that algorithm for sorting.
4. Unlike the previous assignments, after printing the results of a sort, exit the program automatically. In other words, do not ask to enter the algorithm again in a loop.
5. In each of the sorting functions, you should embed statements to count the total number of comparisons used by the function for sorting. You can use a type long count variable to count comparisons. After sorting is completed, you should print this count exactly as shown in the example output.
6. For this assignment you need to do two sets of experiments and prepare a report which will include results, plots and discussion from these two experiments. The first experiment is explained in points 7 and 8 where you just need to find out the number of comparisons for different sorting algorithms for different types of input files. The second experiment is explained in point 9 and 10 where you need to draw a plot between size vs no. of comparisons for different sorting algorithms and then verify that the plots obtained by your experiments match with the theoretical result. You need to prepare a report summarizing all your results, plots, discussion and conclusion from these two experiments.
7. You will be given 3 input files for testing the first experiment. Check ELC contents page for these files.
   1. Ordered file Containing integers placed in ascending order from 0 to 9999
   2. Random file Containing 10000 integers arranged in a random fashion
   3. Reversed file Containing integers placed in reverse order from 9999 to 0
8. You can use the same code snippet for reading input from the files as in the previous assignments. Write a well-organized, 1 to 3 page report of your work (you can exceed this if you need to). Your report must be submitted as a PDF file with your name in the middle of the cover page. Submit your report on elc and your code on odin. Your report must include an explanation of the experiments you performed for each algorithm. In conclusion answer the following questions :
   1. Provide the total number of comparisons used by each one of the algorithms and explain whether they align with the Big O time complexity of each algorithm. In case of quick sort, compare and comment about the number of comparisons and complexity with the other quicksort implementation.
   2. For Ordered file as input. ii. For Random file as input.

iii. For Reversed file as input.

Please use the following table format to summarize the content for point a.

After this table, also answer these questions below:

1. Did you use extra memory space or other data structures other than the input array? If so, explain where and why?
2. Explain what sorting algorithms work best in what situations based on your experimental results.

Here is a small example that shows what to expect when you run these algorithms on the input files. The size of input is 10,000 so for an algorithm with N² complexity N² is going to be 10000000 for such an algorithm expect 8-9 digits in the number of comparison value. Similarly for algorithm with

NlogN complexity NlogN will be 40,000 so expect 5-6 digits in the number of comparisons that you will get. For NlogN algorithm if you are getting 8-9 digits in comparisons that will indicate a problem in your comparison calculation.

9. After completing the above program and report, you will do the next set of experiments where you will draw plots (n , input size vs no. of comparisons) for sorting algorithms and verify that the experimental results match with the theoretical results. You have complete freedom in how you want to implement this part of the assignment. You can create a new main, or add an function to your sorting.cpp class or add an function in the main.cpp that implements this part of the assignment.Your code should use the algorithms created in Sorting.cpp to find additional insights about the 5 different sorting algorithms. For this part of the assignment you are not reading inputs from the text files, but instead you will be generating the inputs within the program itself and it should calculate the comparison values. Your code should be able to run the five algorithms (mentioned below) with different sizes of the inputs and give the number of comparisons. You can use these comparison values to draw the plots. (This is for the grading purpose) provide an interface in your implementation where user can specify which sorting algorithm they want to use and the size of the input that they wish to test. Your program should then generate an array with n number of random values (with n being the number specified by the user) and then it should sort those values using the sorting algorithm selected by the user. The number of comparisons should also be printed. Please specify in your README file how to compile, run and use your implementation because it is mostly up to you for how you want to implement this part of the assignment. Also note there is no sample output for this part of the assignment.
10. You are now going to use implementation in point 9 to create multiple different plots for the report mentioned above. Keep track of your experiments in a table formatted like the following and include this on your report:

Size of input

Note: I recommend running each algorithm multiple times and taking the average result for each input size to use in this table and for your plots. You can also use more values of n to make your plot look smoother however in the report you just need to show the results for the above table.

1. You should use some sort of graphing software like Microsoft Excel or Google Sheets to generate plots that compare the size of input n to the number of comparisons for the 5 sorting algorithms. You should have 5 separate plots(one for each sorting algorithm) with n on the x-axis and number of comparisons on the y-axis. Include these plots in your report.
2. You will then provide some discussion about your results. Compare the theoretical result with your experimental result for each algorithm. Does your experimental result coincide with the Big-O of that specific algorithm? Describe why there may be some inconsistencies between your plot and what the theoretical plot looks like.

Your report must be in PDF format. Submit the report on the submission link provided on the eLC under the assignment section.

Note: Example output has not shown the complete list of numbers. However, you must print the complete list of numbers in your program. The number of comparisons shown in sample output below may be slightly different than the numbers that you get, however make sure that you at least get the same number of digits so you know that it is in the correct big-O.

quick-sort-fp stands for quick sort with first element as the pivot. quick-sort-rp stands for quick sort with random element as the pivot.

Sample Output 1 (ordered.txt):

./main ordered.txt

selection-sort (s) merge-sort (m) heap-sort (h) quick-sort-fp

(q) quick-sort-rp (r)

Enter the algorithm: s 1 2 3 4 5 .. 9999

#Selection-sort comparisons: 49995000

./main ordered.txt

selection-sort (s) merge-sort (m) heap-sort (h) quick-sort-fp

(q) quick-sort-rp (r)

Enter the algorithm: m

1 2 3 4 5 . 9999

#Merge-sort comparisons: 69008

./main ordered.txt

./main random.txt

(q) quick-sort-rp (r)

Enter the algorithm: h 1 2 3 4 5 . 9999

#Heap-sort comparison: 226720

./main reversed.txt selection-sort (s) merge-sort (m) heap-sort (h) quick-sort-fp

(q) quick-sort-rp (r)

Enter the algorithm: q 1 2 3 4 5 . 9999

#Quick-sort-fp comparison: 49995000

./main reversed.txt selection-sort (s) merge-sort (m) heap-sort (h) quick-sort-fp

(q) quick-sort-rp (r)

Enter the algorithm: r 1 2 3 4 5 . 9999

#Quick-sort-rp comparison: 165518