アルゴリズムをはじめよう実装(ruby)
#二分探索 def binary_search(array, serch_num) head = 0 tail = array.length - 1 while head <= tail center = (head+tail) /2 case array[center] <=> serch_num when -1 head = center +1 when 0 return puts "見つかった #{serch_num}はarray[#{center}]" when 1 tail = center -1 end end puts "見つからないよ" end
#挿入ソート def insert_sort(array) for i in 0..array.length-1 tmp = array[i] k = i while k>0 && array[k-1]>tmp array[k] = array[k-1] k -=1 end array[k] = tmp #1 end puts array end
whileのループ(デクリメントとかループカウンタの初期値)のところを
forとかでもっとうまく書けるかなと思ったけど
kをブロック変数にしてしまうと#1のとこで代入できなくなっちゃうから
これが今のところベスト
#バブルソート def bubble_sort(array) 1.upto(array.length-1) do |k| #2 (array.length-1).downto(k) do |i| if array[i-1] > array[i] array[i-1], array[i] = array[i], array[i-1] #3 end end end puts array end
配列のインデックスで少しこんがらがった。
1.upto(array.length-1) do |i| #=> i = 1,2,..,length-1 for(i=1; i<=array.length-1; i++) #=> i = 1,2,..,length-1
個人的なメモ
uptoやfor inの終了条件はcとかのforで書き直すと=も含む。
イコールが含まれてるから#2を0.upto とすると#3でarray[0]とarray[-1]の交換が行われてしまう。