Java Reference
In-Depth Information
is referred to as a
bucket
. Write a class named
BucketSort
containing a method called
sort
that op-
erates 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 ar-
ray. 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.
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 addi-
tional 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.
Another possibility is to create a second two-dimensional bucket array and repeatedly
swap the data between the two bucket arrays.
19.8
(Recursive Linear Search)
Modify Fig. 19.2 to use recursive method
recursiveLin-
earSearch
to perform a linear search of the array. The method should receive the search key and
starting index as arguments. If the search key is found, return its index in the array; otherwise, return
-1
. Each call to the recursive method should check one index in the array.
19.9
(Recursive Binary Search)
Modify Fig. 19.3 to use recursive method
recursiveBinary-
Search
to perform a binary search of the array. The method should receive the search key, starting
index and ending index as arguments. If the search key is found, return its index in the array. If the
search key is not found, return
-1
.
19.10
(Quicksort)
The recursive sorting technique called quicksort uses the following basic algo-
rithm for a one-dimensional array of values:
a)
Partitioning Step
: Take the first element of the unsorted array and determine its final lo-
cation in the sorted array (i.e., all values to the left of the element in the array are less
than the element, and all values to the right of the element in the array are greater than
the element—we show how to do this below). We now have one element in its proper
location and two unsorted subarrays.
b)
Recursive Step
: Perform
Step 1
on each unsorted subarray. Each time
Step 1
is performed
on a subarray, another element is placed in its final location of the sorted array, and two
unsorted subarrays are created. When a subarray consists of one element, that element
is in its final location (because a one-element array is already sorted).
The basic algorithm seems simple enough, but how do we determine the final posi-
tion of the first element of each subarray? As an example, consider the following set of
values (the element in bold is the partitioning element—it will be placed in its final
location in the sorted array):
37
2 6 4 89 8 10 12 68 45
Starting from the rightmost element of the array, compare each element with
37
until
an element less than
37
is found; then swap
37
and that element. The first element less
than
37
is 12, so
37
and 12 are swapped. The new array is
