Java Reference
In-Depth Information
6. Write a Comparator that compares String objects by the number of words they contain. Consider any nonwhitespace
string of characters to be a word. For example, “hello” comes before “I see”, which comes before “You can do it”.
7. Write a Comparator that compares String objects of a particular format. Each string is of a form such as "123456
Seattle, WA" , beginning with a numeric token that is followed by additional text tokens. Your job is to treat the
first tokens as integers and compare them in numerical order. You cannot simply compare them by using the strings'
compareTo method, since it would treat the numbers as text and not as integers. For example, "276453 Helena,
MT" is greater than "9847 New York, NY" . Use a Scanner to tokenize the strings while comparing them.
8. Write a modified version of the selection sort algorithm that selects the largest element each time and moves it to the
end of the array, rather than selecting the smallest element and moving it to the beginning. Will this algorithm be
faster than the standard selection sort? What will its complexity class (big-Oh) be?
9. Write a modified “dual” version of the selection sort algorithm that selects both the largest and smallest elements on
each pass and moves each of them to the appropriate end of the array. Will this algorithm be faster than the standard
selection sort? What predictions world you make about its performance relative to the merge sort algorithm? What
will its complexity class (big-Oh) be?
10. Implement an algorithm to shuffle an array of numbers or objects. The algorithm for shuffling should be the following:
for (each index i) {
choose a random index j where j >= i.
swap the elements at indexes i and j.
}
(The constraint about j being greater than or equal to i is actually quite important, if you want your shuffling algo-
rithm to shuffle fairly. Why?)
11. Implement a “bogus” sorting algorithm called bogo sort that uses your shuffling algorithm from the previous exer-
cise to sort an array of numbers. The bogo sort algorithm is the following:
while (array is not sorted) {
shuffle array.
}
Obviously, this is not a very efficient sorting algorithm, but it eventually does shuffle the array into order if you let it
run long enough. Try running it on a very small array, such as 8 or 10 elements, to examine its runtime. What is your
best guess about the complexity class (big-Oh) of this silly algorithm?
Programming Projects
1. Write a program that reads a series of input lines and sorts them into alphabetical order, ignoring the case of words.
The program should use the merge sort algorithm so that it efficiently sorts even a large file.
2. Perform a “Sort Detective” challenge to run several sorting algorithms without knowing which is which. Try to
figure out which sorting algorithm is which on the basis of the runtime and characteristics of each algorithm. Search
the web for “sort detective” for more ideas on such a project.
Search WWH ::




Custom Search