シェルソート

単純挿入ソートの発展版。
整列されていればされているほど高速になるため、
部分的に単純挿入ソートを繰り返すことで性能を向上させる。

クイックソート登場前は最速のソートだったらしい。

#rubyでループをうまく書けず簡潔でないコードになっている
#挿入を行う条件は２つ
#	１：先頭まで挿入位置が見つからない場合	=>　先頭に挿入
#	２：先頭まで確認する前に挿入位置が見つかった場合　=>　途中に挿入

def shellsort!(array)
  #hの最大値を求める
  #同じ集合に対してソートを繰りかえさないために
  #h=...,121,40,13,4,1となるのが好ましい
  h = 1
  while h < array.size / 9 do
     h = h * 3 + 1
  end

  while h > 0 do
    #h＞0の間繰り返す
    h.step(array.size - 1, 1) do |i|
      #開始位置をhから末尾とするシェルソートを繰り返す
      target = array[i]
      insertion = nil
      (i - h).step(0, -h) do |j|
        #先頭まで繰り返す
        #挿入位置が見つかるまで要素をずらす
        insertion = j
        if array[j] < target then
          #条件２
          #挿入対象が現在位置の要素よりも大きい時
          #挿入位置が現在位置+hに決定する
          insertion += h
          break
        end
        #現在位置の要素をh右（後ろ）へずらす
        array[j + h] = array[j]
      end
      #挿入対象を挿入
      array[insertion] = target
    end
    #hを小さくする(ソートの間隔を短くしていく）
    h /= 3
  end
end

data = Array.new
while input = $stdin.gets.to_i
  break if input < 0
  data << input
end

p data
shellsort!(data)
p data