Question

Hey guys so ive been working on these Radix for quite sometime but I keep hitting roadblocks on my todos. Ive implement the first TODO but I cant get the stringRadixSort to work properly as well nor the ChainOfNodes mergeTwoChainsIntoThird() function. Please feel free to rewrite anything you see wrong with it. Ive also provided the Lab Description down below as well for what the output should be and what to do. Thanks again for your guys help! 

1) Implement a radix sort of String objects in a chain of linked nodes, where strings consist only of upper-case characters. This sort will need 27 buckets: 26 for letters A to Z and one bucket for a space.  Each bucket holds a ChainOfNodes object, which will hold appropriate Strings during the sorting. 

2) The ChainOfNodes is a private class inside the SortChain class, its add method adds new elements to the end on the chain.

3) SortChain constructor is already defined and it calls a private method generateList that randomly generates the given number of String objects with number of characters no longer than the given maxStringLength and adds them to the given list. Utilize StringBuffer to build each String.

4) You will create two lists: this.linkedDataOne and this.linkedDataTwo. Each list will be sorted with the stringRadixSort method which you need to implement following the radix sort algorithm.

5) Finally, you will create a third list with mergeTwoChainsIntoThird method. The new list will contain the same data the this.linkedDataOne and this.linkedDataTwo contain. The new list will also be sorted in the ascending order and the original list will remain unchanged. 

See sample runs (with seed 101):
RUN #1
How many nodes in the first chain?
 It should be an integer value greater than or equal to 0.
5
How many characters in the longest string in the first chain?
 It should be an integer value greater than or equal to 1.
6

How many nodes in the second chain?
 It should be an integer value greater than or equal to 0.
7
How many characters in the longest string in the second chain?
 It should be an integer value greater than or equal to 1.
3

The original listOne is: 
CLYUD RWUMOX OVW A CEZ 
The are 5 elements in the list
  The longest string has 6 characters, so the number of needed passes is 6
The original listOne sorted with RadixSort: 
A CEZ CLYUD OVW RWUMOX 
The are 5 elements in the list


The original listTwo is: 
AY NCQ UBT D TF A UAR 
The are 7 elements in the list
  The longest string has 3 characters, so the number of needed passes is 3
The original listTwo sorted with RadixSort: 
A AY D NCQ TF UAR UBT 
The are 7 elements in the list

The mergeChain is:
A A AY CEZ CLYUD D NCQ OVW RWUMOX TF UAR UBT 
The are 12 elements in the list
The listOne sorted should be unchanged: 
A CEZ CLYUD OVW RWUMOX 
The are 5 elements in the list
The listTwo sorted should be unchanged: 
A AY D NCQ TF UAR UBT 
The are 7 elements in the list

Process finished with exit code 0


RUN #2
How many nodes in the first chain?
 It should be an integer value greater than or equal to 0.
0
How many characters in the longest string in the first chain?
 It should be an integer value greater than or equal to 1.
5

How many nodes in the second chain?
 It should be an integer value greater than or equal to 0.
5
How many characters in the longest string in the second chain?
 It should be an integer value greater than or equal to 1.
3

The original listOne is: 
The list is empty
The original listOne sorted with RadixSort: 
The list is empty


The original listTwo is: 
CL UD RWU O S 
The are 5 elements in the list
  The longest string has 3 characters, so the number of needed passes is 3
The original listTwo sorted with RadixSort: 
CL O RWU S UD 
The are 5 elements in the list

The mergeChain is:
CL O RWU S UD 
The are 5 elements in the list
The listOne sorted should be unchanged: 
The list is empty
The listTwo sorted should be unchanged: 
CL O RWU S UD 
The are 5 elements in the list

Process finished with exit code 0

RUN #3
How many nodes in the first chain?
 It should be an integer value greater than or equal to 0.
25
How many characters in the longest string in the first chain?
 It should be an integer value greater than or equal to 1.
4

How many nodes in the second chain?
 It should be an integer value greater than or equal to 0.
4
How many characters in the longest string in the second chain?
 It should be an integer value greater than or equal to 1.
25

The original listOne is: 
CLY D RWU OX OVWM MCE O Y NCQD BTQ WT GA UAR BNOZ KK H U JBAO DF DIN RYBA BMZG GFLU SJX X 
The are 25 elements in the list
  The longest string has 4 characters, so the number of needed passes is 4
The original listOne sorted with RadixSort: 
BMZG BNOZ BTQ CLY D DF DIN GA GFLU H JBAO KK MCE NCQD O OVWM OX RWU RYBA SJX U UAR WT X Y 
The are 25 elements in the list


The original listTwo is: 
OAQTRHPCWYKQJLDVISONZN ORLBRYUSSXFNFQ YSLFLIASALCGMYBNXISCIJQ OPEMSYQVZUMCCVDS 
The are 4 elements in the list
  The longest string has 23 characters, so the number of needed passes is 23
The original listTwo sorted with RadixSort: 
OAQTRHPCWYKQJLDVISONZN OPEMSYQVZUMCCVDS ORLBRYUSSXFNFQ YSLFLIASALCGMYBNXISCIJQ 
The are 4 elements in the list

The mergeChain is:
BMZG BNOZ BTQ CLY D DF DIN GA GFLU H JBAO KK MCE NCQD O OAQTRHPCWYKQJLDVISONZN OPEMSYQVZUMCCVDS ORLBRYUSSXFNFQ OVWM OX RWU RYBA SJX U UAR WT X Y YSLFLIASALCGMYBNXISCIJQ 
The are 29 elements in the list
The listOne sorted should be unchanged: 
BMZG BNOZ BTQ CLY D DF DIN GA GFLU H JBAO KK MCE NCQD O OVWM OX RWU RYBA SJX U UAR WT X Y 
The are 25 elements in the list
The listTwo sorted should be unchanged: 
OAQTRHPCWYKQJLDVISONZN OPEMSYQVZUMCCVDS ORLBRYUSSXFNFQ YSLFLIASALCGMYBNXISCIJQ 
The are 4 elements in the list

Process finished with exit code 0


   

import java.util.InputMismatchException;
import java.util.Random;
import java.util.Scanner;

/**
 * A class Radix Sort tester
 *
 * @author YOUR NAME
 * @version 10/6/2020
 */
public class SortChain>
{
    private ChainOfNodes linkedDataOne;
    private ChainOfNodes linkedDataTwo;
    private Random generator;

    public SortChain(int listSizeOne, int maxStringLengthOne, int listSizeTwo, int maxStringLengthTwo)
    {
        this.generator = new Random(101);
        this.linkedDataOne = generateList(listSizeOne, maxStringLengthOne);
        this.linkedDataTwo = generateList(listSizeTwo, maxStringLengthTwo);
    }

    /**
     * Creates a ChainOfNodes object called list, randomly generates String objects and adds them to the list
     *
     * @param listSize        - number of STring objects to generate
     * @param maxStringLength - the maximum number of characters in the generated String object
     * @return created list
     */
    private ChainOfNodes generateList(int listSize, int maxStringLength)
    {
        final int ASCII_Z = 90;
        final int ASCII_A = 65;
        ChainOfNodes list = new ChainOfNodes<>();
        //TODO Project 4 #1

        for (int i = 0; i < listSize; i++)
        {
            StringBuilder builder = new StringBuilder();
            int length = generator.nextInt (maxStringLength) + 1;

            for (int j = 0; j < length; j++)
            {
                char c = (char) (generator.nextInt ((ASCII_Z - ASCII_A) + 1) + ASCII_A) ;
                builder.append (c);
            }
            String word = builder.toString();
            list.add (word);
        }

        return list;
    }

    public void sortLinkedDataAndDisplayResults()
    {
        System.out.println("\nThe original listOne is: ");
        displayChain(this.linkedDataOne.firstNode);
        stringRadixSort(this.linkedDataOne);
        System.out.println("The original listOne sorted with RadixSort: ");
        displayChain(this.linkedDataOne.firstNode);

        System.out.println("\n\nThe original listTwo is: ");
        displayChain(this.linkedDataTwo.firstNode);
        stringRadixSort(this.linkedDataTwo);
        System.out.println("The original listTwo sorted with RadixSort: ");
        displayChain(this.linkedDataTwo.firstNode);
    }

    /**
     * RADIX SORT
     * sorts String objects in linkedData chain of nodes
     */
    private void stringRadixSort(ChainOfNodes linkedData)
    {
        // TODO Project 4 #2
        Node currentNode = linkedData.firstNode;
        final int NUMBER_OF_UPPER_CASE_LETTERS = 26;

        // do nothing if no more than one node

        // otherwise
        // create buckets

        // traverse the chain to find the longest string

        if (currentNode.next == null)
        {
            return;
        }

        Node[] buckets = new Node[NUMBER_OF_UPPER_CASE_LETTERS];


        String longestString = currentNode.data;
        while (currentNode != null)
        {
            if (currentNode.data.length () > longestString.length ())
            {
                longestString = currentNode.data;
            }
            currentNode = currentNode.next;
        }




        int max = longestString.length (); // THIS IS A STUB
        System.out.println("\u001B[35m\u001B[1m  The longest string has " + max + " characters so the number of needed passes is " + max + "\u001B[0m\n");


        // start soring

        // for each pass:
        // distribute nodes to appropriate buckets
        // clear the original chain and add the nodes back in "buckets" order
        // clear buckets


        for (int i = 0; i < max; i++)
        {

            currentNode = linkedData.firstNode;
            int length = 1;

            while (currentNode.data != null)
            {
                if (currentNode.data.length () > i)
                {
                    int charValue = (int) (currentNode.data.charAt (i)) - 'A';

                }
                currentNode = currentNode.next;
                length++;
            }
            linkedData.clear ();
        }

    }

    public void createSortedChainFromTwoAndDisplayResults()
    {
        ChainOfNodes mergeChain = mergeTwoChainsIntoThird();
        System.out.println("\n\u001B[35m\u001B[1mThe mergeChain is:\u001B[0m");
        displayChain(mergeChain.firstNode);

        System.out.println("The listOne sorted should be unchanged: ");
        displayChain(this.linkedDataOne.firstNode);

        System.out.println("The listTwo sorted should be unchanged: ");
        displayChain(this.linkedDataTwo.firstNode);
    }

    /**
     * Merges two sorted chains: this.linkedDataOne and this.linkedDataTwo into a new one
     * and returns a reference to the new chain.
     * Each chain is in ascending order.
     * The resulting chain should be in ascending order
     * The original chains remain unchanged
     */
    private ChainOfNodes mergeTwoChainsIntoThird()
    {
        ChainOfNodes newChain = new ChainOfNodes<>();
        Node firstCurrent = this.linkedDataOne.firstNode;
        Node secondCurrent = this.linkedDataTwo.firstNode;

        while ((firstCurrent != null) && (secondCurrent != null))
        {
            // TODO Project 4 #3
            // Create new node for merged chain and decide what data belongs in it


        } // end while


        // Exhausted one or both chains; add any remaining data


        return newChain;
    }


    /**
     * Displays all entries in the given chain of nodes.
     */
    private void displayChain(Node currentNode)
    {
        if (currentNode == null)
            System.out.println("The list is empty");
        else
        {
            int count = 0;
            while (currentNode != null)
            {
                System.out.print(currentNode.data + " ");
                count++;
                currentNode = currentNode.next;
            }
            System.out.println("\nThe are " + count + " elements in the list");
        }
    }

    /**
     * Chain of nodes class with add method that adds elements to the end of the list
     */
    private class ChainOfNodes>
    {
        private Node firstNode;       // reference to first node
        private Node tailNode;        // reference to the last node in the chain

        public ChainOfNodes()
        {
            this.firstNode = null;
            this.tailNode = null;
        } // end default constructor

        /**
         * Adds a new entry to the end of the chain.
         *
         * @param newEntry the object to be added as a new entry
         * @return true
         */
        public boolean add(T newEntry) // OutOfMemoryError possible
        {
            // add to the end of the chain:
            Node newNode = new Node<>(newEntry);
            if (this.firstNode == null)
            {
                this.firstNode = newNode;
                this.tailNode = newNode;
            }
            else
            {
                this.tailNode.next = newNode;
                this.tailNode = newNode;
            }
            return true;
        } // end add

        /**
         * Removes all entries from this bag.
         */
        public void clear()
        {
            this.firstNode = null;
            this.tailNode = null;
        } // end clear
    } // end ChainOfNodes

    private class Node
    {
        private S data; // entry in bag
        private Node next; // link to next node

        private Node(S dataPortion)
        {
            this(dataPortion, null);
        } // end constructor

        private Node(S dataPortion, Node nextNode)
        {
            this.data = dataPortion;
            this.next = nextNode;
        }
    } // end Node

    public static void main(String args[])
    {
        int listOneSize = 0;
        int maxStringLengthListOne = 0;
        int listTwoSize = 0;
        int maxStringLengthListTwo = 0;
        boolean invalidInput;

        // get input
        do
        {
            try
            {
                invalidInput = false;
                Scanner keyboard = new Scanner(System.in);
                System.out.println("How many nodes in the first chain?" + "\n It should be an integer value greater than or equal to 0.");
                listOneSize = keyboard.nextInt();

                System.out.println("How many characters in the longest string in the first chain?" + "\n It should be an integer value greater than or equal to 1.");
                maxStringLengthListOne = keyboard.nextInt();

                System.out.println("\nHow many nodes in the second chain?" + "\n It should be an integer value greater than or equal to 0.");
                listTwoSize = keyboard.nextInt();

                System.out.println("How many characters in the longest string in the second chain?" + "\n It should be an integer value greater than or equal to 1.");
                maxStringLengthListTwo = keyboard.nextInt();
            } catch (InputMismatchException ime)
            {
                System.out.println("Could not convert input to an integer");
                invalidInput = true;
            } catch (Exception e)
            {
                System.out.println("There was an error with System.in");
                System.out.println(e.getMessage());
                invalidInput = true;
            }
        } while (invalidInput);

        SortChain tester = new SortChain(listOneSize, maxStringLengthListOne, listTwoSize, maxStringLengthListTwo);
        tester.sortLinkedDataAndDisplayResults();
        tester.createSortedChainFromTwoAndDisplayResults();
    }
} // end RadixSort

Answer 1

SortChain.java

import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.List;

public class SortChain{
   List<String> list;
  
   public SortChain() {
       list=new LinkedList<>();
   }
   public void stringRadixSort() {
       if (list.size() <= 1) {
   return;
   }
       int n=list.size();
   List<String>[] buckets = new List[27];
   for (int i = 0; i < buckets.length; i++) {
   buckets[i] = new LinkedList<>();
   }
   int largestLength = -1;
   int secondLargestLength = 0;
   for (String s : list) {
   int length = s.length();
   if (length >= largestLength) {
   secondLargestLength = largestLength;
   largestLength = length;
   } else if (secondLargestLength < length) {
   secondLargestLength = length;
   }
   }
  
   System.out.println("\nThe longest string has "+largestLength+" characters, so the number of needed passes is "+largestLength);
   for (int i = secondLargestLength == largestLength ? secondLargestLength-1 : secondLargestLength; i >= 0; i--) {
   for (String word : list) {
   int index = (word.length() <= i) ? 0 : word.charAt(i) - ('A' - 1);
   buckets[index].add(word);
   }

   list.clear();

   for (List<String> lst : buckets) {
   if (lst != null) {
   list.addAll(lst);
   lst.clear();
   }
   }
     
  
   }
   System.out.println("The original list sorted with RadixSort:");
   for(String s:list) {
   System.out.print(s+" ");
}
   }
   public static void main(String args[]) {
       SortChain d=new SortChain();
       d.list.add("HI");
       d.list.add("ERFG");
       d.list.add("ASD");
       d.list.add("BVD");
       d.list.add("SDFGNV");
       System.out.println("Original list is:");
       for(int i=0;i<d.list.size();i++) {
           System.out.print(d.list.get(i)+" ");
       }
       d.stringRadixSort();
   }
}

Output: