JAVA
Sortable.java
public interface Sortable{
public int maxNum();
public int posToNum(int pos);
public String digits();
public String paddedDigits();
public void padDigits(int minLength);
}
DynamicArray.java
public class DynamicArray{
private static final int INITCAP = 2; // default initial capacity / minimum capacity
private T[] storage; // underlying array
private int size = 0;
private int capacity = 0;
@SuppressWarnings("unchecked")
public DynamicArray(){
storage = (T[]) new Object[INITCAP];
size = 0;
capacity = INITCAP;
}
@SuppressWarnings("unchecked")
public DynamicArray(int initCapacity){
if(initCapacity
throw new IllegalArgumentException();
storage = (T[]) new Object[initCapacity];
size = 0;
capacity = initCapacity; }
public int size() {
return size; }
public int capacity() {
return capacity; }
public T set(int index, T value){
if (index =capacity)
throw new IllegalArgumentException();
T old = storage[index];
storage[index] = value;
return old; }
public T get(int index){
if (index =capacity)
throw new IllegalArgumentException();
return storage[index]; }
@SuppressWarnings("unchecked")
public boolean add(T value){
if(size==capacity){
T[] temp = (T[]) new Object[2*capacity];
for(int i=0 ;i
temp[i] = storage[i];
storage = temp;
capacity = 2*capacity; }
storage[size] = value;
size++;
return true; }
@SuppressWarnings("unchecked")
public void add(int index, T value){
if (index
throw new IllegalArgumentException();
if(index==capacity || size == capacity){
T[] temp = (T[]) new Object[2*capacity];
for(int i=0 ;i
temp[i] = storage[i];
storage = temp;
capacity = 2*capacity; }
for(int k = size-1; k>=index; k--)
storage[k+1] = storage[k];
storage[index] = value;
size++; }
@SuppressWarnings("unchecked")
public T remove(int index){
if (index =capacity)
throw new IllegalArgumentException();
T val = storage[index];
for(int k = index; k
storage[k] = storage[k+1];
size--;
if(size
T[] temp = (T[]) new Object[capacity/2];
for(int i=0 ;i
temp[i] = storage[i];
storage = temp;
capacity = capacity/2; }
return val;}
I need help on RadixSort
// TO D0: add your imp Lementation and JavaDoc //These are all the imports you are allowed, don't add any more import java.util.Scanner; import java.io.I0Exception; public class RadixSortt DO NOT MODIFY INSTANCE VARIABLES PROVIDED BELOW // EXCEPT TO ADD JAVADOCS //an array of buckets to be used in each round private SmartArray
> buckets; //A SmartArray to store values to be sorted. //It is also used to store intermediate results after /each round and the TinaL group of sorted va Lues //The values should always be sorted in ascending order. private SmartArray values; //ADD MORE PRIVATE MEMBERS HERE IF NEEDED // constructor public RadixSort() // return true if the numbers are guaranteed to be sorted, // .. digit locations have been inspected // return false otherwise public boolean isSorted) f return false; // return which round is about to be performed // round number starts with 0 after a new group of value I gets initialized public int getRound () return -1; // return the number of buckets to be used in each round public int getNumBuckets) return -1; // return the group of values to be sorted public SmartArray getValues) [ return null; // return the array of values corresponding to bucketNum /I return null for invalid bucketNum public SmartArray getBucket(int bucketNum) return null; // return the max number of digits of the values public int getMaxLength) return-1; // read values from the provided scanner // get ready to sort the new group of values // first specify the base: // "a"-alphabetic string with CAPITAL LETTERS onLy //otherwise it would be an integer base in [2,16] // (10 for decimal, 2 for binary, 16 for hexdecimal, etc. // Note: you can assume the type input is always valid public void initValuesFromScanner(Scanner s) throws I0Exception // The following lines are provided to you as a starting point. // Use it as is or make changes as you want String types.next); int base; if (!type.equals("a")) base Integer.parseInt (type) else base SortableString. BASE; /end of provided code /your code can start from here to finish // reading from the scanner and initialization of values // check the list of values and remove the ones with invalid digits // return the number of invalid values removed public int sanitizeValues) return -1; /make sure all values are of the same length // use padding if needed // return the number of values padded public int setSameLength) return -1; //perform one round of radix sort - round number should be incremented by 1 instance variables buckets and values should be updated based on LSD radix sort algorithm public void oneRound(ot // example testing code... edit this as much as you want! public static void main(String[] args) /I create a RadixSort object and read in from a String RadixSort rs - new RadixSort); tryt Scanner s = new Scanner("a BOB TOM AMY TIM"); rs.initValuesFromScanner(s); catch (I0Exception e) e.printStackTrace) System.exit(0); //check features after initialization SmartArray vs -rs.getValues (); if (vs. size()-4 && vs.get ( 0 ) . digits() . equals("BOB") && vs.get (2).digits().equals("AMY")) System.out.println("Yay 1"); // get ready to sort if (rs. sanitizeValues() = 0 && rs.setSameLength()-0 && rs . getMaxLength() = 3 && rs.getRound ( )=0)( System.out.println("Yay 2"); //one round of radix sort rs.oneRound) vs - rs.getValues) //should be "BOB","TOM", "TIM", "AMY" if (!rs.issorted ( ) && rs.getRound ()==1 && vs.get(0).digits().equals("BOB") && vs.get (2).digits().equals("TIM")) System.out.println("Yay 3"); // bucket for "M": should contains "TOM" and "TIM" SmartArray bucket - rs.getBucket (13) if (bucket . size() = 2 && bucket.get(0).digits().equals ("TOM") && bucket.get(1).digits().equals ("TIM"))- System.out.println("Yay 4"); /Note: use provided RadixSortASCII class for debug printing can be helpful // TO D0: add your imp Lementation and JavaDoc //These are all the imports you are allowed, don't add any more import java.util.Scanner; import java.io.I0Exception; public class RadixSortt DO NOT MODIFY INSTANCE VARIABLES PROVIDED BELOW // EXCEPT TO ADD JAVADOCS //an array of buckets to be used in each round private SmartArray> buckets; //A SmartArray to store values to be sorted. //It is also used to store intermediate results after /each round and the TinaL group of sorted va Lues //The values should always be sorted in ascending order. private SmartArray values; //ADD MORE PRIVATE MEMBERS HERE IF NEEDED // constructor public RadixSort() // return true if the numbers are guaranteed to be sorted, // .. digit locations have been inspected // return false otherwise public boolean isSorted) f return false; // return which round is about to be performed // round number starts with 0 after a new group of value I gets initialized public int getRound () return -1; // return the number of buckets to be used in each round public int getNumBuckets) return -1; // return the group of values to be sorted public SmartArray getValues) [ return null; // return the array of values corresponding to bucketNum /I return null for invalid bucketNum public SmartArray getBucket(int bucketNum) return null; // return the max number of digits of the values public int getMaxLength) return-1; // read values from the provided scanner // get ready to sort the new group of values // first specify the base: // "a"-alphabetic string with CAPITAL LETTERS onLy //otherwise it would be an integer base in [2,16] // (10 for decimal, 2 for binary, 16 for hexdecimal, etc. // Note: you can assume the type input is always valid public void initValuesFromScanner(Scanner s) throws I0Exception // The following lines are provided to you as a starting point. // Use it as is or make changes as you want String types.next); int base; if (!type.equals("a")) base Integer.parseInt (type) else base SortableString. BASE; /end of provided code /your code can start from here to finish // reading from the scanner and initialization of values // check the list of values and remove the ones with invalid digits // return the number of invalid values removed public int sanitizeValues) return -1; /make sure all values are of the same length // use padding if needed // return the number of values padded public int setSameLength) return -1; //perform one round of radix sort - round number should be incremented by 1 instance variables buckets and values should be updated based on LSD radix sort algorithm public void oneRound(ot // example testing code... edit this as much as you want! public static void main(String[] args) /I create a RadixSort object and read in from a String RadixSort rs - new RadixSort); tryt Scanner s = new Scanner("a BOB TOM AMY TIM"); rs.initValuesFromScanner(s); catch (I0Exception e) e.printStackTrace) System.exit(0); //check features after initialization SmartArray vs -rs.getValues (); if (vs. size()-4 && vs.get ( 0 ) . digits() . equals("BOB") && vs.get (2).digits().equals("AMY")) System.out.println("Yay 1"); // get ready to sort if (rs. sanitizeValues() = 0 && rs.setSameLength()-0 && rs . getMaxLength() = 3 && rs.getRound ( )=0)( System.out.println("Yay 2"); //one round of radix sort rs.oneRound) vs - rs.getValues) //should be "BOB","TOM", "TIM", "AMY" if (!rs.issorted ( ) && rs.getRound ()==1 && vs.get(0).digits().equals("BOB") && vs.get (2).digits().equals("TIM")) System.out.println("Yay 3"); // bucket for "M": should contains "TOM" and "TIM" SmartArray bucket - rs.getBucket (13) if (bucket . size() = 2 && bucket.get(0).digits().equals ("TOM") && bucket.get(1).digits().equals ("TIM"))- System.out.println("Yay 4"); /Note: use provided RadixSortASCII class for debug printing can be helpful
