# Lab

## Set up

Start by downloading the `lab8` folder from the cs server. This folder contains a (subset of the)`javafoundations` classes.

On paper, write a recursive solution for the following problems, from the codingbat page:

A. array11()

B. countPairs()

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!

#### [END PRELAB ]

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.

• Fill in the input vector with some integers. Each one should have length 3 (NUMBERLENGTH).
• 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 3C: 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.

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:

• 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 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 `Queue`s, here. Use a `Vector` to hold those Queues. As for a Queue implementation, you can either use the `ArrayQueue` one in the `javafoundations` 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.