Stable topN?

[Xinok via Digitalmars-d]

On Tuesday, 24 June 2014 at 16:03:26 UTC, Andrei Alexandrescu 
wrote:
> On 6/23/14, 3:47 PM, Xinok wrote:
>> I've managed to build a small laundry list the past couple 
>> days, so why
>> not add another item? I've been tasked with implementing a
>> "deterministic topN", but I also noticed that topN is lacking 
>> a stable
>> implementation, so this seemed like an ideal opportunity to 
>> kill two
>> birds with one stone. However, for me, it begged the question:
>>
>> What exactly does stable topN imply?
>>
>> A stable sort only implies that equal elements retain their 
>> original
>> order. However, topN is a partitioning function whose pivot is 
>> unknown
>> beforehand. To me, it would make more sense that not just 
>> equal elements
>> but ALL elements retain their original order in their 
>> respective
>> partitions.
>>
>> However, to accomplish the above, the Nth element would need 
>> to be
>> discovered before any other elements are reordered. This 
>> suggests making
>> a full copy of the range to search for the Nth element. The 
>> unstable
>> topN could be applied to the copy to discover the Nth element, 
>> then the
>> stable partition function could finish the job with the 
>> correct pivot.
>>
>> 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?
>
> There's a notion of "semiStable" in std.algorithm that you may 
> use for further refining topN guarantees.
>
> I'd say use semiStable for stability among the top N items 
> (seeing as those are the most interesting), and stable for 
> stability of all items.
>
>
> Andrei

 From what I know of partitioning algorithms, they're either 
intrinsically stable or intrinsically unstable. Implementing an 
algorithm with the attribute you described would likely come with 
little benefit. I could be wrong, but this is my intuition.