Modify the selection sort algorithm to sort an array of strings.

Modify the merge sort algorithm to sort an array of strings.

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.

Bubble sort sometimes is called interchange sort or exchange sort. 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. Bubble sort is easily modified to put elements in descending order (with the largest element at the beginning of the list).

Implement a sort not covered in the book. Either invent your own sort or find information on new sorts such as the insertion sort, shell sort, tree sort, or heap sort.

The Comparable interface

Sort list of cities first by state name, then by city name. Implement a City object that contains the city and state names. For convenience, allow the program to read in cities from a file. Have your City object implement the Comparable interface.

Sample output :
     Anchorage, Alaska
     Fairbanks, Alaska
     Juneau, Alaska
     Kodiak, Alaska
     Bumblebee, Arizona
     Flagstaff, Arizona
     Phoenix, Arizona
     Tucson, Arizona
     Arkadelphia, Arkansas
     Little Rock, Arkansas
     Pine Bluff, Arkansas
     . . .

The Comparator object

Sort lists of cities first by state name, then by city name. Implement a City object that contains the city and state names. For convenience, allow the program to read in cities from a file. Do not implement the Comparable interface, but use a Comparator object.

Sample output:

     Anchorage, Alaska
     Fairbanks, Alaska
     Juneau, Alaska
     Kodiak, Alaska
     Bumblebee, Arizona
     Flagstaff, Arizona
     Phoenix, Arizona
     Tucson, Arizona
     Arkadelphia, Arkansas
     Little Rock, Arkansas
     Pine Bluff, Arkansas
     . . .

Write a program to read, save, and sort memos.

Create a Memo object. The Memo object should have fields to store a topic, a date stamp, and the memo text. Allow a user to enter multiple memos, supplying the topic and message. Your program should provide the date stamp using the java.util.Date object (creating a Date object with no arguments initializes the object to the current time and date).

Let the user choose the file name to save the memos to (or read from).

When the user chooses a file to open, ask the user whether to sort memos by topic or date. Display a numbered list of topics and dates (in the correct order). The user can view a file by choosing the number of the memo.

Save the file as an object stream.

Write a sort simulation program. Allow a user to choose the length of an array of integers. The user then chooses the contents of the array. The array can contain random integers, sorted integers, or integers in descending order, from highest value to lowest value. Run and time the selection sort, merge sort, and quicksort (use Java's Arrays.sort() method for quicksort) on the array. Output to a text area to allow the user to run multiple simulations and scroll through the results. Output should be similar to the following:

Array of length 10,000; random integers:

    Sort             Time in milliseconds
    --------------------------------------
    Selection sort        3460
    Merge sort            110
    Quick sort            90

What is the big-Oh formula for the selection sort?

What is the big-Oh formula for the merge sort?

Does this mean one of these sorts is always faster than the other? Explain.

Given the equation for big-Oh notation:

f(n) = O(g(n))

What is the relationship of f(n) to g(n) as f(n) grows?

Suppose algorithm A takes 2 seconds to process a data set of 100 records. If algorithm A is an O(n^2) algorithm, how long will it take to process a data set of 1,000 records? Of 2,000? Of 10,000?

Below is a table giving the timings of algorithm A and algorithm B on different data set sizes:

What is the approximate big-Oh for algorithm A?

What is the approximate big-Oh for algorithm B?

Modify your existing program or create a new program to read, save, sort, and search memos.

Create a Memo object. The Memo object should have fields to store a topic, a date stamp, and the memo text. Allow a user to enter multiple memos, supplying the topic and message. Your program should provide the date stamp using the java.util.Date object (creating a Date object with no arguments initializes the object to the current time and date).

Let the user choose the file name to save the memos to (or read from).

When the user chooses a file to open, ask the user whether to sort memos by topic or date. Display a numbered list of topics and dates (in the correct order). The user can view a file by choosing the number of the memo or typing in the exact topic name (use your search here).

Save the file as an object stream.

Given a city name, find the state the city is in. Implement a City object that contains a city's name and state. For convenience, allow the program to read in cities from a file. Allow the user to enter a city name. If the city is in your list, output the state the city is in, otherwise indicate that the information is not available.

What happens if there are two cities with the same name in different states?

If you search an array only once, it is more efficient to pay for an O(n) linear search than for an O(nlog(n)) sort and an O(log(n)) binary search.

How many times must you search an array to make it efficient to sort the array and use a binary search?

Write a simulation program. Allow a user to choose the size (n) of an array of integers. Fill the array with the numbers 0 to (n-1) in a random order. Randomly choose a number x between 0 and (n-1). Time how long it takes to do a linear search for x. Make a copy of the unsorted array and time how long it takes to sort the array and to do a binary search for x.

Randomly choose another number y. Time how long it takes to do a linear search for y. Time how long it takes do a binary search for y in the sorted array. Repeat at least ten times, or until the binary search is obviously faster. Output your times. Run the program for at least five different values of n