Q: Add five (5) classes to the code in order to make the implementation run. Specifically, you must create the classes listed under Class Required using the interface in Table 1. You are not allowed to make changes to any of the files above.

Class Required -------------------------------Interface

BinaryIterativeSearch.java-----------------Practice03Search.java

BinaryRecursiveSearch.java--------------Practice03Search.java

LinearSearch.java ---------------------------Practice03Search.java

SelectionSort.java ---------------------------Practice03Sort.java

BubbleSort.java ------------------------------Practice03Sort.java

InsertionSort.java --------------------------Practice03Sort.java

requirs:

Test your implementation by compiling and running the implementation. When you do this successfully, you should see output such as the following (although your values may be different):

linear search (on 50000-item array): total search time = 861ms. Average search time = 0.01722ms. linear search (on 100000-item array): total search time = 1500ms. Average search time = 0.015ms.

linear search (on 150000-item array): total search time = 2317ms. Average search time = 0.015446667ms.

The sorting algorithms may take quite a long time to run. You should do so only when you have the time to collect the time to leave it running uninterrupted.

public class Practice03Factory { /** * Gets a Practice03Search instance according to the parameter. * @param algoName Sorting algorithm name; must contain one of: linear, binary*{recursive|iterative}. * @return An instance of the search algorithm or null if not a valid algoName. */ public Practice03Search getSearchAlgorithm(String searchtype) { if (searchtype.contains("linear")) return new LinearSearch(); else if (searchtype.contains("binary") && searchtype.contains("recursive")) return new BinaryRecursiveSearch(); else if (searchtype.contains("binary") && searchtype.contains("iterative")) return new BinaryIterativeSearch(); return null; } /** * Gets a Practice03Sort instance according to the parameter. * @param algoName Sorting algorithm name; one of: selection, bubble, insertion. * @return An instance of the sorting algorithm or null if not a valid algoName */ public Practice03Sort getSortingAlgorithm(String algoName) { String lowercaseAlgoName = algoName.toLowerCase(); if (lowercaseAlgoName.contains("selection")) { return new SelectionSort(); } if (lowercaseAlgoName.contains("bubble")) { return new BubbleSort(); } if (lowercaseAlgoName.contains("insertion")) { return new InsertionSort(); } return null; } } Practice03Sort.java public interface Practice03Sort { void sort(int [] a); //post your answer here }

Practice03Search.java

public interface Practice03Search { public int search(int [] arr, int target); //post your answer here

}

Practice03Test.java 

import java.util.Random;

public class Practice03Test { protected final int [] ARRAY_SIZES = {50000, 100000, 150000, 200000, 250000, 300000, 350000, 400000, 450000, 500000}; protected final int SEARCH_SIZE = 50000; protected final String [] SEARCH_TYPE = {"linear", "binary-recursive", "binary-iterative"}; protected final String [] SORT_TYPE = {"selection", "bubble", "insertion"}; protected int [] arr; Practice03Factory factory = new Practice03Factory(); /** * Default (and only) constructor. Just creates the factory. */ public Practice03Test() { factory = new Practice03Factory(); } /** * Populates the array with non-decreasing random values. */ private boolean fillSearchArray () { Random rand = new Random(); int stepSize = Integer.MAX_VALUE / (arr.length * 2); arr[0] = rand.nextInt(stepSize); for (int i = 1; i < arr.length; i++) { // Generate candidates for the array. But ensure all numbers are // monotonically non-decreasing. int candidate = arr[i-1] + rand.nextInt(stepSize); if (candidate < arr[i-1]) arr[i] = arr[i-1]; else arr[i] = candidate; } return true; } /** * Executes multiple searches for values in the arr of int[]. Reports total search time * and average time (i.e. approximate time for one search). */ public void timeSearches() { Random rand = new Random(); for (String searchAlgo : SEARCH_TYPE) { Practice03Search search = factory.getSearchAlgorithm(searchAlgo); for (int size : ARRAY_SIZES) { arr = new int[size]; fillSearchArray(); long totalTime = 0; for (int i = 0; i < SEARCH_SIZE; i++) { long startTime = System.currentTimeMillis(); search.search(arr, rand.nextInt()); totalTime += System.currentTimeMillis() - startTime; } System.out.println(searchAlgo + " search (on " + size + "-item array): total search time = " + totalTime + "ms. Average search time = " + (float)totalTime / (float)arr.length + "ms."); } } } /** * Populates the array with random values. */ private void fillSortArray () { Random r = new Random(); for (int i = 0; i < arr.length; i++) { arr[i] = r.nextInt(); } } /** * Executes multiple sorts on arr of int[]. Reports total time to sort the values. */ public void timeSorts() { for (String sortAlgo : SORT_TYPE) { Practice03Sort sort = factory.getSortingAlgorithm(sortAlgo); for (int size : ARRAY_SIZES) { arr = new int[size]; fillSortArray(); long totalTime = 0; long startTime = System.currentTimeMillis(); sort.sort(arr); totalTime += System.currentTimeMillis() - startTime; System.out.println(sortAlgo + " sort (on " + size + "-item array): total sorting time = " + totalTime + "ms."); } } } public static void main(String[] args) { Practice03Test test = new Practice03Test(); test.timeSearches(); test.timeSorts(); } }