Programming Language

Java

Introduction 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:

• Display your name and email address as the first output

• Display the following under your name: I certify that this is my own work

• Load a list of words from a file

• Create 27 buckets (yes, I know there are only 26 letters in the alphabet...this 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

Text File content

dog cactus plum ant APPLE cat Drum pumPkin burrow manatee woodpecker bookcase

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