Stable topN?
Peter Alexander via Digitalmars-d
digitalmars-d at puremagic.com
Tue Jun 24 07:33:04 PDT 2014
On Tuesday, 24 June 2014 at 11:50:37 UTC, Xinok wrote:
> On Tuesday, 24 June 2014 at 04:40:48 UTC, Peter Alexander wrote:
>> On Monday, 23 June 2014 at 22:47:20 UTC, Xinok wrote:
>>> What do you all think? Do you agree with my definition of
>>> stable topN? Do you know of a better algorithm/approach for
>>> implementing this function?
>>
>> I agree with your definition, and can't think of a better
>> algorithm, but wouldn't a stable sort have the same effect as
>> your algorithm? Both are O(n lg(n)) time and O(n) space.
>
> A stable sort would lose the original ordering of the elements
> though. Furthermore, the entire point of the topN function is
> to be faster than simply sorting the range.
Yeah ignore me. Just woke up realising I'd made that mistake, but
you've already replied :-)
However, is your version faster? The last stable partition step
is O(n lg n), same as stable sort.
More information about the Digitalmars-d
mailing list