Overview For this assignment, you will implement one of the most clever sorting algorithms of all time – Herman Hollerith's Radix Sort. To properly test your program, I'm going to provide some data files. The format of each file will be the same. Also, as not to make this assignment too difficult, all the keys will be base-10 numbers. In other words, you can assume their will be 10 buckets in your sort.Below I have attached the full assignment worksheet, The Linked list and queue code needed along with the Test files
CSC 130 - Fall 2021 - Assignment 2 - Radix Sort California State University, Sacramento College of Engineering and Computer Science Computer Science 130: Data Structures and Algorithm Analysis Assignment #2 – Radix Sort Overview For this assignment, you will implement one of the most clever sorting algorithms of all time – Herman Hollerith's Radix Sort. To properly test your program, I'm going to provide some data files. The format of each file will be the same. Also, as not to make this assignment too difficult, all the keys will be base-10 numbers. In other words, you can assume their will be 10 buckets in your sort. Part 1: Key-Value Class Entry Class To store the values in the array, we need to create a key-value class. In this case, I called it "Entry", but you are welcome any other name that you like. class Entry public String key public String value end class Note, this is far different from the Node class used by the linked list. That class shouldn't be modified. Your Updated Queue Class So, how do you implement the buckets? Well, they are essentially queues. The following is the modified interface for the Queue Class. You will only have to make some minor changes to your Assignment #1 code. Don't have to make any modifications to your Linked List class. public class Queue Item About() Returns text about you – the author of this class. void Enqueue(Entry) Enqueues a string onto the queue. Entry Dequeue() Dequeues (removes) a string from the front of the queue. Entry Peek() Returns the value on the front of the queue. Do not return the linked list node. boolean IsEmpty() Returns true of the stack is empty. 2 Part 2: Input File Format A number of test files will be provided to you for testing your code. The format is designed to be easy to read in multiple programming languages. The first line of the data contains the total digits in the key. You should save this value and use it to control the number of passes the Radix Sort will perform. Naturally, this can also be inferred from the data itself, but its useful to have it explicitly stated. The second line consists of the number of records (i.e., succeeding lines) in the file. You can use this variable to initialize an array. Note: Radix Sort can be performed on a Linked-List, but we didn't cover this in class. Please use whichever approach is easier (arrays are easier to understand). Digits in the key Number of records Key 1, Value 1 Key 2, Value 2 Key 3, Value 3 ... Key n, Value n The following is one of the most basic test files on the CSc 35 Website. It consists of only 13 records. File: years.txt 4 13 2020,Great Toilet Paper Shortage 1839,Sutter's Fort founded 1846,Bear Flag Revolt 1947,Sacramento State founded 1977,Star Wars was born 2017,Star Wars franchise almost destroyed 1964,Buffalo wings invented 1783,United States Constitution enacted 1850,California joins the United States 1848,Gold Rush begins 1776,American Revolution 1980,Pacman was released 1953,Cheese Whiz was invented (Nacho Era began) 13 records 3 Requirements You must use your linked-list and queue (modified) from Assignment #1. Do not use any built-in queue library class, etc… If you do, you will receive a zero. No exceptions. No resubmissions. • This must be completely all your code. If you share your solution with another student or re-use code from another class, you will receive a zero. • You must use your Linked-List from Assignment #1. • Your Queue must use your Linked-List class. • You may use any programming language you are comfortable with. I strongly recommend not using C (C++, Java, C#, Visual Basic are all good choices). Due Date Due October 19, 2021 by 11:59 pm. Given you already have developed excellent programming skills in CSc 20, this shouldn't be a difficult assignment. Do not send it to canvas. E-Mail the following to
[email protected]: • The source code. • The main program that runs the tests. • Output generated by your tests The e-mail server will delete all attachments that have file extensions it deems dangerous. This includes .py, .exe, and many more. So, please send a ZIP File containing all your files. //Dymone Hunt Chambers //Linked List that is O(1) without built in library //HW1 CSC130 public class LinkedList { //Implementation of the linked list node //internal node class and object value for all data types class Node { // Value to be stored in linked list public Object value; //Next node public Node next; //Constructor used to set node value //item for value public Node(Object item) { value = item; next = null; } } // Head and tail of the linked list private Node head = null; private Node tail = null; //Pool node for part 3 private Node pool = null; //LinkedList and pool size defined private int size, poolSize; //set both sizes to zero public LinkedList() { size = 0; poolSize = 0; } //Method Will return something about me public String About() { return "I'm the real life cookie monster"; } // Adds an object to the head of the list O(1) //Object parameter item = Item to be added to head public void AddHead(Object item) { //Creating new node called newNode Node newNode = new Node(item); //code for removepool //check to see if it is null if (pool == null) { //newNode = new Node(); newNode = new Node(item); poolSize = 1; } else{//remove the node and decrease poolside newNode = pool; pool = pool.next; poolSize--; } //if head is empty then link head&tail to the new node newNode //return so not set to null that will cause an error if (head == null) { head = tail = newNode; head = newNode; tail = newNode; return; } //link the new node to the old head //set the head = to the newNode //add size else { newNode.next = head; head = newNode; size++; } } // Add node to tail //item to be added to tail public void AddTail(Object item) { //creating a new node called newNode Node newNode = new Node(item); //code for removepool //check to see if it is null if (pool == null) { newNode = new Node(item); poolSize = 1; } else {//remove the node and decrease poolside newNode = pool; pool = pool.next; poolSize--; } //check if head is null if (head == null) { head = newNode; tail = newNode; return; } //link the old tail to the new node //the new node is the new tail //add to size tail.next = newNode; tail = newNode; size++; } //remove an object from the head of the list public Object RemoveHead() { //save a reference to the old head //save the value to return later //the second item is the new head Node old = head; Object result = old.value; head = head.next; if (head == null) { tail = null; //Personal note: could throw an exception to show what the error is //throw new ArrayIndexOutOfBoundsException("Stack is Empty"); } //add pool code //if pool count is not at the maximum value which is 10 if (poolSize < 10) { //add the old value to the pool and add poolsize old.next = pool; pool = old; poolsize++; //change old to null old.value = null; } size--; return result; } //peek value from head //return value from head node of the list public object peekhead() { if (head == null) return null; return head.value; } //return the size of the link list for is empty public int getsize() { 10)="" {="" add="" the="" old="" value="" to="" the="" pool="" and="" add="" poolsize="" old.next="pool;" pool="old;" poolsize++;="" change="" old="" to="" null="" old.value="null;" }="" size--;="" return="" result;="" }="" peek="" value="" from="" head="" return="" value="" from="" head="" node="" of="" the="" list="" public="" object="" peekhead()="" {="" if="" (head="=" null)="" return="" null;="" return="" head.value;="" }="" return="" the="" size="" of="" the="" link="" list="" for="" is="" empty="" public="" int="" getsize()="">