院卒新人サラリーマンのメモ代わり

備忘としてのメモを記載

アルゴリズムをはじめよう実装(ruby)

アルゴリズムをはじめようを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]の交換が行われてしまう。