1. A binary radix sort will sort an array a of n integer values based on their binary bits instead of their decimal digits. This sort will need only two buckets. Represent the buckets as a 2 by n array. You should avoid unnecessary work by not copying the contents of the buckets back into the array a at the end of each pass. Instead just add the values from the second bucket to the end of the first bucket. do not copy elements of the buckets at end of each pass, copy elements of bag 1 and bag 0, and swap pointer to make a[ ]. save address to chunk of memory at a [ ] Implement this algorithm:
   • implement the binaryRadixSort method that is already defined in SortArray.java
     • must make use of methods and constants defined in the Integer class like: Integer.SIZE, Integer.numberOfLeadingZeros, Integer.rotateLeft
     • must incorporate the concept of a bitMask : http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html
   • create a test driver class CheckBinaryRadixSort.java to test the method (it should be similar to CheckCountingSort.java): in main method:
     • prompt the user for three inputs: size of the array, number of trials, and the maximum number to be generated
     • generate an Integer array (use Random class to generate random ints between 0 and the maximum value provided by the user to populate the array)
     • print the array content before and after the binaryRadixSort method was called
     • create a copy of the generated array and sort the copy with a sort method from Arrays class
     • compare the original sorted array with the sorted copy of the array, and print the result: passes or fails

See sample run (please note that seed was not used):

What size array should be used?

It should be an integer value greater than or equal to 1.

21

How many arrays should be used (number of trials)?

It should be an integer value greater than or equal to 1.

3

What maximum number should be generated?

It should be an integer value greater than or equal to 1.

99

TRIAL #1

The original array is:

[43, 23, 27, 42, 43, 98, 85, 95, 85, 20, 16, 30, 40, 45, 85, 33, 45, 85, 39, 57, 51]

The original array sorted with binaryRadixSort:

[16, 20, 23, 27, 30, 33, 39, 40, 42, 43, 43, 45, 45, 51, 57, 85, 85, 85, 85, 95, 98]

passes

TRIAL #2

The original array is:

[7, 21, 63, 14, 2, 60, 10, 92, 18, 43, 20, 83, 59, 42, 27, 19, 16, 56, 98, 13, 46]

The original array sorted with binaryRadixSort:

[2, 7, 10, 13, 14, 16, 18, 19, 20, 21, 27, 42, 43, 46, 56, 59, 60, 63, 83, 92, 98]

passes

TRIAL #3

The original array is:

[4, 84, 24, 84, 6, 48, 24, 18, 53, 83, 50, 53, 20, 24, 6, 49, 92, 66, 99, 23, 38]

The original array sorted with binaryRadixSort:

[4, 6, 6, 18, 20, 23, 24, 24, 24, 38, 48, 49, 50, 53, 53, 66, 83, 84, 84, 92, 99]

passes

//-----------------------------------------------------------------------------------------------------------------------------------

 /************************************************************** * * BINARY RADIX SORT * **************************************************************/ /** * Utilizing radix sort algorithm sorts the values based on their internal binary * representation * * @param a array containing integers to be sorted * @param maxNumber the largest possible value if the array */ 

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

 public static void binaryRadixSort(Integer[] a, int maxNumber) { //TODO Project 3 int indexBucket0 = 0; int indexBucket1 = 0; final int NUMBER_OF_BUCKETS = 2; Integer[][] buckets = new Integer[NUMBER_OF_BUCKETS][a.length]; // // need to utilize bit related constants and methods from Integer class // 

 } }// end SortArray

import java.util.Arrays; import java.util.InputMismatchException; import java.util.Random; import java.util.Scanner; /** * A class for testing countingSort method 

 This is what our test drive should be mirrored by public class CheckCountingSort { public static void main(String args[]) { int arraySize = 0; int trials = 0; int maxNumber = 0; boolean invalidInput; // get input do { try { invalidInput = false; Scanner keyboard = new Scanner(System.in); System.out.println("What size array should be used?" + " It should be an integer value greater than or equal to 1."); arraySize = keyboard.nextInt(); System.out.println("How many arrays should be used (number of trials)?" + " It should be an integer value greater than or equal to 1."); trials = keyboard.nextInt(); System.out.println("What maximum number should be generated?" + " It should be an integer value greater than or equal to 1."); maxNumber = keyboard.nextInt(); } catch(InputMismatchException ime) { System.out.println("Could not convert input to an integer"); invalidInput = true; } catch(Exception e) { System.out.println("There was an error with System.in"); System.out.println(e.getMessage()); invalidInput = true; } }while (invalidInput); // start testing int data[]; int forTesting[]; for(int i = 1; i <= trials; i++) { System.out.println(" TRIAL #" + i); Random generator = new Random(); // create an array and fill it with random values between 0 and MAX_RANDOM exclusive data = new int[arraySize]; for(int j = 0; j < arraySize; j++) { data[j] = generator.nextInt(maxNumber + 1); } System.out.println("The original array is: "); System.out.println(Arrays.toString(data)); // make a copy of the original array we will sort it and use it for comparing result forTesting = Arrays.copyOf(data, arraySize); Arrays.sort(forTesting); SortArray.countingSort(data, maxNumber); System.out.println("The original array sorted with countingSort: "); System.out.println(Arrays.toString(data)); System.out.println(Arrays.equals(data, forTesting)?" passes":" fails"); } //end for } }