Introduction (Java)

As we have seen in the text, the best we can hope for when sorting string using a comparison sort is O(n log n). In this chapter we saw that Radix sort could sort numbers in O(n) time. What if we could figure out a way to do a Radix sort on Strings? This assignment will challenge you to do just that. In order to make this easier for you, the following assumptions will be made:

No words will be longer than 10 characters (if there are more than 10 characters, you can ignore them)

You can convert all the words to lowercase

Words will contain only letters, no special characters, spaces or numbers

Assignment Description

The program will need to perform the following tasks:

Load a list of words from a file

Create 27 buckets (yes, I know there are only 26 letters in the alphabetthis may be a hint)

o Each bucket will need to be a Collection object, please carefully consider which object you will choose and explain why you chose that one in your comments

Process the words using the Radix sort algorithm from the book as a guide, you will need to modify the algorithm to account for words of differing lengths

Display the result of each iteration of your Radix algorithm

Be careful when choosing your Collection objects, some dont guarantee to maintain the order that items are added to them

Must have the following methods and parameters

o performRadixSortItartion( words, buckets, iteration)

Performs an iteration of the Radix sort, placing the words in the appropriate buckets (via calls to placeInBucket)

o placeInBucket(buckets, bucketLocation, word)

Place the word in the appropriate bucket based on the bucketLocation passed in

o extractFromBuckets(buckets, words)

Pull out all the words from the buckets in the appropriate order

o displayWordList(words)

Display all the words in their current order

Rubric

Code Compiles

Code Structure

Comments

Explained why the Collection object was chosen in a comment

Displayed the results of each iteration

Successfully sorted the words using a modified Radix algorithm

Use methods as outlined above

Sample Run

Iterating on index: 9

dog cactus plum ant apple cat drum pumpkin burrow manatee bookcase woodpecker

Iterating on index: 8

dog cactus plum ant apple cat drum pumpkin burrow manatee bookcase woodpecker

Iterating on index: 7

dog cactus plum ant apple cat drum pumpkin burrow manatee bookcase woodpecker

Iterating on index: 6

dog cactus plum ant apple cat drum burrow woodpecker manatee pumpkin bookcase

Iterating on index: 5

dog plum ant apple cat drum bookcase woodpecker manatee pumpkin cactus burrow

Iterating on index: 4

dog plum ant cat drum bookcase apple pumpkin burrow woodpecker manatee cactus

Iterating on index: 3

dog ant cat manatee woodpecker bookcase apple plum drum pumpkin burrow cactus

Iterating on index: 2

cactus dog pumpkin manatee woodpecker bookcase apple burrow ant cat plum drum

Iterating on index: 1

cactus manatee cat plum ant dog woodpecker bookcase apple drum pumpkin burrow

Iterating on index: 0

ant apple bookcase burrow cactus cat dog drum manatee plum pumpkin woodpecker