In this lab you will write a program in Java using queues to implement the Radix Sort algorithm. A skeleton of the code is provided in the RadixSort.java file. Your assignment is to complete the code for the radix method. Print out the contents of the pockets queue (one number per line, right-aligned) after each pass of the radix sort algorithm. For the input data in the file radix.dat, there will be 5 such passes. You will also require the classes related to the QueueReferenceBased class.

import ccj.*;

public class RadixSort{ static queueClass Q= new queueClass();

public static void main(String[] argv){

//Read file radix.dat into a queue Q

//Calling RadSort with queue Q and the pass number RadSort(Q, 1); }

static void RadSort(queueClass Q, int k) { final int NUMDIGITS = 5; // maximum number of digits in data final int NUMBASE = 10; // decimal numbers, base 10

QueueNode Y = new QueueNode(); queueClass pockets[] = new queueClass[10]; for (int i=0; iNUMDIGITS) // Base condition: There should be NUMDIGITS passes return; while(!Q.QueueIsEmpty()){ //Remove first item from the queue into Y. //Find the kth digit of this item. //Add this item in the appropriate pocket based on its kth digit }

//Remove items from all the pockets (from pocket0 to pocket9) and // add them to the queue Q Q.Display(); // Display the queue after each pass

RadSort(Q,k+1); //Recursive call after incrementing the pass # } // end RadSort }// end RadixSort

class QueueNode { public int num; public QueueNode link; }

class queueClass { private QueueNode front; // front item of the queue private QueueNode rear; // rear item of the queue private int count; // the number of items in the queue

/*-----------------*/ // Java's automatically defined no-arg constructor suffices /*-----------------*/ public boolean QueueIsEmpty() { return (count == 0); } /*-----------------*/ public void QueueAdd(QueueNode newNode) { if (QueueIsEmpty()) { front = rear = newNode; } else { rear.link = newNode; rear = newNode; } count++; } //end insert /*-----------------*/ public QueueNode QueueRemove() { if (count == 0) { // if the queue is empty, return null return null; } else { // otherwise, return the front item QueueNode tempItem = front; front = front.link; if (front == null) { rear = null; } count--; tempItem.link = null; return tempItem; } } //end remove /*-----------------*/ public QueueNode GetQueueFront() { if (count == 0) { // if the queue is empty, return null return null; } else { // otherwise, return the front item return front; } } //end GetQueueFront /*-----------------*/ public void Display(){ QueueNode index = front; System.out.println("Printing the queue"); while(index!=null) { System.out.println(index.num); index= index.link; } System.out.println(); } //end Display /*-----------------*/ // End of implementation. }

radix.dat

46291 09229 12245 34299 06275 94227 34218 00286 19244 38265 41290 36217 90215 03227 55221 67247 12280 79232 00231 45251 78233 45230 33221 64273 00222