Source:
· Java How
to Program: Deitel and Deitel, Seventh Edition, Chapter 16
Problem#16.7, Page 804: Bucket Sort
A bucket sort begins with a one-dimensional array of positive integers
to be sorted and a two-dimensional array of integers with columns indexed from
0 to 9 and rows indexed from 0 to n – 1, where n is the number of values
to be sorted. Each row of the two-dimensional array is referred to as
a bucket. The bucket sort algorithm operates as follows:
a) Place each value of the one-dimensional array into
a row of the bucket array, based on the value’s “ones” (rightmost)
digit. For example, 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 one-dimensional 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 no tens digit) and 97 is placed in
row 9. After the gathering pass, the order of the values in the one-dimensional
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.
Note that 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 trade-off: 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.
Programming
Details:
a)
Let A be the input integer array and N be the size of A.
b)
Declare a two dimensional array, B such
that, b has N rows and 10 columns. Set all values of B to zero.
c)
Find the maximum value, M in A.
d)
Compute the number of digits (k) that is contained in M.
e)
for (int i = 1; i
<=k; i++) // k passes
{
System.out.println
(“Pass#” + k);
for (int j = 0; j <a.length; j++)
{
int value = (A[j] /((int) Math.pow(10,
i-1))) % 10;
int cell = 0; // row#
if B[cell][value] == 0, assign B[cell][value] = A[j]
else, go down a row until B[cell][value] == 0 and assign B[cell][value]
= A[j]
}
Print all values of B
Go through the values in B column by
column and copy all the non-zero values back to A
Reset all values of B to zero
Print all values of A
}
Example:
Input Array, A: 25
346 12 8 55 355
155
Pass#1:
Values in the Matrix, B :
0 0 12
0 0 25
346 0 8
0
0 0 0
0 0 55
0 0 0
0
0 0 0
0 0 355
0 0 0
0
0 0 0
0 0 155
0 0 0
0
0 0 0
0 0 0
0 0 0
0
0 0 0
0 0 0
0 0 0
0
0 0 0
0 0 0
0 0 0
0
Array, A : 12
25 55 355
155 346 8
Pass#2:
Values in the Matrix, B :
8 12 25
0 346 55
0 0 0
0
0 0
0 0 0
355 0 0
0 0
0 0
0 0 0
155 0 0
0 0
0 0
0 0 0
0 0 0
0 0
0 0
0 0 0
0 0 0
0 0
0 0
0 0 0
0 0 0
0 0
0 0
0 0 0
0 0 0
0 0
Array, A: 8
12 25 346
55 355 155
Pass#3:
Values in the Matrix, B :
8 155 0 346
0 0 0
0 0 0
12 0 0
355 0 0
0 0 0
0
25 0 0
0 0 0
0 0 0
0
55 0 0
0 0 0
0 0 0
0
0 0
0 0 0
0 0 0
0 0
0 0
0 0 0
0 0 0
0 0
0 0
0 0 0
0 0 0
0 0
Array, A: 8
12 25 55
155 346 355