計数ソート
要素間の比較に基づかないソートアルゴリズム
要素の登場数をカウントする補助配列を用いる
補助配列の添字順に並ぶことになる
配列の要素がn個、要素の集合がk個の場合、$ O(n+k)
nがkと比べて大きいほど有効
安定ソート
code:ruby
def counting_sort(array, k)
c = Array.new(k,0)
array.each do |elem|
end
1.upto(k-1) do |i|
end
b = Array.new(array.size)
(array.size-1).downto(0) do |i|
end
b
end
a = 7,2,9,0,1,2,0,9,7,4,4,6,9,1,0,9,3,2,5,9 k = 10
p counting_sort(a, k)
# => 0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 9, 9, 9, 9, 9