Create an Evaluator class that will evaluate the sorting algorithms you learned about in this chapter.Create 1 method for each of the sorting algorithms below. Each method must accept 1 int[]as a parameter. Ensure that the name of your method includes your last name (e.g., John Doe might use a method name like this: selectionSortDoe).

Selection sort

Insertion sort

Merge sort

Implement the code for each of the sort methods above by referring to Figures 19.4 (pp. 814815), 19.5 (pp. 817819), and 19.6 (pp. 820822) in the textbook.

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.

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.

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.

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

Take a screenshot of your output table and paste it into the Word document you created for the first exercise, but place the screen shot under a header for Exercise 2. Following the screenshot in the same document, write a brief paragraph (100200 words) on your findings that comments on whether your observed values are consistent with the Big O notation for each sorting algorithm that the textbook provides (see Figure 19.7 on p. 825). If your results differ substantially from the book, discuss why you believe your results were different. Keep in mind that the notations in Figure 19.7 are only for worst-case scenarios.

Adjust your array sizes to hold only 1,000 elements and run the 9 tests again. Take another screen shot of your output table and append to the document you created above. Add to the document a brief paragraph (100200 words) commenting on whether your newly observed values are consistent with the Big O notation that the book provides. If your results differ substantially from the book, discuss why you believe your results were different.

// Fig. 19.4: BinarySearchTest.java

// Use binary search to locate an item in an array.

import java.security.SecureRandom;

import java.util.Arrays;

import java.util.Scanner;

public class BinarySearchTest

{

// perform a binary search on the data

public static int binarySearch(int[] data, int key)

{

int low = 0; // low end of the search area

int high = data.length - 1; // high end of the search area

int middle = (low + high + 1) / 2; // middle element

int location = -1; // return value; -1 if not found

do // loop to search for element

{

// print remaining elements of array

System.out.print(remainingElements(data, low, high));

// output spaces for alignment

for (int i = 0; i < middle; i++)

System.out.print(" ");

System.out.println(" * "); // indicate current middle

// if the element is found at the middle

if (key == data[middle])

location = middle; // location is the current middle

else if (key < data[middle]) // middle element is too high

high = middle - 1; // eliminate the higher half

else // middle element is too low

low = middle + 1; // eliminate the lower half

middle = (low + high + 1) / 2; // recalculate the middle

} while ((low <= high) && (location == -1));

return location; // return location of search key

} // end method binarySearch

// method to output certain values in array

private static String remainingElements(int[] data, int low, int high)

{

StringBuilder temporary = new StringBuilder();

// append spaces for alignment

for (int i = 0; i < low; i++)

temporary.append(" ");

// append elements left in array

for (int i = low; i <= high; i++)

temporary.append(data[i] + " ");

return String.format("%s%n", temporary);

} // end method remainingElements

public static void main(String[] args)

{

Scanner input = new Scanner(System.in);

SecureRandom generator = new SecureRandom();

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

for (int i = 0; i < data.length; i++) // populate array

data[i] = 10 + generator.nextInt(90);

Arrays.sort(data); // binarySearch requires sorted array

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

// get input from user

System.out.print("Please enter an integer value (-1 to quit): ");

int searchInt = input.nextInt();

// repeatedly input an integer; -1 terminates the program

while (searchInt != -1)

{

// perform search

int location = binarySearch(data, searchInt);

if (location == -1) // not found

System.out.printf("%d was not found%n%n", searchInt);

else // found

System.out.printf("%d was found in position %d%n%n",

searchInt, location);

// get input from user

System.out.print("Please enter an integer value (-1 to quit): ");

searchInt = input.nextInt();

}

} // end main

} // end class BinarySearchTest

// Fig. 19.5: InsertionSortTest.java

// Sorting an array with insertion sort.

import java.security.SecureRandom;

import java.util.Arrays;

public class InsertionSortTest

{

// sort array using insertion sort

public static void insertionSort(int[] data)

{

// loop over data.length - 1 elements

for (int next = 1; next < data.length; next++)

{

int insert = data[next]; // value to insert

int moveItem = next; // location to place element

// search for place to put current element

while (moveItem > 0 && data[moveItem - 1] > insert)

{

// shift element right one slot

data[moveItem] = data[moveItem - 1];

moveItem--;

}

data[moveItem] = insert; // place inserted element

printPass(data, next, moveItem); // output pass of algorithm

}

}

// print a pass of the algorithm

public static void printPass(int[] data, int pass, int index)

{

System.out.printf("after pass %2d: ", pass);

// output elements till swapped 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 i = 0; i <= pass; i++)

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

insertionSort(data); // sort array

System.out.printf("Sorted array:%n%s%n%n",

Arrays.toString(data)); // display array

}

} // end class InsertionSortTest

// 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