Programming Radix Sort You will implement Radix Sort on arrays of base 10 integers between 0 and 2,147,483,647 (Integer.MAX_VALUE). You will implement RadixSort in a new way using an array of Queues to sort the values by digit. Your algorithm must run in at most O(n) time. I have given you a simple implementation of a Queue (Queue.java) that inserts and removes elements in constant time. This is method signature Class to use Programming Radix Sort: package sorting; import java.util.Arrays; public class RadixSorter{ //returns the max value in the array //used to provide the k to counting sort private static int getMax(int[] arr) { int max = Integer.MIN_VALUE; for(int i: arr) { if(i>max) max = i; } return max; } public static void radixSort(int[] arr) { //Get the maximum to know how many digits I have int max = getMax(arr); } } And this is queue Class: package sorting; import java.util.NoSuchElementException; public class Queue { private static class Node { int data; Node next; public Node(int data) { this.data = data; next = null; } } private Node front; private Node back; private int size; public void enqueue(int i) { Node toInsert = new Node(i); if(size==0) { front = toInsert; back = toInsert; size++; } else { back.next = toInsert; back = back.next; size++; } } public int dequeue() { if(size==0) { throw new NoSuchElementException("Queue is Empty"); } int frontData = front.data; if(size==1) { front = null; back = null; } else { front = front.next; } size--; return frontData; } public int peek() { if(size==0) { throw new NoSuchElementException("Queue is Empty"); } return front.data; } public boolean isEmpty() { return size==0; }
Programming Radix Sort
You will implement Radix Sort on arrays of base 10 integers between 0 and 2,147,483,647
(Integer.MAX_VALUE). You will implement RadixSort in a new way using an array of Queues
to sort the values by digit. Your
simple implementation of a Queue (Queue.java) that inserts and removes elements in
constant time.
This is method signature Class to use Programming Radix Sort:
package sorting;
import java.util.Arrays;
public class RadixSorter{
//returns the max value in the array
//used to provide the k to counting sort
private static int getMax(int[] arr) {
int max = Integer.MIN_VALUE;
for(int i: arr) {
if(i>max)
max = i;
}
return max;
}
public static void radixSort(int[] arr) {
//Get the maximum to know how many digits I have
int max = getMax(arr);
}
}
And this is queue Class:
package sorting;
import java.util.NoSuchElementException;
public class Queue {
private static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
next = null;
}
}
private Node front;
private Node back;
private int size;
public void enqueue(int i) {
Node toInsert = new Node(i);
if(size==0) {
front = toInsert;
back = toInsert;
size++;
}
else {
back.next = toInsert;
back = back.next;
size++;
}
}
public int dequeue() {
if(size==0) {
throw new NoSuchElementException("Queue is Empty");
}
int frontData = front.data;
if(size==1) {
front = null;
back = null;
}
else {
front = front.next;
}
size--;
return frontData;
}
public int peek() {
if(size==0) {
throw new NoSuchElementException("Queue is Empty");
}
return front.data;
}
public boolean isEmpty() {
return size==0;
}
}
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 1 images
The updated code doesn't handle the arary with negative numbers. Can you help update the code to handle negative numbers?
by Bartleby Expert
