Rubyでヒープソート書いてみた。
なにかと苦手意識のあったアルゴリズムまわりについてちょっと理解を深めたいなーというか とりあえず著名なアルゴリズムくらいすらすら書けなくて、エンジニアとしてどうなんだとも思うので、買ってみた。
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本(ソフトカバー)
- 購入: 11人 クリック: 656回
- この商品を含むブログ (63件) を見る
見た感じ、よく聞くクイックソートやヒープソートなんかをはじめとして、グラフアルゴリズムやら経路発見やら色々と解説があって一息力を入れて勉強するにはちょうどいい。 基本cでの実装が書いてあるんですが、それをRubyで実装しなおしてみました。
#ruby-2.0.0 #HeapSort def sort(ary) #ヒープ木を生成する buildHeap(ary) i = ary.size - 1 while i > 0 #配列の最後尾iにヒープ木から最大値を抜いて入れて行く ary[0],ary[i] = ary[i],ary[0] #再度縮小したヒープ木に生成し直す heapify(ary,0,i) i -= 1 end end # # ヒープツリーを生成する関数 # @params ary ヒープツリーにしたい配列 # def buildHeap(ary) i = ary.size/2 -1 while i >= 0 heapify(ary, i, ary.size) i -= 1 end end # # @params ary 変形するターゲット配列 # @params idx heapifyを行った回数のindex # @params max # def heapify(ary,idx,max) l_idx = idx * 2 + 1 r_idx = idx * 2 + 2 largest = (l_idx < max and ary[idx] < ary[l_idx]) ? l_idx : idx largest = (r_idx < max and ary[largest] < ary[r_idx]) ? r_idx : largest if idx != largest ary[largest], ary[idx] = ary[idx], ary[largest] heapify(ary,largest,max) end end ary = %w(5 3 16 2 10 14 8 9 6 1 4).map(&:to_i) sort(ary) p ary
やっていた中で、RubyのRangeが降順に使えなくて引っかかった。 使えても良さげなのに。 結局whileで回した。
i = 5 for i in i..1 puts i end