For this assignment, you will be writing code to generate test data and benchmark sorting algorithms on

it $($edited from Sedgewick and Wayne: $2\mathrm{.}1\mathrm{.}36).$ Already provided for you is CompletedBenchmarkTool.java

which contains the sorting algorithms: insertion sort and shellsort. As usual, it's not complete just yet.

This class extends an interface called BenchmarkTool which denes all of the methods that you need to

create. You may create additional private helper methods. Before writing any code, you should write

up your hypotheses $(3$ per algorithm$)$ to describe what you think the running time will look like on each

algorithm$/$input combination $($see Writeup below$).$ Your rst step to benchmarking the algorithms will be

to write a series of methods to generate test data that is non$-$uniform:

$$ Implement the method public Integer$[]$ generateTestDataBinary$($int size$).$ Half the data is $0$s$,$ half $1$s$.$

For example, an input of length $8$ might look like $[0,0,0,0,1,1,1,1].$ See the interface. $[4$ points$]$

$$ Implement the method public Integer$[]$ generateTestDataHalfs$($int size$).$ Half the data is $0$s$,$ half the

remainder is $1$s$,$ half the reminder is $2$s$,$ half the reminder is $3$s$,$ and so forth. For example, an input of

length $8$ might look like $[0,0,0,0,1,1,2,3].$ See the interface. $[6$ points$]$

$$ Implement the method public Integer$[]$ generateTestDataHalfRandom$($int size$).$ Half the data is $0$s$,$

half random int values $($use nextInt$()$ from Java's Random package, and use Integer.MAX$\_$VALUE as

its argument to ensure the values are positive$).$ For example, an input of length $8$ might look like $[0,$

$0,0,0,54119567,4968,650736346,138617093].$ See the interface. $[4$ points$]$

Each of these three techniques should be implemented as a method that takes an int representing the size of

a dataset, and returns an Integer array containing that number of elements generated with the corresponding

rule. Do not randomize $($shue$)$ the contents of the generated arrays. You may assume that only arrays

with a power $2$ length will need to be created.

For each of the sorting algorithms, your program should run them on the three types of test data. Test

them with datasets size of $4096$ and $4096*2.($If your system is so fast that you don't get good results, you

may increase the dataset size. If your system continues to generate strange values even with a large dataset

size, try turning o compiler optimizations.$)$ Time each of the tests with the Stopwatch class discussed in

class. The program needs to compute the result of the doubling formula on the run times from the sample

data generated to get the power $($b$)$ for that algorithm on that type of input, and then display it$.$ Six

dierent values should be shown if you have properly implemented all of the benchmarks.

$$ Implement the method public double computeDoublingFormula$($double t$1,$ double t$2).$ See the interface

for more information. $[2$ points$]$

$$ Implement the method public double benchmarkInsertionSort$($Integer$[]$ small, Integer$[]$ large$).$ See the

interface for more information. $[2$ points$]$

$$ Implement the method public double benchmarkShellsort$($Integer$[]$ small, Integer$[]$ large$).$ See the interface for more information. $[2$ points$]$

$$ Implement the method public void runBenchmarks$($int size$).$ Whitespace is exible $($any number of

tabs or spaces$)$ but you must show three decimal places. See the interface for more information. Hint:

should call the two benchmark methods above. The output should look like b