The following Java program exercises a few sorting algorithms from the authors library and writes out the results for different data set sizes. You are to complete the code; theres some missing in the run() method. Note that to run the Insertion sort algorithm on a set of data, you call Selection.sort(data); the other algorithms work in the same manner. Your code should use the methods of the Stopwatch object to compute the time each algorithm takes. For each algorithm, append the answer onto the result string, so that the run() method returns something like this: Size: 10 Selection: 0.001 Insertion: 0.0 Merge: 0.0 Quick: 0.002

import edu.princeton.cs.algs4.*;

import java.util.Arrays;

import java.util.Random;

public class HW3 {

// an array to hold the various data set sizes to be tested

private static final int DATASIZES[] = {10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000,

500000, 1000000};

public HW3() {

}

// this method takes one size, generates a random set of ints, times all of the searcj algorithms and

// returns a String of the results

public String run(int size) {

Integer data[], masterData[];

Stopwatch sw = new Stopwatch();

Random r = new Random();

double thistime, lasttime;

String resultStr = "Size: " + size;

// fill master array so all algorithms get the same data

masterData = new Integer[size];

data = new Integer[size];

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

masterData[i] = r.nextInt();

}

// run the selection sort and add time to results string

data = Arrays.copyOf(masterData, size);

<< YOUR CODE GOES HERE >>

// run the Insertion sort and add time to results string

data = Arrays.copyOf(masterData, size);

<< YOUR CODE GOES HERE >>

// run the Merge sort and add time to results string

data = Arrays.copyOf(masterData, size);

<< YOUR CODE GOES HERE >>

// run the quick sort and add time to results string

data = Arrays.copyOf(masterData, size);

<< YOUR CODE GOES HERE >>

return resultStr;

}

public static void main(String[] args) {

HW3 trial = new HW3(); // create a new HW3 object

for (int size : DATASIZES) { // get results for each data set size and print it out

System.out.println(trial.run(size));

}

}

}