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