Java Reference
In-Depth Information
When Program P9.4 is run, it produces the following output:
Max stack items: 5
14 17 19 21 22 23 25 26 28 31
32 35 37 38 39 40 42 43 44 46
48 50 51 54 56 58 60 63 65 66
68 69 72 73 75 77 78 79 81 84
85 86 87 88 90 93 96 99
As written, even if a sublist consists of two items only, the method will go through the whole process of calling
partition, checking the lengths of the sublists, and stacking the two sublists. This seems an awful lot of work to sort two
items.
We can make
quicksort
more efficient by using a simple method (insertion sort, say) to sort sublists that are
shorter than some predefined length (8, say). You are urged to write
quicksort
with this change and experiment with
different values of the predefined length.
9.5.3 Finding the
k
th
Smallest Number
Consider the problem of finding the
k
th
smallest number in a list of
n
numbers. One way to do this is to sort the
n
numbers and pick out the
k
th
one. If the numbers are stored in an array
A[1..n]
, we simply retrieve
A[k]
after sorting.
Another, more efficient way is to use the idea of partitioning. We will use that version of
partition
that places
the pivot in its final sorted position. Consider an array
A[1..99]
and suppose a call to
partition
returns a division
point of 40. This means that the pivot has been placed in
A[40]
with smaller numbers to the left and bigger numbers
to the right. In other words, the 40
th
smallest number has been placed in
A[40]
. So, if
k
is 40, we have our answer
immediately.
What if
k
were 59? We know that the 40 smallest numbers occupy A[1..40]. So, the 59
th
must be in A[41..99], and
we can confine our search to this part of the array. In other words, with one call to
partition
, we can eliminate 40
numbers from consideration. The idea is similar to
binary search
.
Suppose the next call to
partition
returns 65. We now know the 65
th
smallest number and the 59
th
will be in
A[41..64]
; we have eliminated
A[66..99]
from consideration. We repeat this process each time, reducing the size of
the part that contains the 59
th
smallest number. Eventually,
partition
will return 59, and we will have our answer.
The following is one way to write
kthSmall
; it uses
partition1
:
public static int kthSmall(int[] A, int k, int lo, int hi) {
//returns the kth smallest from A[lo] to A[hi]
int kShift = lo + k - 1; //shift k to the given portion, A[lo..hi]
if (kShift < lo || kShift > hi) return -9999;
int dp = partition1(A, lo, hi);
while (dp != kShift) {
if (kShift < dp) hi = dp - 1; //kth smallest is in the left part
else lo = dp + 1; //kth smallest is in the right part
dp = partition1(A, lo, hi);
}
return A[dp];
} //end kthSmall
For instance, the call
kthSmall(num, 59, 1, 99)
will return the 59
th
smallest number from
num[1..99]
.
Note, however, that the call
kthSmall(num, 10, 30, 75)
will return the 10
th
smallest number from
num[30..75]
.
As an exercise, write the recursive version of
kthSmall
.
Search WWH ::
Custom Search