But if this does not compile on your computer you can start here
Let's do a quick example to refresh your memory on how Radix sort works. Take a few mins to run the algorithm on your notebook sorting these numbers:
540 145 420 542
Open the project you downloaded. In the RadixSort class, set up the following instance variables:
private final int NUMBERLENGTH = 3; //the length of each number in the input.
//Notice that, in this early version, all numbers to be sorted need to have the same number of digits.
private final int BASE = 10; //number system we are working on
private Vector<Integer> input, output; //one to hold the input (unsorted) and one the output (sorted) numbers
In the constructor, as always, initialize the instance variables:
Fill in the input vector with some 3-digit integers of your choice.
Write a public method toString()
to print the input and output.
At this point you should be able to test your code, although no sorting has happened yet.
Write a main()
method to do so.
This part may not be difficult to understand, but it is a bit hairy to write in Java. We encourage you to check the following methods in the Java API. Make a note, with an example, of them in your notebook:
Write a private method, processOnePosition(int pos)
, which does exactly that:
For each number in the output vector, it looks at its digit at position pos
, and adds the
number to the corresponding queue.
For example, if the input number is 763, and pos is 1, it adds the number 763 to the 6th queue, since the number's digit at position 1 is 6.
You will need a number of Queue
s, here. Use a Vector
to hold those Queues.
As for a Queue implementation, you can use the LinkedQueue
in javafoundations
.
Once each number is added to the correct queue -according to the Radix Sort algorithm-, move them out of those queues, into the output vector.
At this point TEST your method! Do not move on until you make sure this method works well!
Write a public method processAll()
, which processes all the positions in the
numbers, one after the other. This method should call the previous one, and be only a couple of lines long.
Think carefully which position you want to process first, and which last!
Lastly, test your code thoroughly.
If you have any extra time, think about how you would change your code to work on numbers of varying lengths.
Like the other Queue implementations seen in class, LinkedQueue will also be part of the javafoundations package.
Steps:
main()
method to test your implementation. Should this class be part of the javafoundations package?Now you are ready to start your coding in the LinkedQueue.java file. Some questions to consider with your partner:
Some recommendations: