【アルゴリズムの勉強】Rubyで分布数え上げソート（カウンティングソート、度数ソート）を書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyで分布数え上げソート（カウンティングソート、度数ソートとも呼ばれる）を実装する。

分布数え上げソートとは

分布数え上げソートはソート対象のデータをキーにして、キーの出現回数とその累積度数分布を計算して利用することで整列を行うアルゴリズムです。 バケットソートと同じくキーとなるデータがとりうる値の範囲をあらかじめ知っている必要があります。バケットソートとの違いはキーの重複に対応したアルゴリズムであるということです。

分布数え上げソート : アルゴリズム

Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12, 9]
number_of_elements = arr.count
max = arr.max

def counting_sort(arr, number_of_elements, max)
  counting_arr = Array.new(max + 1, 0)
  answer = []

  for i in 0..(number_of_elements - 1)
    counting_arr[arr[i]] += 1
  end

  for i in 1..max
    counting_arr[i] += counting_arr[i - 1]
  end

  (number_of_elements - 1).downto(0) {|i|
    key = counting_arr[arr[i]] - 1
    answer[key] = arr[i]
    counting_arr[arr[i]] += -1
  }
  return answer
end

sorted_arr = counting_sort(arr, number_of_elements, max)
p sorted_arr
# => [2, 4, 6, 9, 9, 10, 12, 15, 20, 25, 60]

参考文献、参考リンク