Edited at

シェルソート

More than 3 years have passed since last update.

基礎から学ぶデータ構造とアルゴリズム』「4.2 シェルソート」の勉強メモです。自分なりに咀嚼したソート手順とサンプルコード(Ruby)をまとめています。


  1. h だけ離れた数字で組を作る

  2. この組の中で数字を挿入ソートで整列する

  3. h の値を小さくして、1 に戻る

def insertion_sort(a)

n = a.size
1.upto(n - 1) do |j|
temp = a[j]
i = j
while i > 0 && a[i - 1] > temp
a[i] = a[i - 1]
i -= 1
end
a[i] = temp if a[i] != temp
end
end

def shell_sort(a)
n = a.size
h = n / 2
while h > 1
0.upto(h - 1) do |i|
b = []
i.step(n - 1, h) do |j|
b.push a[j]
end

insertion_sort b

i.step(n - 1, h) do |j|
k = b.shift
a[j] = k if a[j] != k
end
end

puts "h = #{h}"
p a

h /= 2
end

insertion_sort a

puts "h = 1"
p a
end

shell_sort [28, 37, 2, 26, 7, 48, 23, 15]

h = 4

[7, 37, 2, 15, 28, 48, 23, 26]
h = 2
[2, 15, 7, 26, 23, 37, 28, 48]
h = 1
[2, 7, 15, 23, 26, 28, 37, 48]


リンク