Description
Question 1 – 15 points
-
-
creates an array from the following: {12, 7, 11, 18, 19, 9, 6, 14, 21, 3, 17, 20, 5, 12, 14, 8}.
-
-
-
calls the selectionSort function, displays the number of key comparisons and the number of data moves to sort this array, and calls the displayArray function to show the contents of the array after selection sorting
-
-
-
calls the mergeSort function, displays the number of key comparisons and the number of data moves to sort this array, and calls the displayArray function to show the contents of the array after merge sorting
-
-
-
calls the quickSort function, displays the number of key comparisons and the number of data moves to sort this array, and calls the displayArray function to show the contents of the array after quick sorting
-
-
-
calls the radixSort function to sort this array and calls the displayArray function to show the contents of the array after radix sorting
-
At the end, write a basic Makefile which compiles all of your code and creates an executable file named hw1. Check out this tutorial for writing a simple makefile:
http://www.cs.colby.edu/maxwell/courses/tutorials/maketutor/
Please make sure that your Makefile works properly, otherwise you will not get any points from Question 2.
Important: Then run your executable and add the screenshot of the console to the solution of Question 2 in the pdf submission.
-
[10 points] In this part, you will analyze the performance of the sorting algorithms that you will have implemented. Write a performanceAnalysis function to systematically call these algorithms. This function should call the auxiliary global functions to create the arrays with different contents. For each scenario (random, ascending, descending), use the following sizes for the arrays: 6000, 10000, 14000, 18000, 22000, 26000, 30000. Run each of the sorting algorithms with each scenario and output the elapsed time in milliseconds, the number of key comparisons and the number of data moves.
The performanceAnalysis function needs to produce an output similar to the one given on the next page. Include this output to the answer of Question 2 in the pdf submission.
—————————————————–
Analysis of Selection Sort
-
-
Array Size
Elapsed time
compCount
moveCount
6000
x
ms
x
x
10000
x
ms
x
x
…
—————————————————–
Analysis of Merge
Sort
Array Size
Elapsed time
compCount
moveCount
6000
x
ms
x
x
10000
x
ms
x
x
…
—————————————————–
Analysis of Quick
Sort
Array Size
Elapsed time
compCount
moveCount
6000
x
ms
x
x
10000
x
ms
x
x
…
—————————————————–
Analysis of Radix
Sort
Array Size
Elapsed time
6000
x
ms
10000
x
ms
…
-
Question 3 – 15 points
After running your programs, prepare a single page report about the experimental results that you will have obtained in Question 2. With the help of a spreadsheet program (Microsoft Excel, Matlab or other tools), plot elapsed time versus the array size for each sorting algorithm implemented in Question 2. Combine the outputs of each sorting algorithm in a single graph.
In your report, interpret and compare your empirical results with the theoretical ones. Explain any differences between the empirical and theoretical results, if any.
Do not forget to discuss how the time complexity of your program changed when you applied the sorting algorithms to already sorted arrays (ascending and descending) instead of an array containing randomly generated numbers. Also briefly explain the rationality behind this change.
