Big Java / Java Concepts Lab 19

Sorting

1.

Add a counter to the MergeSorter that counts how many times the algorithm compares two array elements. Supply a method getCounter to retrieve the counter. Then run the following experiment. For n = 10000, 20000, . . ., 100000, prepare an array with descending integer values n, n - 1, n - 2, . . .,3, 2, 1. Pass it to the MergeSorter, then print out how many comparisons were made.

What results did you get?


2.

Implement the bubble sort algorithm.

The bubble sort is so called because it compares adjacent items, "bubbling" the smaller one up toward the beginning of the list. By comparing all pairs of adjacent items starting at the end of the list, the smallest item is guaranteed to reach the beginning of the list at the end of the first pass.

The second pass begins again at the end of the list, ultimately placing the second smallest item in the second position in the list. During the second pass, there is no need to compare the first and second items, since the smallest element is guaranteed to be in the first position.

Bubble sort takes at most n-1 passes for a list of n items. During the first pass, n-1 pairs need to be compared. During the second pass, n-2 pairs need to be compared. During the ith pass, n-i pairs need to be compared. During the last pass, n-(n-1) or one pair needs to be compared. If, during any pass, no two adjacent items need to be interchanged, the list is in order and the sort can terminate. If it continues, no further interchanges will occur.

A variation on the bubble sort starts each pass at the beginning of the list, interchanging items as needed so that a larger item "sinks" below a smaller item following each comparison. Such a sort might be called a "rock sort," but this term is not in common usage.

What is the code of your BubbleSorter class?


3.

Describe the efficiency of the bubble sort algorithm and represent it in Big-Oh notation.


4.

A variation on the bubble sort starts each pass at the beginning of the list, interchanging items as needed so that a larger item "sinks" below a smaller item following each comparison. (Such a sort might be called a "rock sort," but this term is not in common usage.)

Implement this variation. What is the code for your sort method?

Comparable and Comparator

5.

We want to sort a list of cities by name; however, if there are two cities with the same name, then we use the state name as tie breaker. Implement a City class and a constructor

public City(String name, String state)

Also supply a toString method--we will need it for testing.

Have your City object implement the Comparable<City> interface.

What is the code of your City class?


6.

Write a tester class that populates an ArrayList<City> with cities and then sorts it. What is the code of your tester class? Remember that you can use Collections.sort to sort an array list.


7.

Now we want to sort lists of cities first by state name, then by city name, without modifying the implementation of the City class. That means, you cannot redefine the compareTo method. Instead, define a CityComparator class that implements the Comparator<City> interface.

public class CityComparator implements Comparator<City>
{
    public int compare(City a, City b)
    {
       . . .
    }
}

What is the code of your CityComparator class?


8.

Write a tester class that populates an ArrayList<City> with cities and then sorts it, using a CityComparator. What is the code of your tester class? 


Binary Search

9.

We will implement a "guess your name" game. The computer will guess your last name:

This program tries to guess your last name, but you have to give some hints.
Does your name come before "MYERSCOUGH" in the dictionary? (Y/N) Y
Does your name come before "ISENBERG" in the dictionary? (Y/N) Y
Does your name come before "DIMAGGIO" in the dictionary? (Y/N) N
Does your name come before "GALLUP" in the dictionary? (Y/N) N

. . .
Is your name "HORSTMANN"? (Y/N) Y

Start out with a program that reads all names from the "last names" file at http://www.census.gov/genealogy/names/. Discard the statistical information. Sort the names, using Collections.sort.


What is the code for reading all names and sorting them?



10.

At the beginning of the search,  set low to 0 and high to the maximum index of the names list. Set mid to the average of low and high, then ask the user if the name comes before the list entry at index mid. Depending on the answer, update low or high. If low == high, ask if the name matches.

What is the code for your program?


11.

How many entries does your names list have? How many guesses does your program need to make until it has guessed the user's name or given up?