Lab $10$ : Run time for Sorting algorithms

For this lab assignment you will need to write some code and create some graphs. You may use excel to

create your graphs, or other language of your choice. Your data needs to demonstrate the experimental

running time for Selection Sort $($code in book$),$ Merge Sort $($code in book$),$ and the Arrays.sort$()$ method.

Here is a basic outline of how you need to code this assignment.

$1)$ Create several arrays of size $100,1000,10000,100000,1000000,...($you need to choose max

size appropriately$).$

$2)$ Start the stop watch $($class provided in book$).$

$3)$ Sort the array

$4)$ Stop the stop watch

$5)$ Print $($or write to a file$)$ the size of the array and the time it took to sort.

You will follow the above outline for each sorting algorithm. You will need to plot size of array $($x$-$axis$)$ vs

time $($y$-$axis$)$ on a log$-$log scale. $($This can be done easily in excel$).$ You should have all three sets of data

on the same graph. $($so use the same array sizes for all $3$ tests$).($On a log$-$log scale, all data should be a

straight line, but the slope of a O$($n$2)$ algorithm will be higher than an O$($n log n$)$ algorithm$).$ I have an

example shown below of a graph of $3$ functions on a log$-$log scale.

$110001000000100000000010000000000001000000000000000$

$1$

$100$

$10000$

$1000000$

$100000000$

$10000000000$

$1000000000000$

$100000000000000$

$1\mathrm{.}00$E$+016$

Growth Rate

n

n$^2$

$($n$^2$ n$)/2$

input size $-$ n

growth rate

You also need to include plots on a standard scale. Create a single graph with all three sorting

algorithms$$ data on that single plot.

You may print your values to the screen and copy $/$ paste into excel. Or you may create CSV files and

open them directly with excel. $($CSV file is simply a text file, with values separated by commas $$ CSV

stands for Comma Separated Values$).$

To Turn In

Turn in your java code, your excel files $($or whatever you used to create your visualization$),$ and a PDF

document with your chart, and a short report $(1-2$ pages$)$ describing how you did this assignment, and

the differences between the run times of the algorithms you tested. You can find the run times of all

algorithms on the internet. Did your experiments line up with your expectations of run time?