How implement a scatter and gather method for Radix Sort? Java package apps; imp
ID: 3668909 • Letter: H
Question
How implement a scatter and gather method for Radix Sort? Java
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 apps;
import java.io.IOException;
import java.util.Collections;
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(0);
//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 {
while(sc.hasNext()){
if(masterListRear == null){
masterListRear = new Node<String>(sc.nextLine(), null);
masterListRear.next = masterListRear;
}
else{
Node<String> newLink = new Node<String>(sc.nextLine(), null);
newLink.next = masterListRear.next;
masterListRear.next = newLink;
masterListRear=newLink;
}
}
}
/**
* 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) {
Node<String> n = masterListRear.next;
do{
if(n.data.length() > pass){
int number = Character.digit(n.data.charAt(n.data.length()-pass-1), radix);
if(buckets[number] == null){
buckets[number] = n;
}
else{
Node<String> first= buckets[number];
first.next=n;
}
}
// else{
// buckets[0] = n;
// }
n = n.next;
}while(n != masterListRear.next);
// System.out.println(buckets[0]);
for(int i = 0 ; i < buckets.length; i++){
System.out.println(buckets[i]);
}
}
/**
* 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() {
for(int i = 0; i < 10; i++){
while(buckets[i] != null){
if(masterListRear == null){
masterListRear = buckets[i];
masterListRear.next = masterListRear;
}
else{
Node<String> newLink = buckets[i];
newLink.next = masterListRear.next;
masterListRear.next = newLink;
masterListRear = newLink;
}
}
buckets[i] = null;
}
}}
Explanation / Answer
Answer:
package apps;
import java.io.IOException;
import java.util.Collections;
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();
System.out.println("da: " + maxDigits);
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
{
String value = "";
Node<String> present = null;
masterListRear = null;
while (sc.hasNext())
{
value = sc.next();
if (masterListRear == null)
{
masterListRear = new Node<String>(value, null);
present = masterListRear;
}
else
{
present.next = new Node<String>(value, null);
present = present.next;
}
}
present.next = masterListRear;
}
/**
*
* 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();
System.out.println("Max: " + maxDigits);
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)
{
Node<String> ptr = masterListRear.next;
Node<String> ptr1 = null;
int length = ptr.data.length();
do
{
ptr1 = ptr;
int at = length - pass - 1;
int d = Character.digit(ptr.data.charAt(at), radix);
if (buckets[d] == null)
{
buckets[d] = new Node<String>(ptr1.data, null);
System.out.println("First node: "+buckets[d].data);
ptr = ptr1.next;
}
else
{
Node<String> indexValue = buckets[d];
while (indexValue.next != null)
{
System.out.println("Inside bucket node: "+indexValue.data);
indexValue = indexValue.next;
}
System.out.println("Outside bucket node: "+indexValue.data);
indexValue = new Node<String>(ptr1.data, null);
ptr = ptr1.next;
buckets[d] = indexValue;
}
} while (ptr1 != masterListRear);
System.out.println(" End of scatter ");
}
/**
* 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()
{
System.out.println("gather begin");
Node<String> currentBucket = buckets[0];
masterListRear = currentBucket;
Node<String> ptr = masterListRear;
while (ptr != null)
{
System.out.println("data: " + ptr.data);
ptr = ptr.next;
}
for (int i = 1; i < buckets.length; i++)
{
ptr = buckets[i];
while (ptr != null)
{
System.out.println("data: " + ptr.data);
ptr = ptr.next;
}
}
masterListRear = ptr;
System.out.println("gather ended");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.