Java coding

3. Right-click the ds1f19lib.jar file, pull-right “Build-path” and choose “Add to Build Path”. You should then see “ds1f19lib.jar” listed under the Referenced Libraries folder

4. Download the starter file: CSC300HW8.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. Please turn in a single document file.

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.

1. Describe how you checked to see which sorts worked.

2. Describe how you used your java program to gather the data.

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? Worst?

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?

What is the purpose of the control loop in the starter file?

Sort# . (fill in blank corresponding the sort number)

For the model T(N) = cNb , what is the of order of growth exponent b:

Plot of N vs Time ( replace this sample with your plot )

Is the plot consistent with your order of growth exponent estimate?

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?

Array Create/Fill 1024 2048 4096 8192 16384 4.5785999999999998E-5 8.9303999999999997E-5 1.7908E-4 3.6664999999999999E-4 7.1666999999999998E-4 Linked List Create/Fill 1024 2048 4096 8192 16384 1.2813000000000001E-5 2.6469999999999999E-5 5.5229999999999998E-5 1.109E-4 2.1264999999999999E-4

List size N

Label goes here

Array Create/Fill 1024 2048 4096 8192 16384 4.5785999999999998E-5 8.9303999999999997E-5 1.7908E-4 3.6664999999999999E-4 7.1666999999999998E-4 Linked List Create/Fill 1024 2048 4096 8192 16384 1.2813000000000001E-5 2.6469999999999999E-5 5.5229999999999998E-5 1.109E-4 2.1264999999999999E-4

List size N

Label goes here