From: Mathieu Bouchard <matju@...>
Date: 2005-03-21T20:40:15+09:00
Subject: Re: Stable sort?


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)

no, maybe this:

a=people.sort(:name)
a.each_extent(:name) {|i,n|
  a[i,n].sort!(:age)
  a[i,n] = a[i,n].each_extent(:age) {|i_,n_|
    # gets worse here...
  }
}

where #each_extent is like each_index but also gives the number of
elements with the same key and then skip over them:

class Array
  def each_extent(sym)
    i=j=0
    while j<length
      i=j
      j+=1 while self[i].__send__(sym)==self[j].__send__(sym)
      yield i,j-i
    end
  end
end

Then you could use SubArray (found in MetaRuby) to sort everything
in-place, but MetaRuby's sort is slow, because it's written in Ruby *and*
because speed never was a concern there. Then it would be:

a=people.sort(:name)
a.each_extent(:name) {|i,n|
  b=people.part(i,n)
  b.sort!(:age)
  b.each_extent(:age) {|i_,n_|
    # etc
  }
}

Then Matz suggested using sort_by with an array. If that is too heavy,
then you can use any order-preserving function (that is, for which
f(x)<f(y) exactly when x<y), as long as it returns something simpler than
an array. However, that pretty much just means Fixnum, and not Array, and
it's not really feasible to stay in the Fixnum range while keeping those
condensed-keys easy to compute...

_____________________________________________________________________
Mathieu Bouchard -=- Montr�al QC Canada -=- http://artengine.ca/matju