Lab on Queues

RadixSort.java

Task 1 Queue Application: RadixSort

• Download the folder lab8 starting code

But if this does not compile on your computer you can start here

Task 1A: What is RadixSort?

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

Task 1B: Set up the RadixSort class

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
  

Task 1C: Constructor

In the constructor, as always, initialize the instance variables:

• Fill in the input vector with some 3-digit integers of your choice.

• Copy the input vector into the output vector. You will be working on the output vector, while maintaining the input unchanged, for printing purposes at the end.

Task 1D: toString() and main()

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.

Task 1E: processOnePosition()

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:

• valueOf(), in the String class.
• charAt(), in the String class. (You have used this method in the past).
• getNumericValue(), in the Character class.

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 Queues, 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!

Task 1F: processAll()

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.

Task 2: LinkedQueue Implementation

Like the other Queue implementations seen in class, LinkedQueue will also be part of the javafoundations package.

Steps:

• Download the folder lab8 starting code It should contain a javafoundations folder that you can use in the LinkedQueue implementation task.
• Create a new folder on your Desktop and name it lab8_yourUserNames. You will use this folder for your work.
• In that folder create a new Project, named lab8Project.
• Start by creating a new class, named QueueDriver.java for testing your Queue implementation. It should only have a main() method to test your implementation. Should this class be part of the javafoundations package?
• Knowing the Queue interface, write some testing code now, before starting the coding of LinkedQueue. Try to compile this class. What do you notice?
• In your lab8Project, import the javafoundations package from the downloaded material. Remember, in order to import it correctly, you need to open the lab8 folder you downloaded that contains the javafoundations package, not the package itself!

Now you are ready to start your coding in the LinkedQueue.java file. Some questions to consider with your partner:

• Where should the LinkedQueue.java file be saved?
• What interface should the class implement?
• How can you be sure that you are not missing any method that needs implementation? (Hint: If you copy and paste all the methods in the interface as they appear, the compiler will complain because there is no code for each one of them. How can you silence temporarily the compiler by adding code stubs?)

Some recommendations:

• Start with declaring instance variables, then define the constructor.
• Test every method right after you write it. Test it by adding testing code to the QueueDriver.java code.