From: "冷雨" <raincolee@...>
Date: 2010-11-08T03:17:42+09:00
Subject: Re: sort_by is not stable ?

--001485f1db98dac85204947a850a
Content-Type: text/plain; charset=ISO-8859-1

On Sun, Nov 7, 2010 at 8:07 PM, Robert Klemme <shortcutter@googlemail.com>wrote:

> On 07.11.2010 12:39, Ammar Ali wrote:
>
>> On Sun, Nov 7, 2010 at 1:15 PM, Michel Demazure<michel@demazure.com>
>>  wrote:
>>
>>> Ammar Ali wrote in post #959889:
>>>
>>>  If I understood your issue correctly,
>>>>
>>> Yes, it is exactly that. Your example shows it :
>>>
>>> a = [["g", 3], ["c", 3], ["a", 3], ["f", 3], ["e", 2], ["d", 3], ["b",
>>> 1]]
>>> b = a.sort_by{ |letter, number| letter}
>>> # =>  [["a", 3], ["b", 1], ["c", 3], ["d", 3], ["e", 2], ["f", 3], ["g",
>>> 3]]
>>> c = b.sort_by{ |letter, number| number}
>>> # =>  [["b", 1], ["e", 2], ["d", 3], ["c", 3], ["a", 3], ["f", 3], ["g",
>>> 3]]
>>>
>>>  Without code, I have to guess
>>>>
>>> The code for sort_by refers to ruby_qsort
>>>
>>> I think a built-in sort method should be stable (or have a stable
>>> variant).
>>>
>>
>> Thanks for the clarification, now I understand what you mean. Based on
>> the results of your example, it appears that ruby's qsort is naive.
>> AFAIK, the majority of qsort implementations are.
>>
>
> IIRC quicksort is instable by definition.  There may be stable variants
> though.
>
> In this case it's not really needed IMHO.  You can either do
>
> x.sort_by {|let,dig| [dig, let]}
>
> or, if you don't want to create all those temporary arrays
>
> x.sort {|(la,da),(lb,db)| da == db ? la <=> lb : da <=> db}
> x.sort {|(la,da),(lb,db)| c = da <=> db; c == 0 ? la <=> lb : c}
>
> Kind regards
>
>        robert
>
> --
> remember.guy do |as, often| as.you_can - without end
> http://blog.rubybestpractices.com/
>
>
From a practical viewpoint, stable sort should be implemented as stable
sort.
Not a multiple keys sort... or something else.

-- 
Lai, Yu-Hsuan

--001485f1db98dac85204947a850a--