Forum: Ruby Re: stable sort_by?

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
87e9a89c53ccf984db792113471c2171?d=identicon&s=25 Kroeger, Simon (ext) (Guest)
on 2005-12-13 13:16
(Received via mailing list)
> >
> ... So, in this case [1,"c"] and [1,"b"] are equivalent, and
> their order
> is un-important ...

From http://en.wikipedia.org/wiki/Stable_sort :

Stability: stable sorting algorithms maintain the relative order
of records with equal keys (i.e. values). That is, a sorting algorithm
is stable if whenever there are two records R and S with the same
key and with R appearing before S in the original list, R will appear
before S in the sorted list.

cheers

Simon
5befe95e6648daec3dd5728cd36602d0?d=identicon&s=25 Robert Klemme (Guest)
on 2005-12-13 14:25
(Received via mailing list)
Kroeger, Simon (ext) wrote:
>>>
>> ... So, in this case [1,"c"] and [1,"b"] are equivalent, and
>> their order
>> is un-important ...
>
> From http://en.wikipedia.org/wiki/Stable_sort :
>
> Stability: stable sorting algorithms maintain the relative order
> of records with equal keys (i.e. values). That is, a sorting algorithm
> is stable if whenever there are two records R and S with the same
> key and with R appearing before S in the original list, R will appear
> before S in the sorted list.

It's pretty easy to transform every sorting operation into a stable one:

orig:
enum.sort_by {|x| calculate_key(x)}

stable:
i=0
enum.sort_by {|x| [calculate_key(x), i+=1]}

Kind regards

    robert
This topic is locked and can not be replied to.