組み込み開発のためのPython · レッスン 163 / 220
カウンティングソートを理解する
カウンティングソートは値の出現数を数え、値域が狭い整数の整列に使えます。メモリ量は最大値と最小値の差に依存します。
カウンティングソートは値の出現数を数え、値域が狭い整数の整列に使えます。メモリ量は最大値と最小値の差に依存します。 仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。
基本の考え方
カウンティングソートは値の出現数を数え、値域が狭い整数の整列に使えます。メモリ量は最大値と最小値の差に依存します。
安全に試すための確認
計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。
コード例
手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。
values = [2, 1, 2, 0, 1]
counts = [0] * (max(values) + 1)
for value in values:
counts[value] += 1
sorted_values = [value for value, count in enumerate(counts) for _ in range(count)]
print(sorted_values)手を動かす課題
負数を含む場合に基準値をずらす方法を実装し、値域が巨大なときの問題を説明してください。