Forum: Ruby 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.
Patrick G. (Guest)
on 2005-12-13 13:13
(Received via mailing list)
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?

Patrick
Frederick R. (Guest)
on 2005-12-13 13:36
Patrick G. 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
Christer N. (Guest)
on 2005-12-13 14:09
Or using Array instead of Hash:

I don't think sort is stable. You have to specify the sorting criteria,
and sort only once.

require 'test/unit'
class TestSortBy < Test::Unit::TestCase
  def test_all
    a= [["A", 3, 2, 6, 114],
        ["B", 0,-2, 4, 112],
        ["C", 3, 4, 4, 110],
        ["D", 3, 4, 4, 108]]

    assert_equal [["A", 3, 2, 6, 114],
                  ["C", 3, 4, 4, 110],
                  ["D", 3, 4, 4, 108],
                  ["B", 0, -2, 4, 112]],
                  a.sort_by {|name,x,y,z,w| [x, w] }.reverse
  end
end

Christer
Patrick G. (Guest)
on 2005-12-13 14:10
(Received via mailing list)
A follow-up:

> --------------------------------------------------
> 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 },
> }

this seems to be stable:

pp h.sort{ |a,b|
  res = a[1][:a] <=> b[1][:a]
  if res == 0
    res = a[1][:b] <=> b[1][:b]
  end
  if res == 0
    res = a[1][:c] <=> b[1][:c]
  end
  if res == 0
    res = a[1][:d] <=> b[1][:d]
  end
  res
}.reverse

But I still would like to know if sort_by is unstable (or if am I
doing something wrong).

Patrick
Patrick G. (Guest)
on 2005-12-13 15:10
(Received via mailing list)
[...]

> Wouldn't this be simpler ? :
>
>  h.sort_by {|k,v| [v[:a],v[:b],v[:c],v[:d]]}.reverse

Oh, yes, that's so much nicer. Thanks.

Patrick
unknown (Guest)
on 2005-12-13 15:25
(Received via mailing list)
Hi --

On Tue, 13 Dec 2005, Frederick R. wrote:

> Wouldn't this be simpler ? :
>
> h.sort_by {|k,v| [v[:a],v[:b],v[:c],v[:d]]}.reverse

Or:

   h.sort_by {|k,v| v.values_at(:a,:b,:c,:d) }.reverse

(Possibly a little clearer visually.)


David

--
David A. Black
removed_email_address@domain.invalid

"Ruby for Rails", forthcoming from Manning Publications, April 2006!
Frederick R. (Guest)
on 2005-12-13 15:38
unknown wrote:

>> h.sort_by {|k,v| [v[:a],v[:b],v[:c],v[:d]]}.reverse
>
> Or:
>
>    h.sort_by {|k,v| v.values_at(:a,:b,:c,:d) }.reverse
>
> (Possibly a little clearer visually.)


Yeah ! This one rocks !
Patrick G. (Guest)
on 2005-12-13 16:10
(Received via mailing list)
>>    h.sort_by {|k,v| v.values_at(:a,:b,:c,:d) }.reverse
>>
>> (Possibly a little clearer visually.)
>
>
> Yeah ! This one rocks !

Right, and it passes all my unittests :). So beautiful!

Patrick
Kevin O. (Guest)
on 2005-12-13 16:49
Does the principle of 'least surprise' suggest that the default sort_by
algorithm should be modified to be stable?

It seems to me that a 'stable' algorithm is the expected behavior.
Mike F. (Guest)
on 2005-12-13 16:56
Frederick R. wrote:
>  h.sort_by {|k,v| [v[:a],v[:b],v[:c],v[:d]]}.reverse

OK, this or something like it should be in the rdoc for sort_by.  I was
doing something similar and wound up writing a similar sort with
multiple if tests like the OP because I didn't remember that Array
implements a sane <=>.

Also, would there be a similar cool way to do this in one step where you
want a mix of ascending and descending sorts on different parts?  Say I
had a hash (in YAML):

Bobby:
  age: 11
  lastname: Smith
Suzy:
  age: 13
  lastname: Jones
Ted:
  age 12
  lastname: Smith

And I wanted to sort
  - alphabetically by lastname
  - then age oldest to youngest

So in Perl I'd do something like:

my @sorted_keys = sort { $a->{lastname} cmp $b->{lastname}
                                        || $b->{age} <=> $a->{age} }
keys %data;

In this case I could use

sorted_keys = data.sort_by { |k,v| [ v["lastname"], -1*v["age"] ] }

But what if I wanted reverse alphabetically by lastname (Z-A)?  In perl
I'd swap $a and $b in the first comparison, but I can't think of a
spiffy way to do the same using sort_by.
Christian N. (Guest)
on 2005-12-14 19:21
(Received via mailing list)
Patrick G. <removed_email_address@domain.invalid> writes:

>   end
>   res
> }.reverse

Checkout Numeric#nonzero?.
Martin DeMello (Guest)
on 2005-12-14 20:58
(Received via mailing list)
Mike F. <removed_email_address@domain.invalid> wrote:
>
> In this case I could use
>
> sorted_keys = data.sort_by { |k,v| [ v["lastname"], -1*v["age"] ] }
>
> But what if I wanted reverse alphabetically by lastname (Z-A)?  In perl
> I'd swap $a and $b in the first comparison, but I can't think of a
> spiffy way to do the same using sort_by.

class Reverser
  attr_accessor :obj

  def initialize(obj)
    @obj = obj
  end

  def <=>(other)
    other.obj <=> self.obj
  end
end

class Object
  def rev
    Reverser.new(self)
  end
end

require 'yaml'

data = YAML.load %{
 Bobby:
   age: 11
   lastname: Smith
 Suzy:
   age: 13
   lastname: Jones
 Ted:
   age: 12
   lastname: Smith
}

p data

sorted_keys_0 = data.sort_by {|k,v| [v["lastname"].rev, v["age"]]}
sorted_keys_1 = data.sort_by {|k,v| [v["lastname"], v["age"].rev]}

p sorted_keys_0
p sorted_keys_1

martin
Patrick G. (Guest)
on 2005-12-14 21:13
(Received via mailing list)
>>   end
>>   res
>> }.reverse
>
> Checkout Numeric#nonzero?.


.... learning a new thing everyday... thanks.

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