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. 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

import java.util.ArrayList; public class SortArray { /**************************************************************  * ITERATIVE SELECTION SORT  **************************************************************/   /**  * Task: Sorts the first n objects in an array into ascending order.  *  * @param a an array of Comparable objects  * @param n an integer > 0  */  public static mergeSort(a, tempArray, first, last); } // end mergeSort /**  * Task: recursively merge sort a portion of an array.  *  * @param a an array of Comparable objects  * @param tempArray an array used by the merge step  * @param first an integer >= 0 that is the index of the first  * array element to consider  * @param last an integer >= 0 that is the index of the last  * array element to consider  */  private static > void mergeSort(T[] a, T[] tempArray, int first, int last) { if (last > first) // we have some work to do { int mid = (last + first) / 2; mergeSort(a, tempArray, first, mid); mergeSort(a, tempArray, mid + 1, last); merge(a, tempArray, first, mid + 1, last); } } // end mergeSort /**  * Task: Merge the elements in two contiguous sorted sublists  *  * @param a an array of Comparable objects  * @param tempArray a temporay array used in the merge  * @param first an integer >= 0 and < mid  * @param mid an integer <= last  * @param last an integer < a.length  */  private static > void merge(T[] a, T[] tempArray, int first, int mid, int last) { int beginHalf1 = first; int endHalf1 = mid - 1; int beginHalf2 = mid; int endHalf2 = last; // While both subarrays are not empty, compare an element in one subarray with //an element in the other; then copy the smaller item into the temporary array int index = first; //next available location in tempArray while ((beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2)) { if (a[beginHalf1].compareTo(a[beginHalf2]) < 0) { tempArray[index] = a[beginHalf1]; beginHalf1++; } else { tempArray[index] = a[beginHalf2]; beginHalf2++; } index++; } //Assertion: One subarray has been completely copied to tempArray. // copy any remaining values from the first subarray over to temp while (beginHalf1 <= endHalf1) tempArray[index++] = a[beginHalf1++]; // copy any remaining values from the second subarray over to temp while (beginHalf2 <= endHalf2) tempArray[index++] = a[beginHalf2++]; // copy values back for (int i = first; i <= last; i++) { a[i] = tempArray[i]; } } // end merge /**  * ***********************************************************  * QUICK SORT -  * RECURSIVE  * MEDIAN OF THREE  * DOES INSERTION SORT ON SMALL ARRAYS  * ************************************************************  */   private static int MIN_SIZE = 7; /**  * Task: Sorts the first n objects in an array into ascending order.  *  * @param a an array of Comparable objects  * @param n an integer > 0  */  public static > void quickSort(T[] a, int n) { quickSort(a, 0, n - 1); } /**  * Task: Recursively sorts an array into ascending order. Uses quick sort with  * median-of-three pivot selection for arrays of at least  * MIN_SIZE elements, and uses insertion sort for other arrays.  *  * @param a an array of Comparable objects  * @param first an integer >= 0 that is the index of the first  * array element to consider  * @param last an integer >= 0 that is the index of the last  * array element to consider  */  private static > void quickSort(T[] a, int first, int last) { if (last - first + 1 < MIN_SIZE) { insertionSort(a, first, last); } else { // Create the partition: Smaller | Pivot | Larger int pivotIndex = partition(a, first, last); // Sort subarrays Smaller and Larger quickSort(a, first, pivotIndex - 1); quickSort(a, pivotIndex + 1, last); } } /**  * Task: Sorts the first, middle, and last elements of an  * array into ascending order.  *  * @param a an array of Comparable objects  * @param first the integer index of the first array element; first >= 0  * @param mid the integer index of the middle array element  * @param last the integer index of the last array element;  * last - first >= 2, last < a.length  */  private static > void sortFirstMiddleLast(T[] a, int first, int mid, int last) { orderTwoItems(a, first, mid); // make a[first] <= a[mid] orderTwoItems(a, mid, last); // make a[mid] <= a[last] orderTwoItems(a, first, mid); // make a[first] <= a[mid] } // end sortFirstMiddleLast /**  * Task: Orders two given array elements into ascending order  * so that a[i] <= a[j].  *  * @param a an array of Comparable objects  * @param i an integer >= 0 and < array.length  * @param j an integer >= 0 and < array.length  */  private static > void orderTwoItems(T[] a, int i, int j) { if (a[i].compareTo(a[j]) > 0) swap(a, i, j); } // end orderTwoItems /**  * Finds recursively indexes of nine pivot candidates  *  * @param indexes indexes of pivot candidates  * @param a an array of Comparable objects  * @param first the integer index of the first sub-array element  * @param mid the integer index of the middle sub-array element  * @param last the integer index of the last sub-array element  * @param size number of elements in the sub-array  */  private static > void findNineCandidatePivotIndexes(ArrayList indexes, T[] a, int first, int mid, int last, int size) { //TODO Project 4  final int NUMBER_OF_SUB_ARRAYS = 8; // IMPLEMENT this method recursively } /**  * Performs insertion sort on nine pivot candidates  * @param indexes indexes of pivot candidates  * @param a an array of Comparable objects  */  private static > void insertionSortNinePivotCandidates(ArrayList indexes, T[] a) { //TODO Project 4  // follow insertion sort algorithm } /**  * Task: Partitions an array as part of quick sort into two subarrays  * called Smaller and Larger that are separated by a single  * element called the pivot.  * Elements in Smaller are left of the pivot and <= pivot.  * Elements in Larger are right of the pivot and >= pivot.  *  * @param a an array of Comparable objects  * @param first the integer index of the first array element;  * first >= 0  * @param last the integer index of the last array element;  * last >= first; last < a.length  * @return the index of the pivot  */  private static > int partition(T[] a, int first, int last) { //TODO Project 4  // modify this code per lab description int mid = first + (last - first) / 2; sortFirstMiddleLast(a, first, mid, last); int pivotIndex = mid; if (last - first + 1 > 3) { // Move pivot to next-to-last position in array swap(a, mid, last - 1); pivotIndex = last - 1; } // done choosing pivot // at this point pivot is moved to the appropriate spot in the array if (last - first + 1 > 3) { T pivotValue = a[pivotIndex]; // Determine subarrays Smaller = a[first..endSmaller] // and Larger = a[endSmaller+1..last-1] // such that entries in Smaller are <= pivotValue and // entries in Larger are >= pivotValue; initially, these subarrays are empty int indexFromLeft = first + 1; int indexFromRight = last - 2; boolean done = false; while (!done) { // Starting at beginning of array, leave entries that are < pivotValue; // locate first entry that is >= pivotValue; you will find one, // since last entry is >= pivot while (a[indexFromLeft].compareTo(pivotValue) < 0) indexFromLeft++; // Starting at end of array, leave entries that are > pivot; // locate first entry that is <= pivot; you will find one, // since first entry is <= pivot while (a[indexFromRight].compareTo(pivotValue) > 0) indexFromRight--; assert a[indexFromLeft].compareTo(pivotValue) >= 0 && a[indexFromRight].compareTo(pivotValue) <= 0; if (indexFromLeft < indexFromRight) { swap(a, indexFromLeft, indexFromRight); indexFromLeft++; indexFromRight--; } else done = true; } // Place pivotValue between the subarrays Smaller and Larger swap(a, pivotIndex, indexFromLeft); pivotIndex = indexFromLeft; // Assertion: // Smaller = a[first..pivotIndex-1] // Pivot = a[pivotIndex] // Larger = a[pivotIndex+1..last] } return pivotIndex; } // end partition /**************************************************************  *  * COUNTING SORT  *  **************************************************************/  /**  * Making only one pass through the array, counts the number of times  * each integer occurs in the array. These counts are then used  * to sort the array  *  * @param a array to be sorted  * @param maxValue the maximum possible value in the array  */  public static void countingSort(int[] a, int maxValue) { //TODO Project 2   } // end countingSort /**************************************************************  *  * 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  */  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; 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 } } 

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