挿入ソート

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

挿入ソート

# 画面に配列の状態を出力する
def trace(ary)
    puts ary.join(", ")
end

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

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