Start by downloading the
lab8 folder from the cs server.
This folder contains a (subset of the)
On paper, write a recursive solution for the following problems, from the codingbat page:
Here is a link to your lecture notes on Radix Sort. Please make sure to review this code, and try it on paper to sort 4 numbers, 3 digit-long each. This way you will be in a good position to start the implementation of this algorithm!
Finish up the implementation of
LinkedQueue class. Make sure you
use your notebook and pencil(s) to draw your pictures! Have your questions ready!
Set up the following instance variables:
private final int NUMBERLENGTH = 3; //the length of each number in the input. //Notice that, in this version, all input numbers have to have the same length. private final int BASE = 10; //number system we are working on private Vector<Integer> input, output; //to hold the input (unsorted) and output (sorted) numbers
In the constructor, initialize the instance variables.
Write a public method
to print the input and output.
At this point you should be able to test your code, although no sorting has happened yet.
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 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 first input number is 763, and pos is 0,
it adds the number 763 to the 3rd queue, since the number's digit at position 0 is 3.
You will need a number of
Queues, here. Use a
Vector to hold those Queues.
As for a Queue implementation, you can either use the
ArrayQueue one in the
folder you downloaded earlier, or the
LinkedQueue from today's Task 2.
Once all numbers are added to the right queue, according to the Radix Sort algorithm, get them out of the queues, into the output vector.
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.
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.