Stable topN?

[matovitch via Digitalmars-d]

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.

Yes you can't use stable sort. However you can use a priority 
queue, which would made the algorithm worst case O(M log N) in 
time and O(N) in space. (M is the number of elements in the 
original array and N the number of top elements)