【アルゴリズム】【Ruby】ソートのいろいろ ~選択法 / 交換法 / 挿入法
「アルゴリズム 練習問題」で検索したらヒットする、
アルゴリズムに関して書いてあるサイト
を読んでいます。
選択法
一番小さい値を探す
それを一番上に書く
チェック済みだよと言う意味で、その値を消す(チェックする)
これを要素数分繰り返す
やってみよう
p a = (1..10).to_a.sample(10) s = [] i = 0 while i < a.size min = a[i] j = 0 while j < a.size if a[j] < min min = a[j] changed = j end j += 1 end s << min a[changed] = 999 i += 1 end p s
■実行結果
[3, 8, 1, 9, 2, 10, 7, 5, 4, 6] [1, 2, 3, 4, 5, 6, 7, 7, 8, 9]
ふーん。
交換法
選択法を少し発展させて、一番小さい値を消す(チェックする)のをやめ、 その選択された値と、それが入る順番の要素データを交換しながら処理することにする
やってみよう
p a = (1..10).to_a.sample(10) i = 0 while i < a.size min = a[i] j = i + 1 changed = -1 while j < a.size if a[j] < min min = a[j] changed = j end j += 1 end a[i] , a[changed] = a[changed] , a[i] if changed != -1 i += 1 end p a
■実行結果
[3, 6, 7, 10, 4, 2, 5, 8, 9, 1] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ふーん。
挿入法
整列済みの配列に、次のデータを挿入していくと考える。
http://www5c.biglobe.ne.jp/~ecb/algorithm/6_a.html
データの最後まで(次のデータがなくなるまで)繰り返す。
なるほど。
やってみよう
a = (1..5).to_a.shuffle! def insert_with_order(result, var) index = result.find_index{|item| item > var} || result.length result.insert(index, var) end result = a.inject([]) do |result, var| insert_with_order(result, var) end p result
■実行結果
[8, 1, 7, 3, 9, 5, 6, 10, 4, 2] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ふーん。
※以前記載していた方法は、誤実装(バブルソートだった)ので、取り下げました。
こちらのサイトを参考に実装しました。
hp12cさんの書くコードはいつも面白い。
ただ、この記事で紹介しているクイックソートの
push base
は、不必要だと思うのだけれど。。。なぜ存在するのかな。。
散々hp12cさんには色々質問してるのでこれ以上聞けないけど、気になる><
クイックとバブルは前やったので省略。
ソート終わり。