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

シェルソート

Rubyアルゴリズムの勉強してます。 元ネタはプログラミングコンテスト攻略のためのアルゴリズムとデータ構造です。

def trace(ary)
    puts ary.join(", ")
end

# 配列を受取、挿入ソートする
def insertionSort(ary, g)
    n = ary.size - 1
    (g..n).each do |i|
        v = ary[i]
        j = i - g
        while (j >= 0 and ary[j] > v) do
            ary[j + g] = ary[j]
            j -= g
        end
        ary[j + g] = v
        trace ary
    end
    ary
end

def shellSort(ary)
    n = ary.size
    gen = []
    h = 1
    while h <= n do
        gen << h
        h = 3 * h + 1
    end
    gen_n = gen.size
    (gen_n - 1).downto(0).each do |i|
        insertionSort(ary, gen[i])
    end
end

ary = gets.split(" ").map(&:to_i) # 標準入力からスペース区切りで配列を受け取る
trace ary # 初期値表示
shellSort ary