rubyで計数ソート

バブルソート、挿入ソート、選択ソート、ヒープソート、マージソート、クイックソート、ノームソートなどなどなどなど、、
これらはソートの為に値と値を比較するで、ある一定の計算量は必要になっています。

が、スリープソート、計数ソート、基数ソート、バケットソートなど、値と値の比較を必要としないアルゴリズムも存在する。
計算量は、比較をするソートに比べて少なくて済む場合が多い。

今回はその中でも、計数ソートをRubyで実装した。

class Array
  def counting_sort
    new_a   = []
    counter = []

    each { |n| counter[n] = counter[n].to_i + 1 }

    counter.each_with_index do |n, idx|
      counter[idx] = n.to_i + counter[idx-1].to_i if idx > 0
    end

    reverse_each do |n|
      new_a[counter[n]-1] = n
      counter[n] -= 1
    end

    new_a
  end
end

a = [4,2,5,4,77,3,3,4,2,56]

p a.counting_sort

[2, 2, 3, 3, 4, 4, 4, 5, 56, 77]

値を添え字として直接使用する。
つまり、大きい数が存在すると、めっちゃ長い配列が必要になる。。

6行目では、同じ数字が何回出てきているかを数えている。
たとえば、元の配列が[4, 2, 5, 4]だったとすると、counterはこうなる。

[nil, nil, 1, nil, 2, 1]

これは、2が1つ、4が2つ、５が1つ。という情報。

8〜10行目では、その添字以下の数字が何個あるかという情報をもつ。
先の例ではこうなる。

[nil, 0, 1, 1, 3, 4]

1以下の数が0個、2以下の数が1個、3以下の数が1個、4以下の数が3個、5以下の数が4個。という情報。

この情報を使って、12〜15行目のように取り出せば、ソート済みの配列になっているという。
トレースするとこう。

counter => [nil, 0, 1, 1, 3, 4]
new_a[counter[4]-1] => new_a[3-1] => new_a[2]
なので、new_a[2] に 4 を入れる。

counter => [nil, 0, 1, 1, 2, 4]
new_a[counter[5]-1] => new_a[4-1] => new_a[3]
なので、new_a[3] に 5 を入れる。

counter => [nil, 0, 1, 1, 2, 3]
new_a[counter[2]-1] => new_a[1-1] => new_a[0]
なので、new_a[0] に 2 を入れる。

counter =>[nil, 0, 0, 1, 2, 3]
new_a[counter[4]-1] => new_a[2-1] => new_a[1]
なので、new_a[1] に 4 を入れる。

結果、new_a => [2, 4, 4, 5] になっている。