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. 814–815), 19.5 (pp. 817–819), and 19.6 (pp. 820–822) 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 (100–200 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 (100–200 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)
{