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.

for (int i = 0; i

{

for (int j = i + 1; j

{

int tmp = 0;

if (dataArray[i] > dataArray[j])

{

tmp = dataArray[i];

dataArray[i] = dataArray[j];

dataArray[j] = tmp;

}

}

}

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 = 0;

int maxNum = array[0];

if (array.length == 0){

max = 0;

}

//TODO4: Implement this method

else{

for(int i =0; i

if (array[i]>maxNum)

maxNum=array[i];

}

while(maxNum!=0){

maxNum/=10;

++max;

}

}

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 = 0;

//TODO3: Implement this method

while(num!=0){

num/=10;

++len;

}

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;

while(--place>0){

num/=10;

}

digit = num % 10;

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

for(int i =0; i

for(int j=0; j

buckets[i][j] = -1;

}

}

}

}

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;

}

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();

}

}

Project Specification: Background. Bucket Sort uses an array of buckets to repeatedly distribute and then collect data until it is sorted. In this project, you will work with integers. In Bucket Sort, one needs to know how many buckets are needed. One bucket is required for each integer. The number of digits, and therefore the number of buckets is 10, the individual digits, (base ten) being: 0,1,2,3,4,5,6,7,8,9. Now that we know the number of buckets we need, let's look at an example of how we can sort some integers. Let's say we have these numbers to sort: 25, 492, 3, 22. We set up ten buckets, one for each digit. We represent the buckets as a two-dimensional array, where the rows are the buckets and the columns are for storing data as in Fig. 1. 0 1 b 2 3 k 4 5 t 6 7 8 9 Fig 1: A bucket array. Pseudocode: Here is the pseudocode for the bucket sort algorithm. Parameters: numBuckets - number of digits (10 in the case of base ten integers). The buckets are the rows of the bucketArray. MAX_DIGIT_LIMIT - maximum number of digits for integers in the data. dataLen - length of the data. dataArray - an array of the data to be sorted. bucketArray = int[numBuckets] [dataLen] //placeNum the integer's value at l's, 10's, 100's, etc. for placeNum = 1 to MAX_DIGIT_LIMIT { // distribution phase for each dataItem in dataArray curBucket = get value of dataItem at current placeNum columIndex = get first available column in curBucket row write data item to bucketArray (curBucket] [columIndex] // collection phase for each row in bucketArray write each dataItem stored in the row to dataArray clear all values from the bucketArray } Code Structure and TODOS. In VSCode when you open the project folder you should see: EXPLORER PROJ3-BUCKET-SORT-STARTER > lib V src vapp BucketSortMain.java IntegerBucket Sorter.java O Sorter.java V test ProjectTests.java 1. Bucket SortMain.java allows you to test your code by choosing different input data. 2. All of the 7 TODOs are found in the IntegerBucket Sorter.java file. Each TODO asks you to implement a method. Explanations of what the methods should do are in the comments for each method. We recommend that you implement the TODOs in order from 1 to 7. 3. The Sorter.java is an interface that IntegerBucket Sorter implements. 4. The JUnit tests are in the ProjectTests.java file. After all the ToDos are completed and you run BucketSortMain.java, the sorted output with the sample input data is: input: 100, 23, 92, 498, 12, 29, 48, 354, 1, 57, 33 output: 1, 12, 23, 29, 33, 48, 57, 92, 100, 354, 498 The next step is to examine the individual numbers in the data starting with the rightmost number. Since we are dealing with base ten numbers, we can say that we will look at each 1's place number first, then the 10's place, then the 100's place, etc. For the example that has 25, 492, 3, 22, the 1's place number in the integer 492 is 2, its 10's place number is 9, and its 100's place number is 4. The Bucket Sort starts by looking at the 1's place numbers in the data and distributing the data into the bucket that corresponds to their 1's place number. The bucket array would look like this after this first round: 0 1 b 2 492 22 u 33 4 k e 5 25 6 t S 7 8 9 Fig 2: Bucket array after 1st round. Note that bucket 2 contains 492 and 22. That's because they both have 2 in their 1's place. Also note that the data is sorted on the 1's place. ROUND TWO The next step in the algorithm is to collect the data starting with bucket 0 and ending with bucket 9. The data is collected in the order it is stored in. For example, you would collect 492 before 22. This is the data after it has been collected from the bucket array: 492, 22, 3, 25. Now we do another round of distribution, but on the 10's place numbers. The bucket array is cleared out first. Fig. 3 shows the array after the second round: 03 1 b 2 22 25 u 3 C k 4 5 6 7 8 9 492 Fig 3: Second round of distribution. Note that for the round with 492, 22, 3, 25, the number 492 is in bucket 9 because its 10's place number is 9. Note also that 3 is in bucket 0- why? Because it has no 10's place number, so we use O instead. After collecting the data from the array, we get: 3, 22, 25, 492. Remember,we have to reset the bucket array to clear it out at the end of each round. The data is now sorted, but we are not done yet! Because at least one of the data has a 100's place number, we need to do another round. In fact, we need to know the maximum number of digits of the integers in the data before the sort can begin. This is because the algorithm needs to process each digit, one at a time. For the data in our example, the maximum number of digits in an integer is 3, because the integer 492 has three digits. ROUND THREE For round 3, for the numbers 3, 22, 25, 492, we would get this distribution in the array, using 0 for all the data without a 100's place number: 03 22 25 1 2 b u 3 C 4 492 5 t 6 S 7 8 9 Fig 4: Third round distribution. After distribution, we collect the data for the last time and the final result is: 3, 22, 25, 492. The maximum number of digits in the data was 3, so we are done and the data is sorted. Implementation note: The data structure pictured above is a two-dimensional array, with the buckets as rows. The number of columns has to be equal to the size of the data, as it could be possible, though extremely unlikely, that all of the data has the same number for a specific place, and the array has to accommodate that possibility. Obviously, the space that this two-dimensional array requires is impractical for a large amount of data. There are other structures that can be used instead, such as linked lists, but for this project you will work with a two-dimensional array of integers. Project Specification: Background. Bucket Sort uses an array of buckets to repeatedly distribute and then collect data until it is sorted. In this project, you will work with integers. In Bucket Sort, one needs to know how many buckets are needed. One bucket is required for each integer. The number of digits, and therefore the number of buckets is 10, the individual digits, (base ten) being: 0,1,2,3,4,5,6,7,8,9. Now that we know the number of buckets we need, let's look at an example of how we can sort some integers. Let's say we have these numbers to sort: 25, 492, 3, 22. We set up ten buckets, one for each digit. We represent the buckets as a two-dimensional array, where the rows are the buckets and the columns are for storing data as in Fig. 1. 0 1 b 2 3 k 4 5 t 6 7 8 9 Fig 1: A bucket array. Pseudocode: Here is the pseudocode for the bucket sort algorithm. Parameters: numBuckets - number of digits (10 in the case of base ten integers). The buckets are the rows of the bucketArray. MAX_DIGIT_LIMIT - maximum number of digits for integers in the data. dataLen - length of the data. dataArray - an array of the data to be sorted. bucketArray = int[numBuckets] [dataLen] //placeNum the integer's value at l's, 10's, 100's, etc. for placeNum = 1 to MAX_DIGIT_LIMIT { // distribution phase for each dataItem in dataArray curBucket = get value of dataItem at current placeNum columIndex = get first available column in curBucket row write data item to bucketArray (curBucket] [columIndex] // collection phase for each row in bucketArray write each dataItem stored in the row to dataArray clear all values from the bucketArray } Code Structure and TODOS. In VSCode when you open the project folder you should see: EXPLORER PROJ3-BUCKET-SORT-STARTER > lib V src vapp BucketSortMain.java IntegerBucket Sorter.java O Sorter.java V test ProjectTests.java 1. Bucket SortMain.java allows you to test your code by choosing different input data. 2. All of the 7 TODOs are found in the IntegerBucket Sorter.java file. Each TODO asks you to implement a method. Explanations of what the methods should do are in the comments for each method. We recommend that you implement the TODOs in order from 1 to 7. 3. The Sorter.java is an interface that IntegerBucket Sorter implements. 4. The JUnit tests are in the ProjectTests.java file. After all the ToDos are completed and you run BucketSortMain.java, the sorted output with the sample input data is: input: 100, 23, 92, 498, 12, 29, 48, 354, 1, 57, 33 output: 1, 12, 23, 29, 33, 48, 57, 92, 100, 354, 498 The next step is to examine the individual numbers in the data starting with the rightmost number. Since we are dealing with base ten numbers, we can say that we will look at each 1's place number first, then the 10's place, then the 100's place, etc. For the example that has 25, 492, 3, 22, the 1's place number in the integer 492 is 2, its 10's place number is 9, and its 100's place number is 4. The Bucket Sort starts by looking at the 1's place numbers in the data and distributing the data into the bucket that corresponds to their 1's place number. The bucket array would look like this after this first round: 0 1 b 2 492 22 u 33 4 k e 5 25 6 t S 7 8 9 Fig 2: Bucket array after 1st round. Note that bucket 2 contains 492 and 22. That's because they both have 2 in their 1's place. Also note that the data is sorted on the 1's place. ROUND TWO The next step in the algorithm is to collect the data starting with bucket 0 and ending with bucket 9. The data is collected in the order it is stored in. For example, you would collect 492 before 22. This is the data after it has been collected from the bucket array: 492, 22, 3, 25. Now we do another round of distribution, but on the 10's place numbers. The bucket array is cleared out first. Fig. 3 shows the array after the second round: 03 1 b 2 22 25 u 3 C k 4 5 6 7 8 9 492 Fig 3: Second round of distribution. Note that for the round with 492, 22, 3, 25, the number 492 is in bucket 9 because its 10's place number is 9. Note also that 3 is in bucket 0- why? Because it has no 10's place number, so we use O instead. After collecting the data from the array, we get: 3, 22, 25, 492. Remember,we have to reset the bucket array to clear it out at the end of each round. The data is now sorted, but we are not done yet! Because at least one of the data has a 100's place number, we need to do another round. In fact, we need to know the maximum number of digits of the integers in the data before the sort can begin. This is because the algorithm needs to process each digit, one at a time. For the data in our example, the maximum number of digits in an integer is 3, because the integer 492 has three digits. ROUND THREE For round 3, for the numbers 3, 22, 25, 492, we would get this distribution in the array, using 0 for all the data without a 100's place number: 03 22 25 1 2 b u 3 C 4 492 5 t 6 S 7 8 9 Fig 4: Third round distribution. After distribution, we collect the data for the last time and the final result is: 3, 22, 25, 492. The maximum number of digits in the data was 3, so we are done and the data is sorted. Implementation note: The data structure pictured above is a two-dimensional array, with the buckets as rows. The number of columns has to be equal to the size of the data, as it could be possible, though extremely unlikely, that all of the data has the same number for a specific place, and the array has to accommodate that possibility. Obviously, the space that this two-dimensional array requires is impractical for a large amount of data. There are other structures that can be used instead, such as linked lists, but for this project you will work with a two-dimensional array of integers