Sorting algorithms - Data Structures and Problem Solving Using Java - page 391

Write a method that takes an array of Strings and returns the largest
group of words that are anagrams of each other. Do to this, sort the
array with a Comparator that compares the sorted character representa-
tion of the words. After the sort, any group of words that are ana-
grams of each other will be adjacent in the array. Test your method by
writing a program that use words read from a file.

8.34

references

The classic reference for sorting algorithms is [5]. Another reference is [3].
The Shellsort algorithm first appeared in [8]. An empirical study of its run-
ning time was done in [9]. Quicksort was discovered by Hoare [4]; that
paper also includes the quickselect algorithm and details many important
implementation issues. A thorough study of the quicksort algorithm, includ-
ing analysis for the median-of-three variant, appears in [7]. A detailed C
implementation that includes additional improvements is presented in [1].
Exercise 8.20 is based on [6]. The Ω ( N log N ) lower bound for comparison-
based sorting is taken from [2]. The presentation of Shellsort is adapted
from [10].

1. J. L. Bentley and M. D. McElroy, “Engineering a Sort Function,” Soft-
ware—Practice and Experience 23 (1993), 1249-1265.
2. L. R. Ford and S. M. Johnson, “A Tournament Problem,” American Math-
ematics Monthly 66 (1959), 387-389.
3. G. H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data
Structures , 2d ed., Addison-Wesley, Reading, MA, 1991.
4. C. A. R. Hoare, “Quicksort,” Computer Journal 5 (1962), 10-15.
5. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and
Searching, 2d ed., Addison-Wesley, Reading, MA, 1998.
6. D. R. Musser, “Introspective Sorting and Selection Algorithms,”
Software—Practice and Experience 27 (1997), 983-993.
7. R. Sedgewick, Quicksort , Garland, New York, 1978. (Originally pre-
sented as the author's Ph.D. dissertation, Stanford University, 1975.)
8. D. L. Shell, “A High-Speed Sorting Procedure,” Communications of the
ACM 2 7 (1959), 30-32.
9. M. A. Weiss, “Empirical Results on the Running Time of Shellsort,” Com-
puter Journal 34 (1991), 88-91.
10. M. A. Weiss, Efficient C Programming: A Practical Approach, Prentice
Hall, Upper Saddle River, NJ, 1995.