Description
In this exercise you will do a timing analysis of several array sorting methods. The goal is to empirically determine the
order of growth for an average case for each method. You will use the template form on page 2 of this document to
record your data and provide your analysis & observations (make additional copies of the form as needed –
copy/paste).
Suggested Procedure.
Prepare Eclipse
1. Start Eclipse using your usual workspace.
2. Download the jar file: CSC402Sp19.jar from the D2L submission folder. Drag this file onto the lib folder
(Package Explorer view).
3. Right-click the CSC402Sp19.jar file, pull-right “Build-path” and choose “Add to Build Path”. You should
then see “CSC402Sp19.jar” listed under the Referenced Libraries folder
4. Download the starter file: CSC402HW9.java.
5. Drag this file to the homework folder
6. Open and Run the file.
Validate the sorting routines
The jar file you added to the library has five sorting methods: Sort0, Sort1, Sort2, Sort3, Sort4.
Sort0 is just for demonstration purposes – see the assignment video; you do not need to do anything with Sort0 for
this homework. At least one of Sort1 – Sort4 does not work; i.e. does not correctly sort the data. Write a
function, isSorted() which will determine if an array is sorted (low to high). Test each of the sorts on an array of
random values. Any sort that does not work is exempt from further testing in this assignment. You will indicate
which sorts are valid by completing timing analyses for them. I.e. if you turn in completed forms for sorts 1,2,3
that will indicate that you found sort4 to be invalid.
Collect data
The forms provided indicate the array sizes for which you will need to collect data.
You are free to modify/use the provided code framework to carry out/automate data collection.
Requirements:
1. In order to approximate an ‘average case’, you will need to run each sorting method a number of times on
randomized data. This will also improve the accuracy of your order of growth estimate AND allow for the
slow Stopwatch clock to tick. You should experiment a bit to see what number M of repetitions gives
reasonable timing accuracy. Making it too big will result in some sorts taking a very long (20 min?) time.
Record the average times in the form along with the value of M used.
2. You may not use any other java classes or libraries.
3. Answer the 3 questions on page1 of the report template.
Analyze the Data
1. Compute the doubling ratio for consecutive array sizes.
2. If possible, determine the order of growth exponent.
3. Graph each set of data individually; your graphs should be similar to the sample one. I suggest you use a
spreadsheet like Excel to generate the plots; however you can use pencil/graph paper and then copy/paste the
plot into the document if you want. An excel spreadsheet ‘template’ is provided for your reference.
4. Determine if your order of growth function is consistent with the graph.
5. Note any observations
6. Create one additional chart showing all data sets together (for comparison sake).
Upload: java source file and completed forms (all in one file) to submission folder. Please delete these instructions in
the document you submit.
CSC 402 Programming Assignment 9 Report 1.0 Name Ximan Liu
1. Describe how you checked to see which sorts worked.
I made up a function named isSorted to make sure whether the sorts worked. If it is sorted
successfully, then it comes with “true” and vice versa it comes with “false”.
2. Describe how you used your java program to gather the data.
My program was completely automated to run all the tests and print out all the results. I just
copied the output to the form.
Example answers: ( you can use one of these answers if they fit what you did, otherwise delete and replace
with your answer).
I manually ran the program 20 times and added up the times and divided by 20 to get the average for
each problem size. I did this for all the working sorts.
My program was completely automated to run all the tests and print out all the results. I just copied
the output to the form.
3. Based on the evidence, which sorting routine is the best? 4 Worst? 2
For your reference: You should be able to answer the following questions.
What are the reasons that your program had to run multiple repetitions of each sorting test?
Keep the running time stable and effective. The more data collected, the accurate results of the
reaction shows.
What is the purpose of the control loop?
Compute the time for the experimental overhead.
Sort# 1 . (fill in blank)
N Time #of Reps Doubling Ratio
1024 0.000570 100 ——————
2048 0.001400 100 2.46E+00
4096 0.001680 50 1.20E+00
8192 0.003260 50 1.94E+00
16384 0.004520 50 1.39E+00
32768 0.009880 25 2.19E+00
65536 0.021080 25 2.13E+00
131072 0.050800 25 2.41E+00
262144 0.118680 25 2.34E+00
For the model T(N) = cN
b
, what is the of order of growth exponent b: 1
Plot of N vs Time ( replace this sample with your plot )
Is the plot consistent with your order of growth estimate? Yes.
y = 9E-07×0.9208
R² = 0.9801
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0 50000 100000 150000 200000 250000 300000
Chart Title
Observations:
Comparison plot page.
Replace the plot below with your plot of all the sort data sets.
What conclusions can you draw about the sorting routines from your plot?
As N is going to be larger and larger, the differences in running time are getting drastically larger due
to the different efficiency of the sorting method. The larger value b is, the more inefficient a sort
method will be.
In that case, the worst sorting method is 2, the best one is 4.
y = 9E-07×0.9208
R² = 0.9801
y = 2E-09×2.0052
R² = 0.9988
y = 3E-06×0.7299
R² = 0.9851
0
20
40
60
80
100
120
140
160
0 50000 100000 150000 200000 250000 300000
Sort 1 & Sort & Sort 4
Series1 Series2 Series3
Power (Series1) Power (Series2) Power (Series3)
