バケツソート

ハッシュと挿入ソートを組み合わせたソートである。
ハッシュ関数により、要素をいくつかの小さいバケツに分ける。
そして、それぞれのバケツの中で挿入ソートを行う。
挿入ソートはO(n^2)なので、それぞれのバケツ中の要素数が少ないほど高速。

したがって、O(n)の性能を出したいのであれば、
１つのバケツに入っている要素数が少なくなるよう、
適したハッシュ関数と十分に多数なバケツを用意する必要がある

今回はハッシュテーブルの長さ（バケツの個数）を4とした。
要素{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}に対応する。

なお、リンクつきリストでバケツを動的に確保する場合、固定長配列よりも高速になる。

#バケツソート
#ハッシュと挿入ソートを組み合わせたソートである。

require "./shuttlesort.rb"

@TableLength = 4

def myhash(key)
  return key / @TableLength
end

def bucketsort!(array)
  bucket = Array.new(@TableLength).map{ Array.new }
  #バケツに要素を加える
  array.each{|k|
    bucket[myhash(k)] << k
  }
  p bucket
  extract!(bucket, array)
end

#各バケツについて挿入ソートを行い、原配列に挿入
def extract!(bucket, array)
  indexInsert = 0
  bucket.each{|b|
    shuttlesort!(b) if  b.size > 0
    b.each{|k|
      array[indexInsert] = k
      indexInsert += 1
    }
  }
end

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

p data
bucketsort!(data)
p data

もろもろで1時間30分ほど。
挿入ソートは、http://d.hatena.ne.jp/matasaburou/20131209/1386601142参照のこと。