Urgent Please

Most sorting algorithms you encounter are designed to be general purpose sorts, where any data type can be sorted as long as a method for comparing them is defined. In Java, this method is called compareTo in the C omparable interface. Any class that implements Comparable can be sorted because they can be compared.

There are other sorting algorithms that do not rely on comparing data directly. These are not general purpose in the sense that they have to be customized for different types of data. In this project you will implement one of these sorting algorithms called Bucket Sort. The version of Bucket Sort will be customized to work with integers, but it could work with any symbolic language.

IntegerBucketSorter.java

package app;

/**

* This class implements the bucket sort algorithm for an array of integers.

* It uses a two dimensional array to carry out the algorithm.

* The maximum integer length, MAX_DIGIT_LIMIT, is 5, so only integers with 5 digits or less

* can be processed. Also at this time, only integers >=0 can be processed.

* The SENTINEL value -1 is used to indicate an empty cell in the buckets array.

*/

public class IntegerBucketSorter implements Sorter {

// 2-D int array- the "buckets".

int[][] buckets;

// indicates an "empty" cell- no data.

private static final int SENTINEL = -1;

// maximum number of digits an integer can have to be processed.

private static final int MAX_DIGIT_LIMIT = 5;

/**

* Use the bucket sort algorithm to return an array of the integers in the

* input array in sorted order. The input array and the returned array may be the same array.

* @param dataArray an array of integers to be sorted.

* @return an array of integers sorted in ascending order.

* @throws an Exception if any integer in the array is > MAX_DIGIT_LIMIT.

*/

public int[] sort(int[] dataArray) throws Exception {

//TODO7: Implement this method.

return dataArray;

}

/**

* Distribution phase:

* Iterate through the input array and distribute the data into the buckets array

* by sorting on the value of each integer at the current place. The integer's value

* at the current place is the index of the row into which it is distributed.

* The next available cell in the row has to be found so data that already exists in that row

* is not overwritten.

* @param dataArray the integers to be sorted.

* @param curPlace the current "place" used to determine the bucket where an integer is written to.

*/

public void distribute(int[] dataArray, int curPlace){

//TODO5: Implement this method.

}

/**

* Collection phase:

* Iterate through the buckets array starting at row 0.

* Collect all integers stored in that row into the data array,

* in the order they appear in that row.

* Do that for each row until done.

* @param dataArray the integers to be sorted.

*/

public void collect(int[] dataArray) {

//TODO6: Implement this method

}

/**

* Finds the integer with the maximum number of digits, or "places"

* in the array. This is used to determine how many iterations of the

* bucket sort algorithm are required.

* Assume the length of the array >=0.

* This method calls findIntLength.

* @param array the input array of integers to be sorted.

* @throws Exception if findIntLength throws an Exception.

* @return the largest number of digits found in the integers in the array, return 0 if array is empty.

*/

public int findMaxIntLength(int[] array) throws Exception{

int max = -1;

//TODO4: Implement this method

return max;

}

/**

* Returns the number of digits or "places" in the argument, num.

* If num was 0, the return would be 1.

* If num was 5, the return would be 1.

* If num was 15, the return would be 2.

* If num was 500, the return would be 3.

* etc. This method should handle an integer with up to MAX_DIGIT_LIMIT places.

* Assume num >=0.

* @param num the integer whose number of digits we want to determine.

* @return the number of digits of num.

* @throws Exception if the number of digits of num is > MAX_DIGIT_LIMIT.

*/

public int findIntLength(int num) throws Exception {

int len = -1;

//TODO3: Implement this method

return len;

}

/**

* Returns the digit at the specific "place" in the argument, num.

* If the argument does not have a digit at the specified place, 0 is returned.

* If place was 1 and num was 5, the return would be 5.

* If place was 2 and num was 5, the return would be 0.

* If place was 1 and num was 39, the return would be 9.

* If place was 2 and num was 167, the return would be 6.

* Assume num >=0.

* @param place the specific digit required.

* @param num the integer we want to extract the digit from.

* @return the digit at the specified place.

*/

public int getPlaceValue(int place, int num){

int digit = -1;

//TODO2: Implement this method

return digit;

}

/**

* This method overwrites all cells in the "buckets" array

* with the SENTINEL value. This resets the array to be ready

* for another round of the bucket sort algorithm. It should

* also be called as soon as the buckets array is created so that

* it is properly initialized.

*/

public void resetBucketValues(){

//TODO1: Implement this method

}

}

BucketSortMain.java

package app;

public class BucketSortMain {

public static void main(String[] args) throws Exception{

Sorter s = new IntegerBucketSorter ();

System.out.println("input:");

int[] testArr = {100, 23, 92, 498, 12, 29, 48, 354, 1, 57, 33};

System.out.println(printArr(testArr));

// correct output: 1, 12, 23, 29, 33, 48, 57, 92, 100, 354, 498

int[] resultArr = s.sort(testArr);

System.out.println("output:");

System.out.println(printArr(resultArr));

}

public static String printArr(int[] arr){

StringBuilder sb = new StringBuilder();

for(int i=0;i

sb.append(arr[i]);

if (i

sb.append(", ");

}

return sb.toString();

}

}

Sorter.java

package app;

/**

* Generic sorting interface. At this time, only arrays of integers is supported.

*/

public interface Sorter {

public int[] sort(int[] unsorted) throws Exception;

}

ProjectTests.java

@Test

public void getPlaceValueTest3() {

int place = 3;

int num = 49;

int correct = 0;

int res = sorter.getPlaceValue(place, num);

assertEquals("Test the getPlaceValue method on place = 3, num = 49.", correct, res);

}

@Test

public void findIntLengthTest1() {

boolean exThrown = false;

int correct = 5;

int res = 0;

try {

res = sorter.findIntLength(10000);

} catch (Exception ex) {

exThrown = true;

}

assertEquals("Test the findIntLength method threw an Exception on valid input.", false, exThrown);

assertEquals("Test the findIntLength method on an int == MAX_DIGIT_LIMIT.", correct, res);

}

@Test

public void findIntLengthTest2() {

boolean exThrown = false;

try {

sorter.findIntLength(100000);

} catch (Exception ex) {

exThrown = true;

}

assertEquals("Test the findIntLength method on an int > MAX_DIGIT_LIMIT.", true, exThrown);

}

@Test

public void findIntLengthTest() throws Exception {

int testNum = 0, corrLen = 0;

boolean correct = true;

for (int i = 0; i < 5; i++) {

testNum = (int) Math.pow(10, i);

corrLen = sorter.findIntLength(testNum);

if (corrLen != i + 1) {

correct = false;

break;

}

}

assertEquals("Test the findIntLength method.", true, correct);

}

@Test

public void findMaxIntLengthTest1() {

int[] testArr = {};

int ans = -1;

try {

ans = sorter.findMaxIntLength(testArr);

} catch (Exception e) {

}

assertEquals("Test the findMaxIntLength method on an empty array.", 0, ans);

}

@Test

public void findMaxIntLengthTest2() {

int[] testArr = { 15, 20, 500, 90, 3, 37000 };

int ans = -1;

try {

ans = sorter.findMaxIntLength(testArr);

} catch (Exception e) {

}

assertEquals("Test the findMaxIntLength method on an array.", 5, ans);

}

@Test

public void findMaxIntLengthTest3() {

int[] testArr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

int ans = -1;

try {

ans = sorter.findMaxIntLength(testArr);

} catch (Exception e) {

}

assertEquals("Test the findMaxIntLength method on an array.", 1, ans);

}

@Test

public void findMaxIntLengthTest4() {

int[] testArr = { 1000000 };

boolean exThrown = false;

try {

sorter.findMaxIntLength(testArr);

} catch (Exception ex) {

exThrown = true;

}

assertEquals("Test the findMaxWordLength method on an int > MAX_DIGIT_LIMIT.", true, exThrown);

}

@Test

public void resetBucketValuesTest1() {

boolean notNeg1 = false;

try {

Field f = sorter.getClass().getDeclaredField("buckets"); // NoSuchFieldException}

f.setAccessible(true);

int[] data = {100, 10, 23};

sorter.sort(data);

sorter.resetBucketValues();

int[][] buckets = (int[][]) f.get(sorter);

for (int i = 0; i < 10; i++) {

for (int j = 0; j < buckets[i].length; j++) {

if (buckets[i][j] != -1) {

notNeg1 = true;

break;

}

}

}

} catch (Exception e) {

assertEquals("No buckets field found in class", true, false);

return;

}

assertEquals("Test the resetBucketValues", notNeg1, false);

}

}