読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【アルゴリズム】【Ruby】ソートのいろいろ ~2分挿入ソート

ソートのすごい記事
とか
自分で工夫してソートを考えている記事
とかみて戦慄している。。。


関係ないけど、昔の恋人にメール送ると
「こんなところが好きだった」と「こんなところが嫌いだった」
がごちゃまぜになって、なんともいえない気持ちになるよね。
自分の気持ちを解析したくない瞬間、トップ10に入るね。


■2分挿入ソート

p a = (1..5).to_a.shuffle!
def where(result, left, right, var)
  return 0 if result == []
  return left if left > right
  middle = (left + right)/2
  if var < result[middle]
    where(result, left, middle-1, var)
  else
    where(result, middle+1, right, var)
  end
end
def insert_with_order(result, var)
  index = where(result, 0, result.length-1, var)
  result.insert(index, var)
end

result = a.inject([]) do |result, var| 
  insert_with_order(result, var)
end
p result

■実行結果

[5, 3, 4, 1, 2]
[1, 2, 3, 4, 5]