[Ruby] CHALLENGE: two column sort, three column sort

[Ryan Pavlik]

On 13 Aug 2003 14:35:03 -0700
Eric Hodel <drbrain at segment7.net> wrote:

> Write an algorithm that will take an Array of Items with two fields,
> and sort them by the first field then second field.

<snip> 

> I have the first algorithm in Javascript, (with bonus point 2) and
> it is slow (but that's no surprise, the servers suck).  Now they
> want the second version, but that'll be even slower, I'm sure.  I'm
> uncertain of how much slower, and am wondering if I'm missing some
> obvious (but not to me) optimizations.
<snip>

In ruby this appears trivial; first because:

    a = [
      [2,3],
      [1,3],
      [1,2],
      [2,1],
    ]

    a.sort => [[1, 2], [1, 3], [2, 1], [2, 3]]

Next, you can make sort work for your Struct by defining <=> or a
compare function and using it for sort:

    Item = Struct.new('Item', :f1, :f2, :f3)

    def cmp_item (a,b)
      f1 = a.f1 <=> b.f1
      f2 = a.f2 <=> b.f2
      f3 = a.f3 <=> b.f3
      (f1 == 0 ? (f2 == 0 ? f3 : f2) : f1)
    end
    
    a = [
      Item.new(3,1,2),
      Item.new(1,4,1),
      Item.new(1,2,3),
      Item.new(1,3,4),
      Item.new(3,2,1)
    ]
    
    
    p a.sort { |a,b| cmp_item(a,b) }
    
There are probably ways to make it more general; not using Struct is
probably a good start.  As for the big-Oh, it's whatever Array#sort()
is, which I'd guess is O(n log n).

hth,

-- 
Ryan Pavlik <rpav at users.sf.net>

"It's like post modern irony, but really dumb." - 8BT