プログラミング

最大部分配列問題。 配列内のある部分を足しあわせたとき、その合計が最大化する部分を探す問題。 例えば配列 があったときに、足しあわせた合計が最大になる部分は、添字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|...

分割統治法を学んでいるついでにクイックソートを自作する。 クイックソートはピボットの選び方の違いで平均計算量に違いが出るそう。 今回実装したのは、部分配列の先頭をピボットにするという安易な方法。 あんまQUICKじゃな・・ def qu...

Union-Findアルゴリズムを木構造で実装する。 wikiに擬似コードでアルゴリズムが書いてある。 Union-Findがどんなもんかというと、何個かの要素があるとして ２番目と５番目を同じグループにして（Union） ３番目と４番...

久しぶりに自分のブログにアクセスしたら「データベース接続エラー」になってた・・。 最近ブログ放置していた、というのも、RailsとかJSとかのwebネタは社内の情報共有場所に投稿してしまうので、この個人ブログに重複して書くのもうんこだなーと...