From: Peter Dimov (pdimov_at_[hidden])
Date: 2007-04-29 14:04:36
Lubomir Bourdev wrote:
> On 4/29/07 12:41 AM, "John Femiani" <JOHN.FEMIANI_at_[hidden]> wrote:
>> Regarding your comment:
>>> I haven't thought much about this, but this is
>>> k-order statistic (in an array of numbers, find
>>> the K-th smallest one). There is an algorithm to do
>>> this in O(N). This would be rather useful, perhaps
>>> someone should put it in Boost?
>> It is part of the stl already: std::nth_element in the <algorithm>
> My understanding is that std::nth_element partially sorts the range,
> suggesting O(NlogN) running time. There are algorithms to return the
> n-th smallest element in an unordered list in O(N).
std::nth_element has (average) linear complexity.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk