tetoblog 
本記事はPythonのカウントソートについて、優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なカウントソートを一緒に学習しましょう！
カウントソートとは？
カウントソートは、比較を行わない珍しい整列アルゴリズムです。
比較を行う代わりに、数え上げ（カウント）を利用してソートを行います。
カウントソートを文書で説明すると非常に難しいので、下に掲載した動画をご覧ください。
海外の動画ですが、字幕が日本語でしっかりと付いているので理解できると思います。
いかがでしたでしょうか。
出現頻度を数え上げることでソートを実現できている、非常に面白いアルゴリズムです。
カウントソートについて、簡単に解説すると、
出現頻度を計算し、出現頻度リストに格納しておきます。
リストの要素を出現頻度リストにおけるインデックスとして記憶することで，要素の順番を整列することができます。
カウントソートの計算量
| 平均計算時間 | 最悪計算時間 | 最良計算時間 |
| Ｏ（n） | Ｏ（ｎ） | Ｏ（n） |
カウントソートの計算量は「Ｏ（n）」であり、安定ソートです。
例えば、[23, 11, 36, 31, 8, 1]をカウントソートで実行する場合、
[0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
のリストが生成されます。
ご覧の通り無駄なメモリが必要になるので場合によって大きな欠点となります。
Pythonコード
def count_sort(nums):
max_num = max(nums)
elements = [0] * (max_num + 1)
ans = [0] * len(nums)
for num in nums:
elements[num] += 1
for i in range(1, len(elements)):
elements[i] += elements[i - 1]
i = len(nums) - 1
while i >= 0:
index = nums[i]
ans[elements[index] - 1] = nums[i]
elements[index] -= 1
i -= 1
return ans上記がPythonを用いて作成したバケットソートの関数です。
６行目でnumsの出現頻度をelementssのリストに格納
カウントソートの実行例
上記で作成した関数を利用して、実際にカウントソートをPython環境で実行してみました。
下記がそのコードと実行結果です。
def count_sort(nums):
max_num = max(nums)
elements = [0] * (max_num + 1)
ans = [0] * len(nums)
for num in nums:
elements[num] += 1
for i in range(1, len(elements)):
elements[i] += elements[i - 1]
i = len(nums) - 1
while i >= 0:
index = nums[i]
ans[elements[index] - 1] = nums[i]
elements[index] -= 1
i -= 1
return ans
if __name__ == '__main__':
nums = [23, 11, 36, 31, 8, 1]
print(count_sort(nums))【実行結果】
[1, 8, 11, 23, 31, 36]実行結果から、
２１行目で宣言した[23, 11, 36, 31, 8, 1]のリストを昇順に上手くソートできています。
ということで、本記事はカウントソートについて、Pythonのコードを使用しながら紹介しました。
最後まで読んでいただき、ありがとうございました＼(^o^)／
超オススメのPC用品
PCを操作する上で、トラックボールマウスが非常におすすめです！
僕も感動したこのマウスを、騙されたと思って使ってみてください！(^^)
外部モニターで２倍以上の効率化が見込めます！
安いものだと、たったの１万円前後なのでおすすめですよー！＼(^o^)／
