今回は挿入ソートの実装。
ソート周りは、Rubyらしく書いている以下の記事もあるけど、本記事ではアルゴリズムの手順そのままRubyで書く。。。え、C使えよって？
https://melborne.github.io/2010/10/12/Ruby/
で実装はこれ
a = [3, 2, 1, 5, 3]
1.upto(a.size-1) do |i|
k = a[i]
j = i - 1
while j >= 0 && a[j] > k
a[j+1] = a[j] # ※1
j -= 1
end
a[j+1] = k # ※2
end
p a
# 結果
[1, 2, 3, 3, 5]
挿入ソートは、２〜n番目の要素をkeyとして、それ以前の要素と比較していく方法をとる。
ソートをトレースすると、こんな感じ。
※1 (i=1, j=-1, k=2) a[0]の要素がa[1]に入る
[3, 3, 1, 5, 3]
※2 (i=1, j=-1, k=2) a[0]にkを格納
[2, 3, 1, 5, 3]
※1 (i=2, j=0, k=1) a[1]の要素がa[2]に入る
[2, 3, 3, 5, 3]
※1 (i=2, j=-1, k=1) a[0]の要素がa[1]に入る
[2, 2, 3, 5, 3]
※2 (i=2, j=-1, k=1) a[0]にkを格納
[1, 2, 3, 5, 3]
※2 (i=3, j=2, k=5) a[3]は順番通りなので特に値は入れ替わらない
[1, 2, 3, 5, 3]
※1 (i=4, j=2, k=3) a[3]の要素がa[4]に入る
[1, 2, 3, 5, 5]
※2 (i=4, j=2, k=3) a[3]にkを格納
[1, 2, 3, 3, 5]
