Stable sort_by?

ruby-talk
1

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])

cheers

Simon

···

-----Original Message-----
From: list-bounce@example.com
[mailto:list-bounce@example.com] On Behalf Of Frederick Ros
Sent: Tuesday, December 13, 2005 12:37 PM
To: ruby-talk ML
Subject: Re: stable sort_by?

Patrick Gundlach wrote:
> Hi,
>
> I have to sort a list using a number of criterions (a,b,c,d) where d
> is the least important criterion and a is the most
important one. All
> comparisons should be 'higher number: better position'.
This is what I
> have tried:
>
> --------------------------------------------------
> require 'pp'
>
> h= {"Team A"=>{:a=>3, :b=>2, :c=>6, :d=>114 },
> "Team B"=>{:a=>0, :b=>-2, :c=>4, :d=>112 },
> "Team C"=>{:a=>3, :b=>4, :c=>4, :d=>110 },
> "Team D"=>{:a=>3, :b=>4, :c=>4, :d=>108 },
> }
>
> tmp=h.to_a
>
> [:d,:c,:b,:a].each do |criterion|
> tmp=tmp.sort_by { |a| a[1][criterion] }.reverse
> end
>
> pp tmp
>
> --------------------------------------------------
>
> [["Team D", {:d=>108, :a=>3, :b=>4, :c=>4}],
> ["Team C", {:d=>110, :a=>3, :b=>4, :c=>4}],
> ["Team A", {:d=>114, :a=>3, :b=>2, :c=>6}],
> ["Team B", {:d=>112, :a=>0, :b=>-2, :c=>4}]]
>
>
> but as far as I can see 'Team C' should be better than 'Team D',
> because of criterion d. Is it possible that sort_by is not
stable? Or
> is there something I did wrong?

Wouldn't this be simpler ? :

h.sort_by {|k,v| [v[:a],v[:b],v[:c],v[:d]]}.reverse

Best Regards,
Fred

2

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

If you do value the order of the 2nd item of the array too, you just
have to specify it :

  test = [[1, 'b'], [1, 'c'], [0, 'a']]
  p test.sort_by{|t| t }

  => [[0, "a"], [1, "b"], [1, "c"]]

Best Regards,
Fred

···

--
Posted via http://www.ruby-forum.com/\.

3

From: list-bounce@example.com
[mailto:list-bounce@example.com] On Behalf Of Frederick Ros
Sent: Tuesday, December 13, 2005 12:37 PM
To: ruby-talk ML
Subject: Re: stable sort_by?

Patrick Gundlach wrote:

Hi,

I have to sort a list using a number of criterions (a,b,c,d) where d
is the least important criterion and a is the most

important one. All

comparisons should be 'higher number: better position'.

This is what I

have tried:

--------------------------------------------------
require 'pp'

h= {"Team A"=>{:a=>3, :b=>2, :c=>6, :d=>114 },
    "Team B"=>{:a=>0, :b=>-2, :c=>4, :d=>112 },
    "Team C"=>{:a=>3, :b=>4, :c=>4, :d=>110 },
    "Team D"=>{:a=>3, :b=>4, :c=>4, :d=>108 },
}

tmp=h.to_a

[:d,:c,:b,:a].each do |criterion|
  tmp=tmp.sort_by { |a| a[1][criterion] }.reverse
end

pp tmp

--------------------------------------------------

[["Team D", {:d=>108, :a=>3, :b=>4, :c=>4}],
["Team C", {:d=>110, :a=>3, :b=>4, :c=>4}],
["Team A", {:d=>114, :a=>3, :b=>2, :c=>6}],
["Team B", {:d=>112, :a=>0, :b=>-2, :c=>4}]]

but as far as I can see 'Team C' should be better than 'Team D',
because of criterion d. Is it possible that sort_by is not

stable? Or

is there something I did wrong?

Wouldn't this be simpler ? :

h.sort_by {|k,v| [v[:a],v[:b],v[:c],v[:d]]}.reverse

Best Regards,
Fred

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])

cheers

Simon

  class Array
    def stable_sort
      n = 0
      sort_by {|x| n+= 1; [x, n]}
    end
  end

>> test = [[1, 'b'], [1, 'c'], [0, 'a']]
=> [[1, "b"], [1, "c"], [0, "a"]]
>> p test.stable_sort{|t|t[0]}
[[0, "a"], [1, "b"], [1, "c"]]

-Ezra Zygmuntowicz
WebMaster
Yakima Herald-Republic Newspaper
ezra@yakima-herald.com
509-577-7732

···

On Dec 13, 2005, at 3:54 AM, Kroeger, Simon (ext) wrote:

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

4

Frederick Ros wrote:

  test = [[1, 'b'], [1, 'c'], [0, 'a']]
  p test.sort_by{|t| t }

  => [[0, "a"], [1, "b"], [1, "c"]]

which is the same as
    test.sort

Christer

···

--
Posted via http://www.ruby-forum.com/\.

5

Frederick Ros wrote:

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

A stable sort will leave items in the original order if their keys are
equal. Since sort_by apparently is _not_ a stable sort, the secondary
keys must be included as you suggested.

···

--
Posted via http://www.ruby-forum.com/\.