From: jm <jeffm@...>
Date: 2005-03-24T15:24:23+09:00
Subject: Re: Stable sort?


On 21/03/2005, at 10:40 PM, Mathieu Bouchard wrote:

>
> On Thu, 17 Mar 2005, Hal Fulton wrote:
>
>> 2. Further I believe that such an algorithm could be used to implement
>> multi-key sorts as "chained" sorts -- correct?
>>       people.sort(:name).sort(:age).sort(:height)
>

here's another one for no other reason than I need to write one. Has 
the advantage that you can elect which value to hold stable. May not be 
as efficient as the others (haven't benchmarked), but a good excuse to 
work out how to use inject and a bit of a bull at the gate 
implementation.

J.

Struct.new('Simp',:name,:second,:value)
initial = [
   Struct::Simp.new('b',2,'value4'),
   Struct::Simp.new('c',2,'value7'),
   Struct::Simp.new('b',3,'value5'),
   Struct::Simp.new('c',1,'value6'),
   Struct::Simp.new('c',3,'value8'),
   Struct::Simp.new('a',1,'value1'),
   Struct::Simp.new('a',2,'value2'),
   Struct::Simp.new('b',1,'value3'),
]
a = initial
a.sort!{|x,y| x[:name] <=> y[:name]}

# group by field f1, and sub sort on f2
def subsort (ary,f1,f2)
   tmp = [[],[]]
   out = ary.inject(tmp) {|t,s|
     if t[1].empty? or t[1][0][f1] == s[f1]
       t[1] << s
     else
       t[1].sort! {|x,y| x[f2] <=> y[f2]}
       t[0] << t[1]
       # t[0].flatten! # not really needed
       t[1] = []
       t[1] << s
     end
     t
   }
   out[1].sort! {|x,y| x[f2] <=> y[f2]}
   out.flatten!
end

puts '=== initial ==='
puts initial
puts '=== result ==='
puts subsort(initial,:name,:second)