Ruby でバケットソートを書いてみた

バケットソートとは？

バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。

「バケットソート」 『フリー百科事典　ウィキペディア日本語版』- 2017年2月5日 (日) 16:26 14:49 https://ja.wikipedia.org/wiki/バケットソート

コード

require "prime"
module BacketArray
  refine Array do
    def backet_sort
      each_with_object(Array.new(size)) { |e, a| a[e] = e }.compact
    end
  end
end

class Test
  using BacketArray
  def self.go
    list = Prime.take(10).shuffle
    print list,"\n"
    print list.backet_sort
  end
end

Test.go

実行結果

[11, 2, 3, 29, 7, 19, 13, 5, 23, 17]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]