In this challenge, you will create a variant of the bucket sort with the BucketSort class (described below) and a BucketSortTest driver that will call the BucketSort sort method.

This bucket sort begins with a one-dimensional array of positive integers to be sorted. It also uses a twodimensional array of integers with rows indexed from 0 to 9 and columns indexed from 0 to n 1, where n is the number of values to be sorted. The rows represent the buckets; the columns that create the two-dimensional array represent the numbers that will fill any particular bucket.

The digits of each integer, from right to left, will be placed in buckets 0 to 9 based on their value in passes, processing one digit placeholder at a time. After each pass, the values are placed back in the original array by copying the values, in order, from the two-dimensional array back into the original array. After the leftmost digit is processed, the original array will be in order.

Now, write a class named BucketSort containing a method called sort that operates as follows:

a. Place each value of the one-dimensional array into a row of the bucket array, based on the values ones (rightmost) digit. For an example with three starting value (97, 3, 100), 97 is placed in row 7, 3 is placed in row 3 and 100 is placed in row 0. This procedure is called a distribution pass.

b. Loop through the bucket array row by row, and copy the values back to the original array. This procedure is called a gathering pass. The new order of the preceding values in the onedimensional array is 100, 3 and 97.

c. Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.). On the second (tens digit) pass, 100 is placed in row 0, 3 is placed in row 0 (because 3 has not tens digit) and 97 is placed in row 9. After the gathering pass, the order of the values in the onedimensional array is 100, 3 and 97. On the third (hundreds digit) pass, 100 is placed in row 1, 3 is placed in row 0 and 97 is placed in row 0 (after the 3). After this last gathering pass, the original array is in sorted order.

The two-dimensional array of buckets is 10 times the length of the integer array being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memory the bubble sort requires space for only one additional element of data.

This comparison is an example of the space/time tradeoff: The bucket sort uses more memory than the bubble sort, but performs better. This version of the bucket sort requires copying all the data back to the original array on each pass.

Specifications

BucketSort.java The BucketSort class should include these features:

A private int one-dimensional array variable

A private static Random object used to fill the array with random numbers

BucketSort constructor creates an array of size n based on an argument passed to the method and then fills the array with random integers Note: You will be provided with partially completed methods for the following:

sort method a void method with no parameters that performs the bucket sort algorithm on the array

o Store the maximum number of digits (returned from numberOfDigits method) in numbers to sort in a local variable.

o Create a two-dimensional array (the bucket array) with 10 rows with each row the same length as the one-dimensional array.

o Inside a count controlled loop that goes through all digit places, two additional methods are called by sort in carrying out the bucket sort:

? distributeElements which receives the bucket array and the pass number

? collectElements which receives the bucket array

o The last statement of the loop checks to see if the pass is not equal to the maximum number of digits. If this is true, the bucket array is cleared (i.e., all elements are set to zero). (A separate method is called to clear the bucket array.)

numberOfDigits method finds the largest value and then calculates and returns the number of digits in the largest value using the Math.log10 method.

distributeElements method receives the bucket array and the pass number and distributes the elements into buckets based on the specified digit (correlated with the pass)

collectElements method receives the bucket array and returns the elements to the original array.

emptyBucket method receives the bucket array and sets all of its elements to zero.

toString method uses StringBuilder and an enhanced for loop to create a string with the sorted elements displayed with a single space between elements.

BucketSortTest.java

Your test application BucketSortTest should:

o Create a new BucketSort object named sortArray.

o Display the original (unsorted) contents of sortArray

o Call the BucketSort sort method

o Display the sorted contents of sortArray

Sample Output (for correct input)

Before: 99 95 54 81 22 16 98 81 20 58

After: 16 20 22 54 58 81 81 95 98 99