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
>>> =A0 foo.sort! {|a,b|
>>> =A0 =A0 =A0# starting from the least important key
>>> =A0 =A0 =A0a.magic(b)
>>> =A0 }
>>> =A0 foo.sort! {|a,b|
>>> =A0 =A0 =A0# sort again using the second-least important key
>>> =A0 =A0 =A0b.key1<=3D> =A0a.key1
>>> =A0 }
>>> =A0 # 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. =A0The complexity of #magic
> only adds to this.
>
>> Cool- thanks for that. I won't be able to use it directly as the last ke=
y
>> sort for most of the things I am doing is typically expensive, but I'm s=
till
>> quite interested in different possible approaches. Thankyou. :)
>
> Please don't, there are much better approaches (see botp's for
> example). =A0Here 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|
> =A0# Ascending, primary.
> =A0(a.key0 <=3D> b.key0).nonzer0? ||
> =A0# Descending, secondary.
> =A0(b.key1 <=3D> a.key1).nonzero? ||
> =A0# A tricky and expensive comparison, tertiary.
> =A0a.magic(b)
> }
>
> foo.sort_by {|a|
> =A0[
> =A0# Ascending, primary.
> =A0a.key0,
> =A0# Descending, secondary, only if numeric.
> =A0-a.key1,
> =A0 # A tricky and expensive comparison, tertiary.
> =A0a.create_magic_key
> =A0]
> }
>
> All these approaches can also be stored in a lambda and used from there
>
> YourClass::SORT_FOO =3D lambda {|a| [a.key0, -a.key1, a.create_magic_key]=
}
> YourClass::SORT_BAR =3D lambda {|a,b| (a.key0 <=3D> b.key0).nonzero? || .=
.. }
>
> enum.sort_by &YourClass::SORT_FOO
> enum.sort &YourClass::SORT_BAR
>
> Kind regards
>
> robert
>