Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

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.

RadixSort.java

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. }

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Business Process Driven Database Design With Oracle PL SQL

Authors: Rajeev Kaula

1st Edition

1795532386, 978-1795532389

More Books

Students also viewed these Databases questions

Question

Connect with your audience

Answered: 1 week ago