Lab 27 - Searching and sorting Lab 27 - Searching and sorting Purpose This laboratory looks at simple searching and sorting algorithms. Setup Download http://www.cs.uno.edu/~fred/nhText/Labs/lab27.zip into your nhLab directory and unzip. You should now have a subdirectory in your nhLab directory named lab27. Open DrJava. If DrJava is already open, close all open documents (Close All from the File pull-down menu) and clear the interactions history by choosing the Clear Interactions History option from the Tools pull-down menu. Sorting algorithms Open the file Utility.java. This file contains a utility method for generating lists of Integers. The first argument to the method genList determines how big the list will be. The second argument determines whether the list will be ascending, descending, or random. > import nhLab.lab27.*; > import nhUtilities.containers.*; > List list = Utility.genList(10,1); > list > list = Utility.genList(10,-1); > list > list = Utility.genList(10,1583); > list In the definitions pane, define a class Up that implements java.util.Comparator. This class should be in package nhLab.lab27 and should define an "increasing" order: that is, compare(i1,i2) < 0 if i1 is numerically less than i2. (Remember that Java automatically "unboxes" an Integer: that is, converts an Integer object to an int value when the context requires. If i1 and i2 are Integers, you can write i1 - i2, and Java will automatically do i1.intValue() - i2.intValue().) Save and compile. In the interactions pane, create an Up instance and test it. > import nhLab.lab27.*; > import nhUtilities.containers.*; > import java.util.Comparator; > Up up = new Up(); > up.compare(new Integer(2), new Integer(3)) > up.compare(new Integer(4), new Integer(3)) > up.compare(new Integer(3), new Integer(3)) Java automatically "boxes" as well. That is, java will convert an int to an Integer if the context requires. > up.compare(2,3) Open the file SortUtilities.java. This file contains three sort methods. The method selectionSort sorts a list using the selection sort algorithm, It takes three arguments: the List to be sorted, the Order, and a boolean. If the boolean is true, the method will display the List after each pass. The method will also write out the number of "steps" required by the algorithm to sort the List. This number is a measure of the "efficiency" of the algorithm. Recall that selection sort works by iteratively finding the "smallest" unpositioned element and putting it in place. Create a List and sort it using selection sort. > List list = Utility.genList(10,-1); > list > SortUtilities.selectionSort(list,up,true); Note that after the first pass, the smallest element is in position; after the second pass, the two smallest elements are in position; and so on. Sort the same List with bubble sort. Bubble sort shifts the "largest" unpositioned element into place on each pass. > list = Utility.genList(10,-1); > list > SortUtilities.bubbleSort(list,up,true); Bubble sort and selection sort generally take about the same number of steps. But bubble sort is written to stop as soon as the List is sorted, and so it is particularly efficient with a sorted or almost sorted List. > list > SortUtilities.bubbleSort(list,up,true); The number of steps required by selection sort and bubble sort is proportional to the square of the size of the list. If we increase the size of the list by a factor of 10, the number of steps required will increase (roughly) by a factor of 100. (Specifically, the number of steps for selection sort is (n2-n)/2, where n is the size of the list.) > list = Utility.genList(100,-1); > SortUtilities.selectionSort(list,up,false); The quick sort algorithm is almost always much faster than either bubble sort or selection sort. On average, the number of steps required by quick sort grows in proportion to n log2n, where n is the size of the list. > list = Utility.genList(10,-1); > SortUtilities.quickSort(list,up); > list = Utility.genList(100,-1); > SortUtilities.quickSort(list,up); Display Utility in the definitions pane and look at the methods ssort and bsort. Note that an "anonymous" class is instantiated in each case. These orders compare Integers based only on the low-order digit. Integers with the same low-order digit, such as 55 and 15, are considered "equivalent." Sort the same List with each of these methods and compare the result. > list = Utility.genList(30,-1); > Utility.ssort(list); > list > list = Utility.genList(30,-1); > Utility.bsort(list); > list Are the sorted lists identical? Search algorithms Open SearchUtilities.java. The class SearchUtilities contains two search algorithms, a linear search and a binary search. Create an increasing List, and search the list using linear search. > list = Utility.genList(1000,1); > SearchUtilities.linearSearch(new Integer(1001),list) If the element is not on the List, linear search must look at each element. Thus the number of steps grows in proportion to the size of the List. Search the List using binary search. To use, binary search, the list must be sorted. SearchUtilities.binarySearch(new Integer(1001),list,up) The number of steps required by binary search is proportional to log2n, where n is the size of the List. Using a sort In the class Utility, add a method stringSort that sorts a list of Strings in lexicographical (alphabetic) order. You can invoke any sort method that you want. Define the Order as an anonymous class, similar to what is done in the methods ssort and bsort. (You might find something useful by looking at the specification of the class String. You can find this, of course, in the API documentation at http://java.sun.com.) What to submit If directed by your instructor, turn in a listing of the modified class Utility. Your instructor might also require that you turn in the interactions history. You can save the interactions history by selecting the Save Interactions History... option from the Tools pull-down menu. Be sure everything you turn in is clearly labeled with your name and section number.
