1. Create an Evaluator class that will evaluate the sorting algorithms. Create 1 method for each of the sorting algorithms below. Each method must accept 1 int[]as a parameter.

Selection sort

Insertion sort

Merge sort

Implement the code for each of the sort methods above by referring to Figures 19.6

// Fig. 19.6: SelectionSortTest.java // Sorting an array with selection sort. import java.security.SecureRandom; import java.util.Arrays;

public class SelectionSortTest { // sort array using selection sort public static void selectionSort(int[] data) { // loop over data.length - 1 elements for (int i = 0; i < data.length - 1; i++) { int smallest = i; // first index of remaining array

// loop to find index of smallest element for (int index = i + 1; index < data.length; index++) if (data[index] < data[smallest]) smallest = index;

swap(data, i, smallest); // swap smallest element into position printPass(data, i + 1, smallest); // output pass of algorithm } } // end method selectionSort

// helper method to swap values in two elements private static void swap(int[] data, int first, int second) { int temporary = data[first]; // store first in temporary data[first] = data[second]; // replace first with second data[second] = temporary; // put temporary in second }

// print a pass of the algorithm private static void printPass(int[] data, int pass, int index) { System.out.printf("after pass %2d: ", pass);

// output elements till selected item for (int i = 0; i < index; i++) System.out.printf("%d ", data[i]);

System.out.printf("%d* ", data[index]); // indicate swap

// finish outputting array for (int i = index + 1; i < data.length; i++) System.out.printf("%d ", data[i]);

System.out.printf("%n "); // for alignment

// indicate amount of array thats sorted for (int j = 0; j < pass; j++) System.out.print("-- "); System.out.println(); }

public static void main(String[] args) { SecureRandom generator = new SecureRandom();

int[] data = new int[10]; // create array

for (int i = 0; i < data.length; i++) // populate array data[i] = 10 + generator.nextInt(90);

System.out.printf("Unsorted array:%n%s%n%n", Arrays.toString(data)); // display array selectionSort(data); // sort array

System.out.printf("Sorted array:%n%s%n%n", Arrays.toString(data)); // display array } } // end class SelectionSortTest

2. Exclude any portions of the textbook code that print anything to the output window. The goal here is to evaluate the efficiency of the sort algorithms, not how quickly they can print things to the console.

3. Add 3 further methods to the Evaluator class that perform the following tasks:

Returns an array with 100,000 int values in sequential order, starting with 1 and ending with 100,000.

Returns an array with 100,000 random int values.

Returns an array with 100,000 int values in descending sequential order, starting with 100,000 and ending with 1.

4. In the main method:Use the Evaluator class to evaluate each sorting algorithm with each of the 3 arrays (best, average, and worst case) for a total of 9 distinct tests.

Store the result of System.nanoTime() before and after each call to the sorting method, and calculate the time in nano-seconds it takes to complete each test (i.e., subtract the time taken before the test from the time taken after the test).

Generate new arrays prior to each test, but do not include the generation of the arrays in the evaluation of sort time.

5. Output a table showing the best, average, and worst case times for each of the sorting algorithms