Driver

import java.util.*; public class MyRecursion{ private static Integer [] oddList; private static Integer [] evenList; private static Integer [] randomOddList; private static Integer [] randomEvenList; private static Integer [] selectionSortOddList; private static Integer [] quickSortOddList; private static int selectionSortCount; private static int quickSortCount; private static int successfulLinearSearchCount; private static int unsuccessfulLinearSearchCount; private static int successfulBinarySearchCount; private static int unsuccessfulBinarySearchCount;

private static int binarySearchCount; //successfulBinarySearchCount private static int size;

public static void main (String [] args){ size = Integer.parseInt(args[0]); oddList = new Integer[size]; evenList = new Integer[size]; randomOddList = new Integer[size]; randomEvenList = new Integer[size]; selectionSortOddList = new Integer[size]; quickSortOddList = new Integer[size];

Recursion7 r = new Recursion7(); //4. populate oddList with values 1,3,5,... // oddList is sorted r.populateOddList(oddList); //r.displayList(oddList); //5. populate evenList with values 0,2,4,... // evenList is sorted r.populateEvenList(evenList); //r.displayList(evenList); //6. clone oddList into randomOddList // randomOddList is still sorted randomOddList = r.cloneList(oddList); // r.displayList(randomOddList); //7. clone evenList into randomOddList // randomEvenList is still sorted randomEvenList = r.cloneList(evenList); //r.displayList(randomEvenList); //8. shuffle randomOddList // randomOddList is random now r.shuffleList(randomOddList); //r.displayList(randomOddList); //9. shuffle randomOddList // randomEvenList is random now r.shuffleList(randomEvenList); // r.displayList(randomEvenList); //10. Clone randomOddList into selectionSortOddList // Use selection sort to sort selectionSortOddList selectionSortOddList = r.cloneList(randomOddList); selectionSortCount = r.selectionSort(selectionSortOddList); // r.displayList(selectionSortOddList); //11. Clone randomOddList into selectionSortOddList // Use quick sort to sort quickSortOddList quickSortOddList = r.cloneList(randomOddList); quickSortCount = r.quickSort(quickSortOddList); //r.displayList(randomOddList); //r.displayList(quickSortOddList);

//12. Use linearSearch to search for all values in OddList in randomOddList successfulLinearSearchCount = r.linearSearch(randomOddList, oddList); unsuccessfulLinearSearchCount = r.linearSearch(randomOddList, evenList);

//13. Use binarySearch to search for all values in randomOddList in OddList successfulBinarySearchCount = r.recursiveBinarySearch(randomOddList, oddList); unsuccessfulBinarySearchCount = r.recursiveBinarySearch(randomOddList, evenList); //14. Display counts System.out.printf (" \t1.\t%-40s%10d","List size:",size); System.out.printf (" \t2.\t%-40s%10d","Selection Sort Count:",selectionSortCount); System.out.printf (" \t3.\t%-40s%10d","Quick Sort Count:",quickSortCount); System.out.printf (" \t4.\t%-40s%10.2f","Successful Linear Search Average:",(double)successfulLinearSearchCount/size); System.out.printf (" \t5.\t%-40s%10.2f","UnSuccessful Linear Search Average:",(double)unsuccessfulLinearSearchCount/size); System.out.printf (" \t6.\t%-40s%10.2f","Successful Binary Search Average:",(double)successfulBinarySearchCount/size); System.out.printf (" \t7.\t%-40s%10.2f","UnSuccessful Binary Search Average:",(double)unsuccessfulBinarySearchCount/size); } }

Write a program named Recursion as specified in the attached UML diagram.Recursion7 should be used with the attached driver. Do not modify the driver.

Recursion
+ counts:int	To be used to count comparisons
+Recursion7 +populateEvenList(list: Integer[]):void +populateOddList(list: Integer[]): void +cloneList(list: Integer[]):Integer[] +shuffleList(list:Integer []):void +SelectionSort(list: Integer[]):int +quickSort(list: Integer[]):int -quickSort(list: Integer[], first:int, last: int):void -partition(list:Integer[], first:int, last:int):int +linearSearch(list1:Integer[],list2:Integer[]):int +recursiveBinarySearch(list1:Integer[], list2:Integer[]): int -recursiveBinarySearch(list:Integer[], key:Integer, low:int, high:int):void +displayList(list:Integer[]):void	No-argument constructor Populate the array with even values starting with 0 Populate the array with odd values starting with 1 Clone list and return its clone Shuffle the list. You may use Collections shuffle Use selection sort to sort the list. count and return the number of comparisons Use quick sort to sort the list. count and return the number of comparisons Private method to help Private helper method to find and return the partition index Searches for all numbers in lst1 in list2 and counts the number of comparisons made. When done, returns the number of comparisons. Implement recursiveBinarySearch. List2 is sorted. Search for all values in list1 against list2. Count number of comparisons. Private method that is invoked from the public recursiveBinarySearch method. Increments number of comparisons. Receives and array. It displays its values 8 per line.