トップ «前の日記(2008-02-23) 最新 次の日記(2008-02-25)» 編集

日々の破片

著作一覧

2008-02-24

_ マージソート

思考する機械コンピュータ (サイエンス・マスターズ)(ダニエル ヒリス) まだ、続きを読んでいるわけだが、
このアルゴリズム(マージソート)では、対象物を二つのグループに分割し、各グループの要素を一つずつ順繰りに取り出しては、昇順に揃える操作を繰り返し、その結果をマージしたものを再びマージの対象にするサブルーチンが再帰的に呼び出される(これでは簡単すぎてうまくいく訳がないとお疑いになる読者は、ご自分で試してみるのも一計である
自分で試すも何もさっぱりわからない説明だ。が、いろいろ考えて、次のようなのができた。これで良いのかな?
NUM_OF_ELEMENTS = 16
o = []
1.upto(NUM_OF_ELEMENTS) do |x|
  o << (rand * NUM_OF_ELEMENTS).to_i
end
p o
 
def m(o0, o1)
  if o0.empty?
    o1
  elsif o1.empty?
    o0
  else 
    [((o0[0] > o1[0]) ? o1.shift : o0.shift)] + m(o0, o1)
  end
end
 
def s(o)
  if o.size > 1
    m(s(o[0...(o.size / 2)]), s(o[(o.size / 2)..-1]))
  else
    o
  end
end
 
p s(o)
実行するとこんな感じ。
$ ruby -d msort.rb
[7, 7, 0, 2, 13, 9, 15, 7, 7, 15, 7, 10, 3, 0, 7, 8]
[7, 7]
[0, 2]
[0, 2, 7, 7]
[9, 13]
[7, 15]
[7, 9, 13, 15]
[0, 2, 7, 7, 7, 9, 13, 15]
[7, 15]
[7, 10]
[7, 7, 10, 15]
[0, 3]
[7, 8]
[0, 3, 7, 8]
[0, 3, 7, 7, 7, 8, 10, 15]
[0, 0, 2, 3, 7, 7, 7, 7, 7, 7, 8, 9, 10, 13, 15, 15]
[0, 0, 2, 3, 7, 7, 7, 7, 7, 7, 8, 9, 10, 13, 15, 15]
(追記:mをちょっと直した(ら、sも直すことになった(ら、デバッグ出力できなくなったので、実行例は嘘になった))。こういう意味かなぁ)

2003|06|07|08|09|10|11|12|
2004|01|02|03|04|05|06|07|08|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|06|07|08|09|10|11|12|
2022|01|02|03|04|05|06|07|08|09|10|11|12|
2023|01|02|03|04|05|06|07|08|09|10|11|12|
2024|01|02|03|

ジェズイットを見習え