カウントソートとは?【アルゴリズム紹介・Pythonによる実行】

本記事はPythonのカウントソートについて、学生エンジニアが初心者の方へ向けて優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なカウントソートを一緒に学習しましょう!

カウントソートとは?

カウントソートは、比較を行わない珍しい整列アルゴリズムです。
比較を行う代わりに、数え上げ(カウント)を利用してソートを行います。

カウントソートを文書で説明すると非常に難しいので、下に掲載した動画をご覧ください。
海外の動画ですが、字幕が日本語でしっかりと付いているので理解できると思います。


いかがでしたでしょうか。
出現頻度を数え上げることでソートを実現できている、非常に面白いアルゴリズムです。

カウントソートについて、簡単に解説すると、
出現頻度を計算し、出現頻度リストに格納しておきます。
リストの要素を出現頻度リストにおけるインデックスとして記憶することで,要素の順番を整列することができます。

カウントソートの計算量

平均計算時間最悪計算時間最良計算時間
O(n)O(n)O(n)

カウントソートの計算量は「O(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を用いて作成したバケットソートの関数です。
6行目で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]

実行結果から、
21行目で宣言した[23, 11, 36, 31, 8, 1]のリストを昇順に上手くソートできています。

ということで、本記事はカウントソートについて、Pythonのコードを使用しながらまとめました。
最後まで読んでいただき、ありがとうございました\(^o^)/

超オススメのPC用品

PCを操作する上で、トラックボールマウスが非常におすすめです!
僕も感動したこのマウスを、騙されたと思って使ってみてください!(^^)

外部モニターで2倍以上の効率化が見込めます!
安いものだと、たったの1万円前後なのでおすすめですよー!\(^o^)/

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です