From: Yong Li <gilbertly@...>
Date: 2012-01-20T11:15:03+09:00
Subject: Re: Elegant expression of sorting

On Thu, Jan 19, 2012 at 5:22 PM, Robert Klemme
<shortcutter@googlemail.com> wrote:
> On Thu, Jan 19, 2012 at 10:09 AM, Garthy D
> <garthy_lmkltybr@entropicsoftware.com> wrote:
>> On 19/01/12 16:35, Yong Li wrote:
>>>

>>> 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

>
> This is totally inefficient because it goes through the original data
> set (which might be large) multiple times.  The complexity of #magic
> only adds to this.
>
>> 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. :)
>
> Please don't, there are much better approaches (see botp's for
> example).  Here are more

Wow, big bow to Robert, I really like reading your posts on this
mailing list. They always teach me something.

I came across this 'generic' multi-key sorting algorithm from a
textbook. It looked interesting to me because I was wondering why I
had never seen it in codes. Now, it seems obvious why I had never seen
it - it is inefficient! lucky that I never used this algorithm in real
life. wheww..


> foo.sort! {|a,b|
>  # Ascending, primary.
>  (a.key0 <=> b.key0).nonzer0? ||
>  # Descending, secondary.
>  (b.key1 <=> a.key1).nonzero? ||
>  # A tricky and expensive comparison, tertiary.
>  a.magic(b)
> }
>
> foo.sort_by {|a|
>  [
>  # Ascending, primary.
>  a.key0,
>  # Descending, secondary, only if numeric.
>  -a.key1,
>   # A tricky and expensive comparison, tertiary.
>  a.create_magic_key
>  ]
> }
>
> All these approaches can also be stored in a lambda and used from there
>
> YourClass::SORT_FOO = lambda {|a| [a.key0, -a.key1, a.create_magic_key]}
> YourClass::SORT_BAR = lambda {|a,b| (a.key0 <=> b.key0).nonzero? || ... }
>
> enum.sort_by &YourClass::SORT_FOO
> enum.sort &YourClass::SORT_BAR
>
> Kind regards
>
> robert
>