Implement the Radix Sort algorithm using multiple queues: 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 java.io.IOException; import java.util.Scanner; import java.io.File; import java.util.ArrayList;

public class RadixSort{ public static void main(String[] argv){ QueueReferenceBased Q=null; try{ Q = new QueueReferenceBased(); //Read file radix.dat into a queue Q Scanner scan = new Scanner(new File("radix.dat")); //Calling RadSort with queue Q and the pass number while (scan.hasNextInt()) Q.enqueue(scan.nextInt()); scan.close(); } catch(IOException e){ System.err.println("error obtaining the data"); System.exit(9); } radixSort(Q); } public static void radixSort(QueueReferenceBased Q){ radix(Q, 1); } public static void radix(QueueReferenceBased Q, int k){ System.out.println("~~ sorting column "+k +" ~~"); final int NUMDIGITS = 5; // maximum number of digits in data final int NUMBASE = 10; // decimal numbers, base 10 // creation of the array ArrayList > pockets = new ArrayList >(NUMBASE); //instantiation of the array for (int i=0; i()); //enqueue the appropriate pockets /* TO COMPLETE */ // dequeue the pockets in the appropriate order // and print the elements right-aligned /* TO COMPLETE */ // Make recursive call if necessary /* TO COMPLETE */ } // end RadSort

/** find the kth digit of a number num writen in base numbase * @param num is the number considered * @param k is the position of the digit we want to know (from the right) * @param numbase is the base used to write num (ex base 10). */ public static int getKthNumber(Integer num, int k, int numbase){ return (num/(int)Math.pow(numbase,k-1))%numbase; }}// end RadixSort

QueueReferenceBased.java

public class QueueReferenceBased implements QueueInterface {

private Node lastNode; public QueueReferenceBased() { lastNode = null; } // end default constructor

public boolean isEmpty() { return lastNode == null; } // end isEmpty

public void dequeueAll() { lastNode = null;}

public void enqueue(E newItem) { Node newNode = new Node(newItem); if (isEmpty()) { newNode.setNext(newNode);} else { newNode.setNext(lastNode.getNext()); lastNode.setNext(newNode); } // end if lastNode = newNode; } public E dequeue() throws QueueException { if (!isEmpty()) { Node firstNode = lastNode.getNext(); if (firstNode == lastNode) { lastNode = null; } else { lastNode.setNext(firstNode.getNext()); } // end if return firstNode.getItem(); } else { throw new QueueException("QueueException on dequeue:" + "queue empty"); } } // end dequeue public E peek() throws QueueException { if (!isEmpty()) { // queue is not empty; retrieve front Node firstNode = lastNode.getNext(); return firstNode.getItem(); } else { throw new QueueException("QueueException on peek:" + "queue empty"); } } }

Node.java

public class Node { private E item; private Node next;

public Node(E newItem) { item = newItem; next = null; } // end constructor

public Node(E newItem, Node nextNode) { item = newItem; next = nextNode; } // end constructor

public void setItem(E newItem) { item = newItem; } // end setItem

public E getItem() { return item;} // end getItem

public void setNext(Node nextNode) { next = nextNode; } // end setNext

public Node getNext() { return next; } // end getNext } // end class Node

QueueInterface.java

public interface QueueInterface {

/** Determines whether a queue is empty. * @return Returns true if the queue is empty; * otherwise returns false. */ public boolean isEmpty();

/** Adds an item at the back of a queue. *

Precondition: newItem is the item to be inserted. *

Postcondition: If the operation was successful, newItem * is at the back of the queue. Some implementations * may throw QueueException if newItem cannot be added * to the queue. */ public void enqueue(E newItem) throws QueueException; /** Retrieves and removes the front of a queue. * @return If the queue is not empty, the item * that was added to the queue earliest is returned and * the item is removed. If the queue is empty, the * operation is impossible and QueueException is thrown. */

public E dequeue() throws QueueException;

/** Removes all items of a queue. *

Postcondition: The queue is empty. */ public void dequeueAll(); /** Retrieves the item at the front of a queue. * @return If the queue is not empty, the item * that was added to the queue earliest is returned. * If the queue is empty, the operation is impossible * and QueueException is thrown. */ public E peek() throws QueueException;} // end QueueInterface

QueueException.java

public class QueueException extends RuntimeException {

public QueueException(String s) { super(s); } }

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