Java: Radix Sort and Counting Sort failing in JUnit test.

Goal: All 10 test cases in JUnit test runs.

Current Status: 3 errors, 7 successes in 10/10 runs.

Error JUnit tests: testEmptyRadix, testEmptyCounting, testRandRadix.

What needs to be fixed: codes under "TODO" and within countingSort and radixSort. Although the codes are running in the console, we have to pass all 10 JUnit tests.

Note: ONLY change codes within the two sorting method, under TODO, and nothing else.

Image Link: http://imgur.com/a/QKMwl

As you can see, 3 errors, all 10 has to pass.

--------------------

The following are codes that I need to edit:

-------------------

package edu.wit.cs.comp3370;

import java.util.Arrays; import java.util.Scanner; import java.util.ArrayList;

/** Sorts integers from command line using various algorithms. * Once you pass the JUnits, run ChartMaker.java to visually compare the performance. * */

/** * * */

public class PA2 {

// TODO: document this method /** * @param a The array unsorted_value from main method is passed to countingSort as array "a". * @return aux Auxillary storage. */ public static int[] countingSort(int[] a) { int max = a[0];

for (int i = 1; i < a.length; i++) if (a[i] > max) max = a[i];

int[] count = new int[max > a.length ? max + 1 : a.length + 1]; int[] sorted = new int[a.length];

for (int element = 0; element < a.length; element++) count[a[element]]++;

for (int i = 0, j = 0; i < count.length; i++) { while (count[i] != 0) { sorted[j] = i; count[i]--; j++;

} }

return sorted; } public static int[] radixSort(int[] a) {

int max = a[0]; int num = 1;

int[] arr2 = new int[10];

for (int i = 1; i < a.length; i++) { if (a[i] > max) { max = a[i]; } } // System.out.println("hello"); // int d = String.valueOf(max).length();

while (max / num > 0) {

int[] arr = new int[10];

for (int i = 0; i < a.length; i++) arr[((a[i] / num) % 10)]++;

for (int i = 1; i < arr.length; i++) arr[i] += arr[i - 1];

for (int i = a.length - 1; i >= 0; i--) arr2[--arr[(a[i] / num) % 10]] = a[i];

for (int i = 0; i < a.length; i++) a[i] = arr2[i];

num *= 10; }

return a; }

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

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

/** * Implementation of insertionSort as given in week 1 lecture. * temp is the key * we step through the array and look for the proper place to insert the key * elements up to the key are assumed to be sorted. *

Steps: *

*
• Copy the key *
• Copy elements UP until we find where the key goes *
• We put [insert] the key *
• Repeat for j+1 *

*

* Java, C++ implementation reference: * http://www.algolist.net/Algorithms/Sorting/Insertion_sort *

* Expected Cost: O(n^2) * * @param a array to be sorted * @return sorted array */ 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 that you would like sorted, 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)); }

}

-------------------

These are the JUnit codes, all 10 tests must pass, currently 3 hasn't pass:

-------------------

package edu.wit.cs.comp3370.tests;

import java.security.Permission; import java.util.Arrays; import java.util.Random;

import org.junit.After; import org.junit.Before; import org.junit.Rule; import org.junit.Test; import org.junit.rules.Timeout;

import static org.junit.Assert.*;

import edu.wit.cs.comp3370.PA2;

public class PA2TestCase{ @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 = PA2.countingSort(values); else actual = PA2.radixSort(values); } catch (ExitException e) {} assertEquals("Output has an incorrect number of items.", expected.length, actual.length); for (int i = 0; i < actual.length; i++) assertEquals("Mismatch in position " + i + ".", 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(PA2.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'); }

}