From: Garthy D <garthy_lmkltybr@...>
Date: 2012-01-19T18:09:21+09:00
Subject: Re: Elegant expression of sorting


Hi Yong Li,

On 19/01/12 16:35, Yong Li wrote:
> On Thu, Jan 19, 2012 at 8:58 AM, Garthy D
> <garthy_lmkltybr@entropicsoftware.com>  wrote:
>> Hi all,
>>
>> I've found that for the current project I am working on that I am frequently
>> doing sorts based on multiple keys. The comparisons on each key tend to
>> vary, ie. sometimes I want descending rather than ascending, and other times
>> the comparison itself is complex.
>>
>> I usually do something like this:
>>
>> foo.sort! {|a,b|
>>   # Ascending, primary.
>>   rv = a.key0<=>  b.key0
>>   # Descending, secondary.
>>   rv = b.key1<=>  a.key1 if rv == 0
>>   # A tricky and expensive comparison, tertiary.
>>   rv = a.magic(b) if rv == 0
>>   rv
>> }
>>
>> Does anyone have any suggestions as to a more elegant way to express this?
>> I'm after something that is logically equivalent, but easier to write and
>> clearer to read.
>>
>> Garth
>>
>
> A general way to perform a multi-key sort is:
> # assuming sort() is a stable sort algorithm, e.g. merge sort
>    foo.sort! {|a,b|
>       # starting from the least important key
>       a.magic(b)
>    }
>    foo.sort! {|a,b|
>       # sort again using the second-least important key
>       b.key1<=>  a.key1
>    }
>    # repeat until you are done with the most important key
>
> I guess you can generalize this using an array of Lambdas.
>
> One potential disadvantage of this for your particular case is that,
> a.magic(b) is always performed even if a.key0 != b.key0. As you have
> stated, this is quite expensive, and can make the above general scheme
> much more expensive than your way.
>

Cool- thanks for that. I won't be able to use it directly as the last 
key sort for most of the things I am doing is typically expensive, but 
I'm still quite interested in different possible approaches. Thankyou. :)

Garth