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)