stable sort_by?

[Patrick Gundlach]

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

Wouldn't this be simpler ? :

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

Best Regards,
Fred

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

[Kroeger, Simon (ext)]

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

[Frederick Ros]

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

[Patrick Gundlach]

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

[Christer Nilsson]

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

[Christer Nilsson]

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

[Kroeger, Simon (ext)]

> -----Original Message-----
> From: list-...@example.com
> [mailto:list-...@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.

cheers

Simon

[Jim Weirich]

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.

[Patrick Gundlach]

[...]

> 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

[Robert Klemme]

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

[dbl...@wobblini.net]

Hi --

On Tue, 13 Dec 2005, Frederick Ros 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
dbl...@wobblini.net

"Ruby for Rails", forthcoming from Manning Publications, April 2006!

[Frederick Ros]

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

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

[Mike Fletcher]

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

[Kevin Olbrich]

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.

[Kroeger, Simon (ext)]

I guess you have to use sort instead of sort_by in such a case,
like:

test = [[1, 'b'], [1, 'c'], [1, 'a'], [0, 'a']]

#sort for first item, than for second in reverse order
p test.sort{|a, b|(a[0] <=> b[0]).nonzero? || (b[1] <=> a[1]) }

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

cheers

Simon

> -----Original Message-----
> From: list-...@example.com
> [mailto:list-...@example.com] On Behalf Of Mike Fletcher
> Sent: Tuesday, December 13, 2005 3:57 PM
> To: ruby-talk ML
> Subject: Re: stable sort_by?
>

[Mike Fletcher]

Kroeger, Simon (ext) wrote:
> I guess you have to use sort instead of sort_by in such a case,
> like:
>
> test = [[1, 'b'], [1, 'c'], [1, 'a'], [0, 'a']]
>
> #sort for first item, than for second in reverse order
> p test.sort{|a, b|(a[0] <=> b[0]).nonzero? || (b[1] <=> a[1]) }
>
> =>[[0, "a"], [1, "c"], [1, "b"], [1, "a"]]
>

Aaah, it's chaining with nonzero? (since it'll return the -1 or 1 if
that's the case) that I was missing.

Thanks.

[Ezra Zygmuntowicz]

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
ez...@yakima-herald.com
509-577-7732

[Christian Neukirchen]

Patrick Gundlach <clr10.10....@spamgourmet.com> writes:

> 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

Checkout Numeric#nonzero?.

> Patrick
--
Christian Neukirchen <chneuk...@gmail.com> http://chneukirchen.org

[Martin DeMello]

Mike Fletcher <lemurifi...@gmail.com> 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 Gundlach]

>> 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
>
> Checkout Numeric#nonzero?.

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

Patrick