二分木を使ったソート

ヒープじゃなくて単純な二分木を使ったソート。すなわち、

• 左の子は親よりも小さい
• 右の子は親よりも大きい

という構造。で、これを通りがけ順（左の枝、根、右の枝の順に調べる）に出力すると昇順にソートされる。

class BinaryTree

  def initialize(x)
    @val = x
    @left = nil
    @right = nil
  end

  def insert(x)
    if x < @val
      @left.nil? ? @left = BinaryTree.new(x) : @left.insert(x)
    else
      @right.nil? ? @right = BinaryTree.new(x) : @right.insert(x)
    end
  end

  def traverse(&block)
    @left.traverse(&block) unless @left.nil?
    block.call(@val)
    @right.traverse(&block) unless @right.nil?
  end

end

def sort(ary)
  btree = BinaryTree.new(ary.shift)
  ary.each{|x| btree.insert(x) }
  [].tap{|a| btree.traverse{|v| a << v } }
end

if $0 == __FILE__
  sample = (1..100).to_a.sample(10)
  puts "unsorted: " + sample.inspect
  result = sort(sample)
  puts "sorted:   " + result.inspect
end

takatoh@nightschool $ ruby btree_sort.rb
unsorted: [47, 97, 34, 39, 74, 44, 38, 5, 10, 53]
sorted:   [5, 10, 34, 38, 39, 44, 47, 53, 74, 97]