Java: Radix Sort and Counting Sort failing in JUnit test. Goal: All 10 test case

ID: 3846996 • Letter: J

Question

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.
   * <p> Steps:
   * <ul>
   * <li> Copy the key
   * <li> Copy elements UP until we find where the key goes
   * <li> We put [insert] the key
   * <li> Repeat for j+1
   * </ul>
   * <p>
   * Java, C++ implementation reference:
   * http://www.algolist.net/Algorithms/Sorting/Insertion_sort
   * <p>
   * 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<Integer> a = new ArrayList<Integer>();

       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<Integer> 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');
   }

}

Explanation / Answer

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;

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

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

   @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 testRandRadix() {
       testRand('r', 1000);
   }

}

Navigate

Java: Radix Sort and Counting Sort failing in JUnit test. Goal: All 10 test case

Java: Task #1 – The Counter Class For this lab we are going to enhance the Count

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Java: Radix Sort and Counting Sort failing in JUnit test. Goal: All 10 test case

Question

Explanation / Answer

Related Questions

Navigate