Question
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;
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
6 dstore_2 [start]
7 ldc2_w
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
6 dstore 4 [start]
8 ldc2_w
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
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
6 dstore_2 [start]
7 ldc2_w
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
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)]
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started