Stable sort_by?

ruby-talk
1

From Sorting algorithm - Wikipedia :

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

···

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

2

Kroeger, Simon (ext) wrote:

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

···

-----Original Message-----