Labs 5, 6 and 7

Recursive Binary Search and Sorts

Open the project , “Labs 5-7..”, in BlueJ. Open and read ArrayUtil. This class will create random arrays of integers to sort and search. Next look at SortTest. This class holds the main method and it gives code similar to what you will need in each lab. SelectionSorter and BinarySearcher are also complete, working classes. You will add a method to BinarySearcher (Lab 5) so it can search recursively. In MergeSorter, you will write the merge method, following the comments to write the code (Lab 6). Finally, you will completely document the QuickSorter (Lab 7).

Lab 5 – Recursive Binary Search

Create a class, Lab5, and copy the code from SortTest into your new class. Change only the line

index = searcher.search(i);

to

index = searcher.recursiveSearch(i);

In the class, Binary Searcher, add the method, recursiveSearch. This method should set the low and the high and then call a new search method (note it has a different signature than the original search).

public int search(int v, int low, int high)

This method will call itself recursively until either high is less than low (not found, returns -1) or the middle element is v (found, returns mid).

Lab 6- Merge Sort

Create a class, Lab 6, and copy the code from SortTest into your new Class. Change only the line

SelectionSorter sorter = new SelectionSorter(a);

to

MergeSorter sorter = new MergeSorter(a);

Read the code and documentation for the MergeSorter and complete the sort method.

Lab 7 - Quicksort

Create a class, Lab 7, and copy the code from SortTest into your new Class. Change only the line

SelectionSorter sorter = new SelectionSorter(a);

to

QuickSorter sorter = new QuickSorter(a);

and delete the searching code.

Read the code in the class QuickSorter. Work the code line by line (transmogrifying it) with a very short array {12, 9, 18, 31, 5}. Write down your work neatly. If you have trouble, put System.out.println’s in to trace the change in the variables as the code is executed with random arrays of different lengths.

Finally, explain the quick sort algorithm in the documentation at the top of the program. Properly document each method, both for extraction and especially for explaining each line of code (inline).