I need to create a radixsort datastructures but I have no idea how. I have to fi

Question

I need to create a radixsort datastructures but I have no idea how. I have to fill in the Radixsort.java file where it says //Write your code here
I cannot use any imports or add any methods or change any methods/classes etc. I tried this on my own but keep getting exception in thread main errors. Also, I'm not allowed to change any methods or add any import statements. When you run sorter.java, you should get an output of the txtfile in radrixsort. PLEASE test the program for me! I'm using Eclipse

-------------------------------------------------------------------------------------------------------------------------

package apps;

import java.io.IOException;
import java.util.Scanner;

import structures.Node;

/**
* This class sorts a given list of strings which represent numbers in
* the given radix system. For instance, radix=10 means decimal numbers;
* radix=16 means hexadecimal numbers.
*
* @author ru-nb-cs112
*/
public class Radixsort {

/**
* Master list that holds all items, starting with input, and updated after every pass
* of the radixsort algorithm. Holds sorted result after the final pass. This is a
* circular linked list in which every item is stored in its textual string form (even
* though the items represent numbers). This masterListRear field points to the last
* node in the CLL.
*/
Node<String> masterListRear;

/**
* Array of linked lists that holds the digit-wise distribution of the items during
* each pass of the radixsort algorithm.
*/
Node<String>[] buckets;

/**
* The sort radix, defaults to 10.
*/
int radix=10;

/**
* Initializes this object with the given radix (10 or 16)
*
* @param radix
*/
public Radixsort() {
  masterListRear = null;
  buckets = null;
}

/**
* Sorts the items in the input file, and returns a CLL containing the sorted result
* in ascending order. The first line in the input file is the radix. Every subsequent
* line is a number, to be read in as a string.
*
* The items in the input are first read and stored in the master list, which is a CLL that is referenced
* by the masterListRear field. Next, the max number of digits in the items is determined. Then,
* scatter and gather are called, for each pass through the items. Pass 0 is for the least
* significant digit, pass 1 for the second-to-least significant digit, etc. After each pass,
* the master list is updated with items in the order determined at the end of that pass.
*
* NO NEW NODES are created in the sort process - the nodes of the master list are recycled
* through all the intermediate stages of the sorting process.
*
* @param sc Scanner that points to the input file of radix + items to be sorted
* @return Sorted (in ascending order) circular list of items
* @throws IOException If there is an exception in reading the input file
*/
public Node<String> sort(Scanner sc)
throws IOException {
  // first line is radix
  if (!sc.hasNext()) { // empty file, nothing to sort
   return null;
  }
  
  // read radix from file, and set up buckets for linked lists
  radix = sc.nextInt();
  buckets = (Node<String>[])new Node[radix];
  
  // create master list from input
  createMasterListFromInput(sc);
  
  // find the string with the maximum length
  int maxDigits = getMaxDigits();
  
  for (int i=0; i < maxDigits; i++) {
   scatter(i);
   gather();
  }
  
  return masterListRear;
}

/**
* Reads entries to be sorted from input file and stores them as
* strings in the master CLL (pointed by the instance field masterListRear,
* in the order in which they are read. In other words, the first entry in the linked
* list is the first entry in the input, the second entry in the linked list is the
* second entry in the input, and so on.
*
* @param sc Scanner pointing to the input file
* @throws IOException If there is any error in reading the input
*/
public void createMasterListFromInput(Scanner sc)
throws IOException {
  // WRITE YOUR CODE HERE
}

/**
* Determines the maximum number of digits over all the entries in the master list
*
* @return Maximum number of digits over all the entries
*/
public int getMaxDigits() {
  int maxDigits = masterListRear.data.length();
  Node<String> ptr = masterListRear.next;
  while (ptr != masterListRear) {
   int length = ptr.data.length();
   if (length > maxDigits) {
    maxDigits = length;
   }
   ptr = ptr.next;
  }
  return maxDigits;
}

/**
* Scatters entries of master list (referenced by instance field masterListReat)
* to buckets for a given pass.
*
* Passes are digit by digit, starting with the rightmost digit -
* the rightmost digit is the "0-th", i.e. pass=0 for rightmost digit, pass=1 for
* second to rightmost, and so on.
*
* Each digit is extracted as a character,
* then converted into the appropriate numeric value in the given radix
* using the java.lang.Character.digit(char ch, int radix) method
*
* @param pass Pass is 0 for rightmost digit, 1 for second to rightmost, etc
*/
public void scatter(int pass) {
  // WRITE YOUR CODE HERE
}

/**
* Gathers all the CLLs in all the buckets into the master list, referenced
* by the instance field masterListRear
*
* @param buckets Buckets of CLLs
*/
public void gather() {
  // WRITE YOUR CODE HERE
}

}

------------------------------------------------------------------------------------------------------

package apps;

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

import structures.Node;

public class Sorter {

public static void main(String[] args)
throws IOException {

  Scanner sysin = new Scanner(System.in);
  System.out.print("Enter input file name: ");
  String inFile = sysin.next();
    
  // create new Radixsort object, using default constructor
  Radixsort rs = new Radixsort();
  
  // sort the items in the input file
  Scanner sc = new Scanner(new File(inFile));
  Node<String> output = rs.sort(sc);
  
  // print output
  System.out.println(" Sorted Result:");
  printCLL(output);
  
}

/**
* Prints the items in a CLL
*/
public static<T> void printCLL(Node<T> rear) {
  if (rear == null) {
   return;
  }
  Node<T> ptr = rear;
  do {
   ptr = ptr.next;
   System.out.println(ptr.data);
  } while (ptr != rear);
  System.out.println();
}
}

---------------------------------------------------------------------------------------

package structures;

public class Node<T> {

public T data;

public Node<T> next;

public Node(T data, Node<T> next) {

this.data = data;

this.next = next;

}

public String toString() {

return "" + data;

}

}

-----------------------------------------------

TXT File to scan

16

A523

76

765B

888

923

C269

786

Explanation / Answer

Hi I have included RadixSort for both integer array and LinkedList. Please modify my program for your String.

For Integer Array:

/**
** Java Program to Implement Radix Sort
**/

import java.util.Scanner;

/** Class RadixSort **/
public class RadixSort
{
/** Radix Sort function **/
public static void sort( int[] a)
{
int i, m = a[0], exp = 1, n = a.length;
int[] b = new int[10];
for (i = 1; i < n; i++)
if (a[i] > m)
m = a[i];
while (m / exp > 0)
{
int[] bucket = new int[10];

for (i = 0; i < n; i++)
bucket[(a[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % 10]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= 10;
}
}
/** Main method **/
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Radix Sort Test ");
int n, i;
/** Accept number of elements **/
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/** Create integer array on n elements **/
int arr[] = new int[ n ];
/** Accept elements **/
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/** Call method sort **/
sort(arr);
/** Print sorted Array **/
System.out.println(" Elements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();   
}
}

For LinkedList:

import java.util.LinkedList;
import java.util.Random;

public class RadixSort {

// Define the length of the array.
private static final int LENGTH = 10;

// Define the queues.
private static LinkedList[] q = {
new LinkedList(), // 0
new LinkedList(), // 1
new LinkedList(), // 2
new LinkedList(), // 3
new LinkedList(), // 4
new LinkedList(), // 5
new LinkedList(), // 6
new LinkedList(), // 7
new LinkedList(), // 8
new LinkedList() // 9
};

/**
* Main method.
* @param args
*/
public static void main(String[] args)
{
// Random List.
Object[] list = new Object[LENGTH];

// Generate a random list of numbers.
for(int r=0; r < LENGTH; r++){
list[r] = new Random().nextInt(1000 * 1000);
}

// Sort the list.
Object[] sortedList = sort(list);

// Print the sorted list.
for(int i=0; i < sortedList.length; i++){
System.out.println(sortedList[i]);
}

}

/**
* Sorts an array of objects (integers) using radix sort.
* @param list The unsorted list.
* @return The sorted list.
*/
public static Object[] sort(Object[] list)
{
// Get the maximum number of digits.
int maxDigits = getMaxDigits(list);

// Iterate through the radix depending on max digits.
for(int r=1; r <= maxDigits; r++){

// Iterate through every number.
int radix;
for(int n=0; n < list.length; n++){
// Figure out what queue to put it into.
radix = getDigitAt(Integer.parseInt(list[n].toString()), r);
// Put it into it's queue accordinmaxDigits = getMaxDigits(list);g to the radix.
q[radix].offer(list[n]);
}

// Go through the queues and put the numbers back into the list.
int a=0;
for(int k=0; k < q.length; k++){
// Go through every element in the queue.
while(q[k].peek() != null){
list[a++] = q[k].poll();
}
}

}

// Return the list, it is now sorted.
return list;

}

/**
* Gets the maximum digits of a list of integers.
* @param list
* @return
*/
public static int getMaxDigits(Object list[])
{
// Define the max digits.
int maxDigits = 0;

// Iterate through the list.
int digits;
for(int i=0; i < list.length; i++){

// Cast the number to a string.
digits = getDigits(Integer.parseInt(list[i].toString()));

// Compare the lengths.
if(digits > maxDigits){
maxDigits = digits;
}

}

// Return the max digits.
return maxDigits;
}

/**
* Gets the number of digits the specified number has.
* @param i
* @return
*/
public static int getDigits(int i)
{
if(i < 10){
return 1;
}
return 1 + getDigits(i / 10);
}

/**
* Gets the digit at the specified radix of the specified number.
* @param number
* @param radix
* @return
*/
public static int getDigitAt(int number, int radix)
{
return (int)(number / Math.pow(10,radix-1)) % 10;
}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.