simultaneous multiple key sorting algorithm

[Andrei Alexandrescu]

On 1/28/12 9:10 AM, Manfred Nowak wrote:
> Andrei Alexandrescu wrote:
>
> [ About ranks]
>> Actually they need to be computed.
>
> Then the problem is still too unclear.

It's very simple and clear in formulation actually.

Given a range r of elements, define rank(a, p) as the position that 
object a would have if range r would be sorted by predicate p. So the 
rank is a number between 0 and n-1 (n being the number of elements in 
the range.) For example, if we sort [ 40, 10, 30, 20 ] using "<" as a 
predicate, the rank of 20 is 1. (For simplicity we can consider for now 
that all elements are distinct.)

Now say we have multiple predicates, p1, p2, ..., pk. We want to sort 
elements in increasing order of rank(a, p1) + ... + rank(a, pk).

>> I think it's possible to find cases where
>>     rank(a, k1) + rank(a, k2)<  rank(b, k1) + rank(b, k2)
>> but
>>     alpha * a.k1 + beta * a.k2>  alpha * b.k1 + beta.k2.
>
> Of course. Especially if the a, b, ... are sortable only partielly.
> But if the ranks are known, the problem can be finished with the
> linear median algorithm.
>
>> One potentially confusing issue is that importance applies to
>> rank, not features.
>
> Do you mean that
>    alpha * rank(a, k1) + beta * rank(a, k2)
> has to be extremized for all `a'?

I don't understand this.

> Again: the problem is still unclear.

Hopefully the above has clarified it. Thanks for looking into it!


Andrei