1 Modify the selection sort algorithm to sort an array of strings. Answer:

 2 Modify the merge sort algorithm to sort an array of strings. Answer:

 3 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). Answer:

 4 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. Answer:

 5 The Comparable interfaceSort 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      . . . Answer:

 6 The Comparator objectSort 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      . . . Answer:

 7 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. Answer:

 8 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 Answer:

 9 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. Answer:

 10 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? Answer:

 11 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? Answer:

12.

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

 Time in milliseconds
 Number of elements Algorithm A Algorithm B
 100 2 1.73
 200 2.3 6.62
 300 2.5 14.2
 400 2.6 25.76
 500 2.7 41.33

What is the approximate big-Oh for algorithm A?

What is the approximate big-Oh for algorithm B?