CSC 300 SP18 Homework 9

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: csc300.jar from the D2L submission folder. Drag this file onto the lib folder (Package Explorer view).

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

4. Download the starter file: CSC300HW9.java.

5. Drag this file to the algs11 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 300 Programming Assignment 9 Report 1.0

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?

Sort# . (fill in blank)

N	Time	#of Reps	Doubling Ratio
1024			------------------
2048
4096
8192
16384
32768
65536
131072
262144

For the model T(N) = cN^b , 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 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?

package algs11;

import csc300sp18.CSC300Sorts; // you must have the csc300.jar file installed

// and added to the build path.

import stdlib.StdOut;

import stdlib.StdRandom;

import stdlib.Stopwatch;

/*

* This is the starter file for Homework 9 Version 1.1

* Corrected descriptor in output statement

*

*

*/

public class CSC300HW9 {

// TODO 1

// write a static function: isSorted, which will check to see if an array of doubles

// passed as a parameter, is sorted.

//

// getARandomArrayOfSize

// create an array of size n and fill will random doubles

// the array is returned

public static double[] getARandomArrayOfSize( int n ){

double[] a = new double[n];

for ( int i=0; i < n; i++)

a[i] = StdRandom.uniform();

return a;

}

// this main program performs the following experiment

//

// create an array of size 1024, fill it with random data and then sort it using Sort0

//

// The experiment is done reps number of times; the average elapsed time is printed.

// Note the 'control loop' used to exclude the overhead cost

//

// you might try changing Sort0 to Sort1, Sort2, Sort3, Sort4 just to make sure

// they are 'callable' before proceeding further

//

// TODO 2: Change main, add additional methods if you want to facilitate

// collecting the data you need.

// You can automate this as much or as little as you like

//

// You may not use any other Java classes or algorithms

public static void main( String[] args) {

// TODO 3 add code to check which sorts actually work

int N = 1024; // size of data set to create and sort

int reps = 100; // number of reps to perform

double[] a;

// control loop - to compute the time for the experimental overhead

Stopwatch control = new Stopwatch();

for (int i=0; i <= reps; i++ ) {

a = getARandomArrayOfSize( N) ;

//CSC300Sorts.Sort0(a); commented out on purpose to compute overhead

}

double control_elapsed = control.elapsedTime();

// end of control loop

// experimental loop - to calculate the total time for the experiment

Stopwatch actual = new Stopwatch();

for (int i=0; i <= reps; i++ ) {

a = getARandomArrayOfSize( N) ;

CSC300Sorts.Sort3(a);

}

double actual_elapsed = actual.elapsedTime();

// end of experimental loop

// determine average time for doing just the sorting

// by subtracting off the overhead time, dividing by the number of reps

double averageTime = ( actual_elapsed - control_elapsed)/reps;

StdOut.format("Number of Reps: %10d elapsed time %10.6f ", reps, averageTime);

}

}

CSC300.jar file

// Compiled from CSC300Sorts.java (version 1.8 : 52.0, super bit)

public class csc300sp18.CSC300Sorts {

// Method descriptor #6 ()V

// Stack: 1, Locals: 1

public CSC300Sorts();

0 aload_0 [this]

1 invokespecial java.lang.Object() [8]

4 return

Line numbers:

[pc: 0, line: 6]

Local variable table:

[pc: 0, pc: 5] local: this index: 0 type: csc300sp18.CSC300Sorts

// Method descriptor #15 ([D)V

// Stack: 6, Locals: 13

public static void Sort0(double[] a);

0 aload_0 [a]

1 arraylength

2 istore_1 [N]

3 ldc2_w [16]

6 dstore_2 [start]

7 ldc2_w [18]

10 dstore 4 [range]

12 invokestatic java.lang.Math.random() : double [20]

15 dload 4 [range]

17 dmul

18 dload_2 [start]

19 dadd

20 dstore 6 [power]

22 iconst_0

23 istore 8 [k]

25 goto 89

28 iconst_0

29 istore 9 [i]

31 goto 72

34 iconst_1

35 istore 10 [j]

37 goto 63

40 aload_0 [a]

41 iload 9 [i]

43 daload

44 dstore 11 [tmp]

46 aload_0 [a]

47 iload 9 [i]

49 aload_0 [a]

50 iload 10 [j]

52 daload

53 dastore

54 aload_0 [a]

55 iload 10 [j]

57 dload 11 [tmp]

59 dastore

60 iinc 10 1 [j]

63 iload 10 [j]

65 iload_1 [N]

66 if_icmplt 40

69 iinc 9 1 [i]

72 iload 9 [i]

74 i2d

75 iload_1 [N]

76 i2d

77 dload 6 [power]

79 invokestatic java.lang.Math.pow(double, double) : double [26]

82 dcmpg

83 iflt 34

86 iinc 8 1 [k]

89 iload 8 [k]

91 iload_1 [N]

92 if_icmplt 28

95 aload_0 [a]

96 invokestatic java.util.Arrays.sort(double[]) : void [30]

99 return

Line numbers:

[pc: 0, line: 9]

[pc: 3, line: 11]

[pc: 7, line: 12]

[pc: 12, line: 13]

[pc: 22, line: 14]

[pc: 28, line: 15]

[pc: 34, line: 16]

[pc: 40, line: 17]

[pc: 46, line: 18]

[pc: 54, line: 19]

[pc: 60, line: 16]

[pc: 69, line: 15]

[pc: 86, line: 14]

[pc: 95, line: 22]

[pc: 99, line: 23]

Local variable table:

[pc: 0, pc: 100] local: a index: 0 type: double[]

[pc: 3, pc: 100] local: N index: 1 type: int

[pc: 7, pc: 100] local: start index: 2 type: double

[pc: 12, pc: 100] local: range index: 4 type: double

[pc: 22, pc: 100] local: power index: 6 type: double

[pc: 25, pc: 95] local: k index: 8 type: int

[pc: 31, pc: 86] local: i index: 9 type: int

[pc: 37, pc: 69] local: j index: 10 type: int

[pc: 46, pc: 60] local: tmp index: 11 type: double

Stack map table: number of frames 6

[pc: 28, full, stack: {}, locals: {double[], int, double, double, double, int}]

[pc: 34, append: {int}]

[pc: 40, append: {int}]

[pc: 63, same]

[pc: 72, chop 1 local(s)]

[pc: 89, chop 1 local(s)]

// Method descriptor #15 ([D)V

// Stack: 1, Locals: 1

public static void Sort2(double[] a);

0 aload_0 [a]

1 invokestatic java.util.Arrays.sort(double[]) : void [30]

4 return

Line numbers:

[pc: 0, line: 26]

[pc: 4, line: 28]

Local variable table:

[pc: 0, pc: 5] local: a index: 0 type: double[]

// Method descriptor #15 ([D)V

// Stack: 5, Locals: 6

public static void Sort3(double[] a);

0 aload_0 [a]

1 arraylength

2 istore_1 [N]

3 iconst_0

4 istore_2 [i]

5 goto 58

8 iconst_1

9 istore_3 [j]

10 goto 48

13 aload_0 [a]

14 iload_3 [j]

15 daload

16 aload_0 [a]

17 iload_3 [j]

18 iconst_1

19 isub

20 daload

21 dcmpg

22 ifge 45

25 aload_0 [a]

26 iload_3 [j]

27 daload

28 dstore 4 [tmp]

30 aload_0 [a]

31 iload_3 [j]

32 aload_0 [a]

33 iload_3 [j]

34 iconst_1

35 isub

36 daload

37 dastore

38 aload_0 [a]

39 iload_3 [j]

40 iconst_1

41 isub

42 dload 4 [tmp]

44 dastore

45 iinc 3 1 [j]

48 iload_3 [j]

49 iload_1 [N]

50 iload_2 [i]

51 isub

52 if_icmplt 13

55 iinc 2 1 [i]

58 iload_2 [i]

59 iload_1 [N]

60 if_icmplt 8

63 return

Line numbers:

[pc: 0, line: 32]

[pc: 3, line: 33]

[pc: 8, line: 34]

[pc: 13, line: 35]

[pc: 25, line: 36]

[pc: 30, line: 37]

[pc: 38, line: 38]

[pc: 45, line: 34]

[pc: 55, line: 33]

[pc: 63, line: 42]

Local variable table:

[pc: 0, pc: 64] local: a index: 0 type: double[]

[pc: 3, pc: 64] local: N index: 1 type: int

[pc: 5, pc: 63] local: i index: 2 type: int

[pc: 10, pc: 55] local: j index: 3 type: int

[pc: 30, pc: 45] local: tmp index: 4 type: double

Stack map table: number of frames 5

[pc: 8, append: {int, int}]

[pc: 13, append: {int}]

[pc: 45, same]

[pc: 48, same]

[pc: 58, chop 1 local(s)]

// Method descriptor #15 ([D)V

// Stack: 6, Locals: 12

public static void Sort1(double[] a);

0 aload_0 [a]

1 arraylength

2 istore_1 [N]

3 ldc2_w [52]

6 dstore 4 [start]

8 ldc2_w [54]

11 dstore 6 [range]

13 invokestatic java.lang.Math.random() : double [20]

16 dload 6 [range]

18 dmul

19 dload 4 [start]

21 dadd

22 dstore 8 [power]

24 iconst_0

25 istore 10 [i]

27 goto 69

30 iconst_1

31 istore 11 [j]

33 goto 60

36 aload_0 [a]

37 iload 10 [i]

39 daload

40 dstore_2 [tmp]

41 aload_0 [a]

42 iload 10 [i]

44 aload_0 [a]

45 iload 11 [j]

47 daload

48 dastore

49 aload_0 [a]

50 iload 11 [j]

52 aload_0 [a]

53 iload 10 [i]

55 daload

56 dastore

57 iinc 11 1 [j]

60 iload 11 [j]

62 iload_1 [N]

63 if_icmplt 36

66 iinc 10 1 [i]

69 iload 10 [i]

71 i2d

72 iload_1 [N]

73 i2d

74 dload 8 [power]

76 invokestatic java.lang.Math.pow(double, double) : double [26]

79 dcmpg

80 iflt 30

83 aload_0 [a]

84 invokestatic java.util.Arrays.sort(double[]) : void [30]

87 aload_0 [a]

88 arraylength

89 iconst_1

90 if_icmpgt 103

93 new java.lang.ArrayIndexOutOfBoundsException [56]

96 dup

97 ldc [58]

99 invokespecial java.lang.ArrayIndexOutOfBoundsException(java.lang.String) [60]

102 athrow

103 aload_0 [a]

104 iconst_0

105 daload

106 dstore_2 [tmp]

107 aload_0 [a]

108 iconst_0

109 aload_0 [a]

110 iconst_1

111 daload

112 dastore

113 aload_0 [a]

114 iconst_1

115 dload_2 [tmp]

116 dastore

117 iconst_0

118 istore 10 [i]

120 goto 173

123 dconst_1

124 invokestatic java.lang.Math.random() : double [20]

127 aload_0 [a]

128 arraylength

129 iconst_1

130 isub

131 i2d

132 dmul

133 dadd

134 d2i

135 istore 11 [pos]

137 iload 11 [pos]

139 iconst_1

140 iadd

141 aload_0 [a]

142 arraylength

143 iconst_1

144 isub

145 if_icmpge 170

148 aload_0 [a]

149 iload 11 [pos]

151 daload

152 dstore_2 [tmp]

153 aload_0 [a]

154 iload 11 [pos]

156 aload_0 [a]

157 iload 11 [pos]

159 iconst_1

160 iadd

161 daload

162 dastore

163 aload_0 [a]

164 iload 11 [pos]

166 iconst_1

167 iadd

168 dload_2 [tmp]

169 dastore

170 iinc 10 1 [i]

173 iload 10 [i]

175 bipush 25

177 if_icmplt 123

180 return

Line numbers:

[pc: 0, line: 45]

[pc: 3, line: 48]

[pc: 8, line: 49]

[pc: 13, line: 50]

[pc: 24, line: 51]

[pc: 30, line: 52]

[pc: 36, line: 53]

[pc: 41, line: 54]

[pc: 49, line: 55]

[pc: 57, line: 52]

[pc: 66, line: 51]

[pc: 83, line: 58]

[pc: 87, line: 59]

[pc: 93, line: 60]

[pc: 103, line: 61]

[pc: 107, line: 62]

[pc: 113, line: 63]

[pc: 117, line: 64]

[pc: 123, line: 65]

[pc: 137, line: 66]

[pc: 148, line: 67]

[pc: 153, line: 68]

[pc: 163, line: 69]

[pc: 170, line: 64]

[pc: 180, line: 72]

Local variable table:

[pc: 0, pc: 181] local: a index: 0 type: double[]

[pc: 3, pc: 181] local: N index: 1 type: int

[pc: 41, pc: 60] local: tmp index: 2 type: double

[pc: 107, pc: 181] local: tmp index: 2 type: double

[pc: 8, pc: 181] local: start index: 4 type: double

[pc: 13, pc: 181] local: range index: 6 type: double

[pc: 24, pc: 181] local: power index: 8 type: double

[pc: 27, pc: 83] local: i index: 10 type: int

[pc: 33, pc: 66] local: j index: 11 type: int

[pc: 120, pc: 180] local: i index: 10 type: int

[pc: 137, pc: 170] local: pos index: 11 type: int

Stack map table: number of frames 8

[pc: 30, full, stack: {}, locals: {double[], int, _, _, double, double, double, int}]

[pc: 36, append: {int}]

[pc: 60, same]

[pc: 69, chop 1 local(s)]

[pc: 103, chop 1 local(s)]

[pc: 123, full, stack: {}, locals: {double[], int, double, double, double, double, int}]

[pc: 170, same]

[pc: 173, same]

// Method descriptor #15 ([D)V

// Stack: 6, Locals: 12

public static void Sort4(double[] a);

0 aload_0 [a]

1 arraylength

2 istore_1 [N]

3 ldc2_w [65]

6 dstore_2 [start]

7 ldc2_w [67]

10 dstore 4 [range]

12 invokestatic java.lang.Math.random() : double [20]

15 dload 4 [range]

17 dmul

18 dload_2 [start]

19 dadd

20 dstore 6 [power]

22 iconst_0

23 istore 8 [i]

25 goto 66

28 iconst_1

29 istore 9 [j]

31 goto 57

34 aload_0 [a]

35 iload 8 [i]

37 daload

38 dstore 10 [tmp]

40 aload_0 [a]

41 iload 8 [i]

43 aload_0 [a]

44 iload 9 [j]

46 daload

47 dastore

48 aload_0 [a]

49 iload 9 [j]

51 dload 10 [tmp]

53 dastore

54 iinc 9 1 [j]

57 iload 9 [j]

59 iload_1 [N]

60 if_icmplt 34

63 iinc 8 1 [i]

66 iload 8 [i]

68 i2d

69 iload_1 [N]

70 i2d

71 dload 6 [power]

73 invokestatic java.lang.Math.pow(double, double) : double [26]

76 dcmpg

77 iflt 28

80 aload_0 [a]

81 invokestatic java.util.Arrays.sort(double[]) : void [30]

84 return

Line numbers:

[pc: 0, line: 75]

[pc: 3, line: 77]

[pc: 7, line: 78]

[pc: 12, line: 79]

[pc: 22, line: 81]

[pc: 28, line: 82]

[pc: 34, line: 83]

[pc: 40, line: 84]

[pc: 48, line: 85]

[pc: 54, line: 82]

[pc: 63, line: 81]

[pc: 80, line: 88]

[pc: 84, line: 89]

Local variable table:

[pc: 0, pc: 85] local: a index: 0 type: double[]

[pc: 3, pc: 85] local: N index: 1 type: int

[pc: 7, pc: 85] local: start index: 2 type: double

[pc: 12, pc: 85] local: range index: 4 type: double

[pc: 22, pc: 85] local: power index: 6 type: double

[pc: 25, pc: 80] local: i index: 8 type: int

[pc: 31, pc: 63] local: j index: 9 type: int

[pc: 40, pc: 54] local: tmp index: 10 type: double

Stack map table: number of frames 4

[pc: 28, full, stack: {}, locals: {double[], int, double, double, double, int}]

[pc: 34, append: {int}]

[pc: 57, same]

[pc: 66, chop 1 local(s)]

// Method descriptor #15 ([D)V

// Stack: 4, Locals: 2

public static void fill(double[] x);

0 iconst_0

1 istore_1 [i]

2 goto 14

5 aload_0 [x]

6 iload_1 [i]

7 invokestatic java.lang.Math.random() : double [20]

10 dastore

11 iinc 1 1 [i]

14 iload_1 [i]

15 aload_0 [x]

16 arraylength

17 if_icmplt 5

20 return

Line numbers:

[pc: 0, line: 92]

[pc: 5, line: 93]

[pc: 11, line: 92]

[pc: 20, line: 95]

Local variable table:

[pc: 0, pc: 21] local: x index: 0 type: double[]

[pc: 2, pc: 20] local: i index: 1 type: int

Stack map table: number of frames 2

[pc: 5, append: {int}]

[pc: 14, same]

// Method descriptor #72 ([Ljava/lang/String;)V

// Stack: 2, Locals: 4

public static void main(java.lang.String[] args);

0 iconst_1

1 istore_1 [reps]

2 goto 35

5 iconst_2

6 istore_2 [i]

7 goto 25

10 iload_2 [i]

11 newarray double [7]

13 astore_3 [x]

14 aload_3 [x]

15 invokestatic csc300sp18.CSC300Sorts.fill(double[]) : void [73]

18 aload_3 [x]

19 invokestatic csc300sp18.CSC300Sorts.Sort3(double[]) : void [75]

22 iinc 2 10 [i]

25 iload_2 [i]

26 sipush 10000

29 if_icmplt 10

32 iinc 1 1 [reps]

35 iload_1 [reps]

36 bipush 100

38 if_icmplt 5

41 ldc [77]

43 invokestatic stdlib.StdOut.println(java.lang.Object) : void [79]

46 return

Line numbers:

[pc: 0, line: 97]

[pc: 5, line: 98]

[pc: 10, line: 99]

[pc: 14, line: 100]

[pc: 18, line: 101]

[pc: 22, line: 98]

[pc: 32, line: 97]

[pc: 41, line: 104]

[pc: 46, line: 105]

Local variable table:

[pc: 0, pc: 47] local: args index: 0 type: java.lang.String[]

[pc: 2, pc: 41] local: reps index: 1 type: int

[pc: 7, pc: 32] local: i index: 2 type: int

[pc: 14, pc: 22] local: x index: 3 type: double[]

Stack map table: number of frames 4

[pc: 5, append: {int}]

[pc: 10, append: {int}]

[pc: 25, same]

[pc: 35, chop 1 local(s)]

}