I use Visual Studio for my assignments and a main.c has to be added
In this assignment, you'll be running experiments on a variety of sorting algorithms, sizes, and input patterns. There's no coding required for this assignment, it's purely about data collection and analysis.
Requirements
To collect the data you need, simply run the ProgrammingAssignment6 code that I've provided to you on Canvas. You can either run the code manually "as is" to generate each data point individually or you can add additional code on your own to collect all the data without user intervention -- it's up to you. Each data point you collect is appended to a file named times.txt; that's built as a csv file, so you can easily import the data into a spreadsheet if you want to.
You need to collect data for the following sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort
You need to run each of the algorithms on sizes 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, and 100000
You need to run each of the algorithms on all of the sizes on the data in random.txt, almostsorted.txt, and backwards.txt
Generating plots
After collecting all the data, you need to use function plotting software to create three plots, one for each of the input files. To generate the plots, you should enter each of the data points you collected and have the plotting software draw a line through those points. An example plot (with fictional data) is shown below (I used paint.net to clean up a screen shot of the graph).
You can use any plotting software you want, but I used the free Graph software available athttp://download.cnet.com/Graph/3000-2053_4-10063417.html(Links to an external site.). If you use the Graph software, you can add a point series (your set of data points for a particular sorting algorithm) using F4 or the
b
utton:
If you set the marker size to 0 and the line width to 2 as shown in the pane on the right, you'll get a line that's fit to your data points just like you need. Be sure to change the Description text box at the top so your "plot key" (upper right in the sample plot) lists the three sorting algorithm names instead of Series *. For each required plot, the X values will be 10000, 20000, 30000, etc, and the Y values will be the time it took for each of those sizes.
Report
Your "deliverable" for this assignment is a report containing your data and your analysis results.
Your report should contain the following sections:
1. Sorting Algorithm Complexity
In this section, you should list the algorithmic complexity, in Big-O notation, of each of the sorting algorithms in the assignment. This is easy, all you have to do is look up the different complexities and write them down here.
2. Random Data
In this section, you need to provide the following:
a. A table of the time you collected for each algorithm, for each size, on the data in random.txt
b. A plot of that data like the example shown above
c. A brief discussion of the results. Specifically, does the performance of the algorithms seem different from each other? If so, why do you think that is?
3. Almost Sorted Data
In this section, you need to provide the following:
a. A table of the time you collected for each algorithm, for each size, on the data in almostsorted.txt
b. A plot of that data like the example shown above
c. A brief discussion of the results. Specifically, does the performance of the algorithms seem different from each other? If so, why do you think that is?
4. Backwards Data
In this section, you need to provide the following:
a. A table of the time you collected for each algorithm, for each size, on the data in backwards.txt
b. A plot of that data like the example shown above
c. A brief discussion of the results. Specifically, does the performance of the algorithms seem different from each other? If so, why do you think that is?
5. Conclusion
If you were only allowed to pick one of the three algorithms for all your sorting needs, which algorithm would you pick? Explain why.
Submitting Your Assignment
Convert your report to a pdf file and submit it in the appropriate assignment on Canvas.