Asp Forum
Home
|
Login
|
Register
|
Search
Forums
>
comp.lang.ruby
Re: stable sort_by?
Kroeger, Simon (ext)
12/13/2005 12:15:00 PM
> -----Original Message-----
> From: list-bounce@example.com
> [mailto:list-bounce@example.com] On Behalf Of Frederick Ros
> Sent: Tuesday, December 13, 2005 1:01 PM
> To: ruby-talk ML
> Subject: Re: stable sort_by?
>
> Kroeger, Simon (ext) wrote:
>
> > Full Ack,
> >
> > obviously sort_by isn't stable:
> >
> > test = [[1, 'b'], [1, 'c'], [0, 'a']]
> > p test.sort_by{|t|t[0]}
> >
> > => [[0, "a"], [1, "c"], [1, "b"]]
> > (ruby 1.8.2 (2004-12-25) [i386-mswin32])
>
> Hummm not sure to understand ... You asked for a sort on the
> first item
> ... So, in this case [1,"c"] and [1,"b"] are equivalent, and
> their order
> is un-important ...
From
http://en.wikipedia.org/wiki/S...
:
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
1 Answer
Robert Klemme
12/13/2005 1:20:00 PM
0
Kroeger, Simon (ext) wrote:
>> -----Original Message-----
>> From: list-bounce@example.com
>> [mailto:list-bounce@example.com] On Behalf Of Frederick Ros
>> Sent: Tuesday, December 13, 2005 1:01 PM
>> To: ruby-talk ML
>> Subject: Re: stable sort_by?
>>
>> Kroeger, Simon (ext) wrote:
>>
>>> Full Ack,
>>>
>>> obviously sort_by isn't stable:
>>>
>>> test = [[1, 'b'], [1, 'c'], [0, 'a']]
>>> p test.sort_by{|t|t[0]}
>>>
>>> => [[0, "a"], [1, "c"], [1, "b"]]
>>> (ruby 1.8.2 (2004-12-25) [i386-mswin32])
>>
>> Hummm not sure to understand ... You asked for a sort on the
>> first item
>> ... So, in this case [1,"c"] and [1,"b"] are equivalent, and
>> their order
>> is un-important ...
>
> From
http://en.wikipedia.org/wiki/S...
:
>
> 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
Servizio di avviso nuovi messaggi
Ricevi direttamente nella tua mail i nuovi messaggi per
Re: stable sort_by?
Inserendo la tua e-mail nella casella sotto, riceverai un avviso tramite posta elettronica ogni volta che il motore di ricerca troverà un nuovo messaggio per te
Il servizio è completamente GRATUITO!
x
Login to ForumsZone
Login with Google
Login with E-Mail & Password