ruby

１２月、１月はCODEVS4に集中してたり、２月はうわおえを更新してたりで、アルゴリズムイントロダクションを勧められていなかったが再開！ 動的計画法を解説している書籍やサイトでは、ナップザック問題を取り上げている場合が多い気がする。 でも...

バケツソート、これは内部で使っている挿入ソート部分以外で比較をしないソート。 なんかwikipediaのバケツソートのページを見ると、計数ソートと同じだとか、計数ソートのコードや図が乗っているという無茶苦茶な状態なので、英語版のwikipe...

バブルソート、挿入ソート、選択ソート、ヒープソート、マージソート、クイックソート、ノームソートなどなどなどなど、、 これらはソートの為に値と値を比較するで、ある一定の計算量は必要になっています。 が、スリープソート、計数ソート、基数ソート...

最大部分配列問題。 配列内のある部分を足しあわせたとき、その合計が最大化する部分を探す問題。 例えば配列 があったときに、足しあわせた合計が最大になる部分は、添字1〜4の。要素の合計は15になる。 分割統治法を利用して解くことになる。...

今回はArrayクラスに組み込んだ。 Rubyでは配列外アクセスはnilが帰るだけなので、番兵じゃなくても良い気がするが、ここはセオリーに従い実装。 class Array def merge_sort!(s = 0, e = siz...

今回は挿入ソートの実装。 ソート周りは、Rubyらしく書いている以下の記事もあるけど、本記事ではアルゴリズムの手順そのままRubyで書く。。。え、C使えよって？ で実装はこれ a = 1.upto(a.size-1) do |i|...