next up previous contents index Search
Next: Modified Quicksort Up: 0.3.10 The nth Largest Previous: 0.3.10 The nth Largest 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.

Scott Gasch