度数分布ソート

別名「数え上げソート」と呼ばれ、その名のとおりそれぞれの要素がいくつあるかを数えていく。
数え上げた結果の累積分布表と原配列を参照し、要素の挿入を行うことでソートが完了する。
そのため、数値を比較する必要がなく高速にソートを行える。

今回は累積度数分布を使用している。安定ソート。
別の方法として、累積度数を求めず度数分布をそのまま使用してもよい。
その場合は、度数分布の分だけ先頭から要素をつめていく。
よって、安定でないソートとなる。

計算量はO(n)であり、非常に高速。
しかし、度数分布表、累積分布表を作成するためには、
「０以上の整数」から「原配列の最大値」まですべてを格納する配列が必要である。
そのため、ソート対象があらかじめ有限の範囲におさまることが保証されていなければならない。

def countingsort(array)
  #配列の最大値を求める
  maxnum = array.max
  #最大値までの度数分布を格納する配列を生成し、０で初期化
  frequency = Array.new(maxnum + 1).fill(0)
  #最大値までの要素がそれぞれいくつあるかカウント
  0.step(array.size - 1, 1) do |i|
    frequency[array[i]] += 1
  end
  #度数分布から累積度数分布を生成
  1.step(frequency.size - 1, 1) do |i|
    frequency[i] += frequency[i - 1]
  end 

  #原配列と累積度数分布を用いてソート済み配列を生成
  sorted = Array.new(array.size)
  (array.size - 1).step(0, -1) do |i|
    #原配列の持つ後方から処理していく
    target = array[i]
    #対象値の累積度数分布での位置を取得
    index = frequency[target]
    #取得した位置を１つずらして挿入
    sorted[index - 1] = target
    #対象値の累積度数分布での位置を１つずらす
    frequency[target] -= 1
  end
  return sorted
end

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

p data
p countingsort(data)

机上での動作確認と実装・テストで時間ほど。