6. (30 points) The authors of modern software libraries are nice enough to include a sort() function for use in applications. These libraries claim that the sort functions use an algorithm that is at least 0(n *lg(n)) in nature. Let's test this claim by writing a small program. In your language of choice, use the sort routine provided by the language to sort randomly generated data sets of 5, 10, 50, 100, 500, 1000, 5000, and 10,000 integers. Since we are looking at average data set sizes, you will need to sort at least 10 or more random data sets for each data set size. You should implement an algorithm that looks like this: Algorithm 3: Test the order of the library sort Output: A data set of run times for each data set size for size = [5, 10, 50, 100, 500, 1000, 5000, 100000) do Set totalRun Time leftarrow 0; for run Number E [o .. NumberOfRuns) do GenerateRandomDataSet (dataSet,size); Note start time; Sort (dataSet); Note end time; Set elapsed time to difference between end and start times; Add elapsed time to totalRunTime; Set averageRunTime = totalRunTime / NumberOfRuns; The function GenerateRandomDataSet (dataSet, size) needs to generate a random set of integers of whatever size is passed into the function as an input. Create a graph (using Excel or your favorite graphing tool) that graphs data set size versus the average run time for each size. Include a plot of data set size versus f(n) = n*lg(n) as well. Submit your source code, graph, and a short (1-3 paragraph) analysis of the results (each of which contributes 10 points to the grade for this problem). 6. (30 points) The authors of modern software libraries are nice enough to include a sort() function for use in applications. These libraries claim that the sort functions use an algorithm that is at least 0(n *lg(n)) in nature. Let's test this claim by writing a small program. In your language of choice, use the sort routine provided by the language to sort randomly generated data sets of 5, 10, 50, 100, 500, 1000, 5000, and 10,000 integers. Since we are looking at average data set sizes, you will need to sort at least 10 or more random data sets for each data set size. You should implement an algorithm that looks like this: Algorithm 3: Test the order of the library sort Output: A data set of run times for each data set size for size = [5, 10, 50, 100, 500, 1000, 5000, 100000) do Set totalRun Time leftarrow 0; for run Number E [o .. NumberOfRuns) do GenerateRandomDataSet (dataSet,size); Note start time; Sort (dataSet); Note end time; Set elapsed time to difference between end and start times; Add elapsed time to totalRunTime; Set averageRunTime = totalRunTime / NumberOfRuns; The function GenerateRandomDataSet (dataSet, size) needs to generate a random set of integers of whatever size is passed into the function as an input. Create a graph (using Excel or your favorite graphing tool) that graphs data set size versus the average run time for each size. Include a plot of data set size versus f(n) = n*lg(n) as well. Submit your source code, graph, and a short (1-3 paragraph) analysis of the results (each of which contributes 10 points to the grade for this problem)
