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: 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: 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)]

}