Name______________________________Name______________________________This lab covers some of the important ideas related to Sorting. You should print a copy of this lab so you can record your answers to questions. Turn in the completed questions and any supporting printouts as required in the lab. Here is a link to the API documentation in case you need it.
P1: Download and unzip the source files for this lab. Create a project including all of the files in the archived lab folder. Familiarize yourself with the contents of the files. Not all of the files will be used at the same time. Run the first program (SortTest) and verify that it works according to your expectations. Modify the selection sort and merge sort algorithms (in files SelectionSorter and MergeSorter) so they sort an array of Strings. Document each change with a single line comment - showing your initials, the date, and a brief change comment - of the form
//tsm: 4/8/2005 changed int to String
Modify (and document as above) the SortTest to create and sort 20 Strings of maximum length 7. Be sure to look at the methods in ArrayUtil.java. Test that the program correctly sorts strings.
P2: Close the SortTest file and open the second main program named SortTimer. Familiarize yourself with the main program and run it. This step assumes you have corectly completed the previous part of the lab. Enter various sizes for the array to be sorted. Increase the sizes until it takes approximately 15 seconds to sort the array.
What size array required approximately 15 seconds to sort? ___________________
What sort method (algorithm) was used for the sorting? ________________________
Change the main program to use merge sort instead. Try sorting the same size list as above (the one that required 15 seconds.
How long does this algorithm take? _______________(seconds)
Try some bigger lists and record the sizes and times (in seconds) for 8 cases that will adequately illustrate the growth rate of this algorithm's running time.
| Size | Seconds | Size | Seconds |
|---|---|---|---|
P3: Open the City program. The main method will be used for testing; ignore it for now. Each City object should include the city name and the state it is in (as two separate private instance members). Provide a toString method to return the city, state as a String (with the comma). You will not need any other methods.
Modify the main program to create and fill an array of these City objects. The data from the file is to be used to create the objects. The file starts with an integer indicating the number of entries; use this integer to set the array size. Subsequent lines contain city and state names, separated by a comma. Look carefully at main and see how these are parsed to a city and state. You must instantiate the corresponding City objects and insert them into an array. Print the array contents to the console (you must use the println method in ArrayUtil to do this) after reading and closing the file. A comment indicates the location of this action.
We will be using a merge sort to arrange these cities in a particular order. Look at the constructor and instance members in the GeneralMergeSort class. What type of an array can it process?
Answer: An array of ___________________
Can this class be used to sort an array of int's? ____ Explain:
Can this class sort an array of City objects? ____ Explain:
Note that the constructor requires two objects, and array and a ________________________.
Compile the GeneralMergeSorter class. What error do you get? Tell what line causes the error and why and then correct the problem by using one of the instance members of the class and one of its methods.
What line causes the error?
______________________________________________________________________
The corrected line is:
_______________________________________________________________________
Modify main (of the City class) to use a GeneralMergeSorter to sort the list of cities. You will need to write a Comparator<Object> class designed to compare City objects. You should make this a static inner class in the City class. That will allow it to access the City members directly even though they are private. It needs to be static because it does not need a this member (it operates on two City objects passed as arguments; there is no third this City). It also needs to be static because it will be instantiated from main, a static method (rather than from an instance method).
The Comparator must be a general Object Comparator (Comparator<Object>) to satisfy the requirement of the GeneralMergeSorter class. Comparator<City> is unfortunately not a subclass of Comparator<Object>; generics might be of use here, but this would be a later lab.Since you are writing a compare method that takes Object parameters, it will require casting the parameters of the compare method to City objects before accessing the city and state fields. The comparison should order by state, then by city. So if c1 and c2 are cities, c1 comes before c2 if c1's state is before c2's state. If the states are the same, the c1 comes before c2 if the c1's city is before c2's city (OH, Zanesville comes before SC, Charlotte comes before SC, Columbia). Instantiate and pass the comparator object to the GeneralMergeSorter constructor.
Your program should display the cities before and after the sort. Again, continue to use the println method provided in ArrayUtil. Be sure everything works correctly.
Print the files SelectionSorter, MergeSorter, SortTest, and City. Attach them in this order to the lab answers. Be sure your files contain your name and the current date. Submit your answers and program solutions in a single stapled package.