I need to create a radixsort datastructures but I don\'t know how I have to fill
ID: 3668034 • Letter: I
Question
I need to create a radixsort datastructures but I don't know how I have to fill in the Radixsort.java file where it says //Write your code here Please Help!
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 masterListRear;
/**
* Array of linked lists that holds the digit-wise distribution of the items during
* each pass of the radixsort algorithm.
*/
Node[] 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 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[])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 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;
}
}
Explanation / Answer
// Radix sort Java implementation
import java.io.*;
import java.util.*;
class Radix {
// A utility function to get maximum value in arr[]
static int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
static void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// A utility function to print an array
static void print(int arr[], int n)
{
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
/*Driver function to check for above function*/
public static void main (String[] args)
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = arr.length;
radixsort(arr, n);
print(arr, n);
}
}
// Radix sort Java implementation
import java.io.*;
import java.util.*;
class Radix {
// A utility function to get maximum value in arr[]
static int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
static void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// A utility function to print an array
static void print(int arr[], int n)
{
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
/*Driver function to check for above function*/
public static void main (String[] args)
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = arr.length;
radixsort(arr, n);
print(arr, n);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.