シェルソート

『基礎から学ぶデータ構造とアルゴリズム』「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]

リンク

• バブルソート、選択ソート、挿入ソート
• クイックソート
• マージソート