カウントソートについて
概要
- 手順
- 最大値、最小値を求め、その間の整数の要素数を持つarrayを作成する
- 対応するインデックスの場所に出現回数を記録する
- arrayを展開することでsortになる
コード
def count_sort(arr):
max_num = max(arr)
min_num = min(arr)
count = [0] * (max_num - min_num + 1)
for ele in arr:
count[ele - min_num] += 1
ret = []
for idx, count in enumerate(count):
for _ in range(count):
ret.append(idx + min_num)
return ret
arr = [81, 77, 66, 34, 93, 27, 14, 65, 84, 65, 28]
assert count_sort(arr) == sorted(arr), "一致しません"