📘
【Python】カウントソートの実装
はじめに
カウントソートの実装例です。
実装
counting_sort.py
from typing import List
def counting_sort(numbers: List) -> List[int]:
max_num = max(numbers)
counts = [0] * (max_num + 1)
result = [0] * len(numbers)
for num in numbers:
counts[num] += 1
# 各数字の個数を調べる
for i in range(1, len(counts)):
counts[i] += counts[i-1]
i = len(numbers) - 1
while i >= 0:
index = numbers[i]
result[counts[index]-1] = numbers[i]
counts[index] -= 1
i -= 1
return result
# テスト
if __name__ == "__main__":
nums = [4,3,6,2,7,1,6]
print(counting_sort(nums))
実装
Discussion