0.3.10.1 Modified Radix Sort
One way to tackle this problem is with a modified radix sort. To find
the nth largest number in a set, classify the set into b buckets by
considering the most significant piece of each item's key value. More
than one item will be in each bucket, usually. Maintain a count of
how many items are placed in each bucket.
Now, since we are only interested in the nth item, consider the first
bucket. If there are less than n items in this bucket, ignore its
contents and continue to the second bucket. Continue to consider and
ignore buckets until reaching the one which must house the nth largest
data item. At this point either explicitly sort this bucket and count
off items or, more likely, continue the radix sort procedure.
|
Search