0.3.10.2 Modified Quicksort
It's also possible to efficiently find the nth largest number in a set
using a modified version of the Quicksort. As you recall, the Quicksort
selects a pivot value and proceeds to partition the data set into two
halves: those which are less than or equal to the pivot value and those
which are greater than it. After partitioning a normal Quicksort would
reiterate on both halves. However, if there are less than n items
in the left partition it makes no sense to reiterate on it. The item
we seek must be in the right partition. The coverse is true also; if
there are more than n items in the left partition it makes no sense
to reiterate on the right partition.
|
Search