solve the TODO

public class A1 {

// TODO: document this method public static int[] countingSort(int[] a) { //TODO: implement this method

return null; // return an array with sorted values }

// TODO: document this method public static int[] radixSort(int[] a) { // TODO: implement this method return null; // return an array with sorted values }

/******************************************** * * You shouldn't modify anything past here * ********************************************/

public final static int MAX_INPUT = 524287; public final static int MIN_INPUT = 0;

// example sorting algorithm public static int[] insertionSort(int[] a) {

for (int i = 1; i < a.length; i++) { int tmp = a[i]; int j; for (j = i-1; j >= 0 && tmp < a[j]; j--) a[j+1] = a[j]; a[j+1] = tmp; }

return a; }

/* Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, * Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data * sets that cause other quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. */ public static int[] systemSort(int[] a) { Arrays.sort(a); return a; }

// read ints from a Scanner // returns an array of the ints read private static int[] getInts(Scanner s) { ArrayList a = new ArrayList();

while (s.hasNextInt()) { int i = s.nextInt(); if ((i <= MAX_INPUT) && (i >= MIN_INPUT)) a.add(i); }

return toIntArray(a); }

// copies an ArrayList of Integer to an array of int private static int[] toIntArray(ArrayList a) { int[] ret = new int[a.size()]; for(int i = 0; i < ret.length; i++) ret[i] = a.get(i); return ret; }

public static void main(String[] args) { Scanner s = new Scanner(System.in);

System.out.printf("Enter the sorting algorithm to use ([c]ounting, [r]adix, [i]nsertion, or [s]ystem): "); char algo = s.next().charAt(0);

System.out.printf("Enter the integers to sort, followed by a non-integer character: "); int[] unsorted_values = getInts(s); int[] sorted_values = {};

s.close();

switch (algo) { case 'c': sorted_values = countingSort(unsorted_values); break; case 'r': sorted_values = radixSort(unsorted_values); break; case 'i': sorted_values = insertionSort(unsorted_values); break; case 's': sorted_values = systemSort(unsorted_values); break; default: System.out.println("Invalid sorting algorithm"); System.exit(0); break; }

System.out.println(Arrays.toString(sorted_values)); }

} -----------------------------------------------------------------

junit case

public class A1TestCase{

@Rule public Timeout globalTimeout = Timeout.seconds(15);

@SuppressWarnings("serial") private static class ExitException extends SecurityException {}

private static class NoExitSecurityManager extends SecurityManager { @Override public void checkPermission(Permission perm) {}

@Override public void checkPermission(Permission perm, Object context) {}

@Override public void checkExit(int status) { super.checkExit(status); throw new ExitException(); } }

@Before public void setUp() throws Exception { System.setSecurityManager(new NoExitSecurityManager()); }

@After public void tearDown() throws Exception { System.setSecurityManager(null); }

private void _test(int[] values, int[] expected, char algo) {

int[] actual = new int[0];

try { if (algo == 'c') actual = A1.countingSort(values); else actual = A1.radixSort(values); } catch (ExitException e) {} assertNotNull("Null output.", actual); assertEquals("Output has an incorrect number of items.", expected.length, actual.length);

if (actual.length > 20) { for (int i = 0; i < actual.length; i++) assertEquals("Mismatch in position " + i + ".", expected[i], actual[i]); } else { for (int i = 0; i < actual.length; i++) assertEquals("Expected array " + Arrays.toString(expected) + " but got " + Arrays.toString(actual) + ".", expected[i], actual[i]); }

}

private int[] generateRandArray(int size) { int[] ret = new int[size];

Random r = new Random(); for (int i = 0; i < size; i++) { ret[i] = r.nextInt(A1.MAX_INPUT+1); } return ret; }

private void testRand(char c, int size) { int[] randArray = generateRandArray(size); int[] sortedArray = Arrays.copyOf(randArray, size); Arrays.sort(sortedArray);

_test(randArray, sortedArray, c); }

@Test public void testEmptyCounting() { _test(new int[0], new int[0], 'c'); }

@Test public void testSingleCounting() { _test(new int[] {1}, new int[] {1}, 'c'); _test(new int[] {10000}, new int[] {10000}, 'c'); }

@Test public void testSmallCounting() { _test(new int[] {1, 2, 3}, new int[] {1, 2, 3}, 'c'); _test(new int[] {3, 2, 1}, new int[] {1, 2, 3}, 'c'); _test(new int[] {1, 2, 3, 4}, new int[] {1, 2, 3, 4}, 'c'); _test(new int[] {3, 2, 1, 4}, new int[] {1, 2, 3, 4}, 'c'); _test(new int[] {2, 1}, new int[] {1, 2}, 'c'); _test(new int[] {9999, 10000}, new int[] {9999, 10000}, 'c'); _test(new int[] {10000, 9999}, new int[] {9999, 10000}, 'c'); }

@Test public void testRandCounting() { testRand('c', 1000); }

@Test public void testSizesCounting() { _test(new int[] {1, 10, 100, 1000, 10000, 100000}, new int[] {1, 10, 100, 1000, 10000, 100000}, 'c'); _test(new int[] {1, 10, 100, 1000, 10000, 100000}, new int[] {1, 10, 100, 1000, 10000, 100000}, 'c'); _test(new int[] {100000, 10000, 1000, 100, 10, 1}, new int[] {1, 10, 100, 1000, 10000, 100000}, 'c'); _test(new int[] {10000, 10, 1, 1000, 100, 100000}, new int[] {1, 10, 100, 1000, 10000, 100000}, 'c'); }

@Test public void testEmptyRadix() { _test(new int[0], new int[0], 'r'); }

@Test public void testSingleRadix() { _test(new int[] {1}, new int[] {1}, 'r'); _test(new int[] {10000}, new int[] {10000}, 'r'); }

@Test public void testSmallRadix() { _test(new int[] {1, 2, 3}, new int[] {1, 2, 3}, 'r'); _test(new int[] {3, 2, 1}, new int[] {1, 2, 3}, 'r'); _test(new int[] {1, 2, 3, 4}, new int[] {1, 2, 3, 4}, 'r'); _test(new int[] {3, 2, 1, 4}, new int[] {1, 2, 3, 4}, 'r'); _test(new int[] {2, 1}, new int[] {1, 2}, 'r'); _test(new int[] {9999, 10000}, new int[] {9999, 10000}, 'r'); _test(new int[] {10000, 9999}, new int[] {9999, 10000}, 'r'); }

@Test public void testRandRadix() { testRand('r', 1000); }

@Test public void testSizesRadix() { _test(new int[] {1, 10, 100, 1000, 10000, 100000}, new int[] {1, 10, 100, 1000, 10000, 100000}, 'r'); _test(new int[] {1, 10, 100, 1000, 10000, 100000}, new int[] {1, 10, 100, 1000, 10000, 100000}, 'r'); _test(new int[] {100000, 10000, 1000, 100, 10, 1}, new int[] {1, 10, 100, 1000, 10000, 100000}, 'r'); _test(new int[] {10000, 10, 1, 1000, 100, 100000}, new int[] {1, 10, 100, 1000, 10000, 100000}, 'r'); }

}