Newbie question about nested sort


#1

what am I doing wrong? I wanted to sort primarily on count (second
position in array), then sub-sort alphabetically (first position in
array)

char_freq = [[“c”, 2],[“b”, 5],[“a”, 2]]
sorted_freq = char_freq.sort {|a, b| b[1]<=>a[1] || a[0]<=>b[0] }
sorted_freq.each do |d|
print d[0]*d[1]
end

produces >> bbbbbccaa

when I was rather hoping for >> bbbbbaacc

I tried using brackets and using ‘or’ instead of ‘||’ even tried the
sort_by method, any help much appreciated I know this works in perl
(add 13 dollar signs, etc and shake well!):

use strict;
use warnings;
my @char_freq = ([“c”, 2], [“b”, 5], [“a”, 2]);
foreach my $d (sort {$$b[1] <=> $$a[1] || $$a[0] cmp $$b[0] }
@char_freq) {
print $$d[0] x $$d[1]
}

produces >> bbbbbaacc


#2

Grehom wrote:

produces >> bbbbbccaa
foreach my $d (sort {$$b[1] <=> $$a[1] || $$a[0] cmp $$b[0] }
@char_freq) {
print $$d[0] x $$d[1]
}

produces >> bbbbbaacc

Generally you need to do conditional evaluation based on higher prio
results. Using “||” or “or” won’t help here (dunno what Perl does
here).

You want something like

char_freq = [[“c”, 2],[“b”, 5],[“a”, 2]]
sorted_freq = char_freq.sort do |a, b|
c = b[1]<=>a[1]
c == 0 ? a[0]<=>b[0] : c
end
sorted_freq.each do |d|
print d[0]*d[1]
end

You can make your life easier (though less efficient) with a helper:

def multi_compare(*results)
results.each {|c| return c if c != 0}
0
end

char_freq = [[“c”, 2],[“b”, 5],[“a”, 2]]
sorted_freq = char_freq.sort {|a,b| multi_compare(b[1]<=>a[1],
a[0]<=>b[0])}
sorted_freq.map {|a,b| a*b}.join

char_freq = [[“c”, 2],[“b”, 5],[“a”, 2]]
=> [[“c”, 2], [“b”, 5], [“a”, 2]]

sorted_freq = char_freq.sort {|a,b| multi_compare(b[1]<=>a[1],
a[0]<=>b[0])}
=> [[“b”, 5], [“a”, 2], [“c”, 2]]

sorted_freq.map {|a,b| a*b}.join
=> “bbbbbaacc”

You can also do something like this which avoids evaluation of all
conditions:

class Integer

condition chain

def cc()
self == 0 ? yield : self
end
end

char_freq = [[“c”, 2],[“b”, 5],[“a”, 2]]
sorted_freq = char_freq.sort {|a,b| (b[1]<=>a[1]).cc { a[0]<=>b[0] }}
sorted_freq.map {|a,b| a*b}.join

char_freq.sort {|a,b| (b[1]<=>a[1]).cc { a[0]<=>b[0] }}.map {|a,b|
a*b}.join
=> “bbbbbaacc”

HTH

Kind regards

robert

#3

Grehom wrote:

produces >> bbbbbccaa

when I was rather hoping for >> bbbbbaacc

Is this what you want?

char_freq = [[“c”, 2],[“b”, 5],[“a”, 2]]
sorted_freq = char_freq.sort_by {|a| [-a[1], a[0]] }
sorted_freq.each do |d|
print d[0]*d[1]
end


#4

Wow! thanks that’s neat, I need to go back to my pickaxe book and study
the differences between sort and sort_by they are more subtle than I
noticed.


#5

Hi –

On Wed, 4 Jan 2006, Grehom wrote:

produces >> bbbbbccaa

when I was rather hoping for >> bbbbbaacc

Since 0 is true in Ruby (unlike Perl, where it’s false), the || test
will never be performed, because b[1] <=> a[1] is always true.

You can use sort_by, though:

sorted_freq = char_freq.sort_by {|a| [-a[1], a[0]] }

(You can also do explicit tests for a 0 result, but sort_by is much
more concise.)

David


David A. Black
removed_email_address@domain.invalid

“Ruby for Rails”, from Manning Publications, coming April 2006!


#6

On Jan 4, 2006, at 13:17, Robert K. wrote:

Grehom wrote:

what am I doing wrong? I wanted to sort primarily on count (second
position in array), then sub-sort alphabetically (first position in
array)

Generally you need to do conditional evaluation based on higher prio
results. Using “||” or “or” won’t help here (dunno what Perl does
here).

In Perl, 0 counts as ‘false’. Not so in Ruby. For example:

     Perl  Ruby

1 || 0 1 1
0 || 1 1 0

So, in Perl, if the first comparison was equal, the result for the
second comparison would be returned by the disjunction.

matthew smillie.


#7

Thanks! interesting stuff I’ll read through this closely there are a
rew bits in there that have gone clear over my head at first reading
(the a*b}.join for example).


#8

On Jan 4, 2006, at 8:24 AM, removed_email_address@domain.invalid wrote:

You can use sort_by, though:

sorted_freq = char_freq.sort_by {|a| [-a[1], a[0]] }

The light bulb will go on with respect to this solution when
you discover that

x <=> y

works as expected when x and y are Arrays. I think this is
one of those cases where Ruby just makes you feel warm all over.

Gary W.


#9

Thanks everyone, very interesting. The sort_by method certainly will
earn it’s keep in my application as my test results show below

require ‘benchmark’
include Benchmark

alphabet = (“abcdefghij”)
char_freq = (1…100000).map {[alphabet[rand(9)].chr, rand(8)+1]}
bm(10) do |b|
b.report(“Sort by”) { char_freq.sort_by {|a| [-a[1], a[0]] } }
b.report(“Sort”) { char_freq.sort {|a, b| (b[1]<=>a[1]).nonzero?
|| a[0]<=>b[0] } }
end

alphabet = (“abcdef”)
char_freq = (1…100000).map {[alphabet[rand(5)].chr, rand(4)+1]}
bm(10) do |b|
b.report(“Sort by”) { char_freq.sort_by {|a| [-a[1], a[0]] } }
b.report(“Sort”) { char_freq.sort {|a, b| (b[1]<=>a[1]).nonzero?
|| a[0]<=>b[0] } }
end

produces >>
C:\rubysrcs\Yahtzee>ruby -w test3.rb
user system total real
Sort by 1.469000 0.000000 1.469000 ( 1.469000)
Sort 2.703000 0.000000 2.703000 ( 2.703000)
user system total real
Sort by 0.766000 0.000000 0.766000 ( 0.766000)
Sort 2.125000 0.016000 2.141000 ( 2.141000)


#10

Grehom wrote:

Thanks everyone, very interesting. The sort_by method certainly will

just as background info, these techniques are called Schwartzian
transforms, or decorate/sort/undecorate // Guttman-Rosler transform (at
least in other languages’ manuals)