Pythonでカウントソートを実装する方法｜サンプルコード付きで解説

この記事では、以下の問題文に対する解決策について詳しく解説します。

問題文

問題： 配列が与えられたとき、カウントソート（Counting Sort）のアルゴリズムを用いて、その配列を昇順に並べ替えます。

カウントソートとは？

カウントソートは、あらかじめ決められた範囲内のキーを対象として動作する整列アルゴリズムです。まず、それぞれ異なるキー（値）を持つ要素がいくつあるかを数え上げます。その後、累積和の計算を行うことで、各要素がソート後の配列のどの位置に配置されるべきかを求め、結果を出力します。

この手法は、キーの取り得る範囲が狭い場合に特に有効で、時間計算量は O(n + k)（n は要素数、k はキーの範囲の大きさ）と非常に高速です。一方で、要素同士を比較しない「非比較ソート」であるため、適用できるデータの種類には制約がある点に注意しましょう。

実装例

それでは、実際の実装を見ていきましょう。

def countSort(arr):
    # ソート済みの文字を格納する出力用配列
    output = [0 for i in range(256)]
    # 0で初期化したカウント用配列を作成
    count = [0 for i in range(256)]
    # 文字列はイミュータブル（変更不可）なのでリストを用意
    ans = ["" for _ in arr]
    # 各文字の出現回数をカウント
    for i in arr:
        count[ord(i)] += 1
    # 累積和を計算し、出力配列内での各文字の位置を求める
    for i in range(256):
        count[i] += count[i-1]
    # 出力用の文字配列を構築
    for i in range(len(arr)):
        output[count[ord(arr[i])]-1] = arr[i]
        count[ord(arr[i])] -= 1
    # ソート済みの文字配列を完成させる
    for i in range(len(arr)):
        ans[i] = output[i]
    return ans

# メイン処理
arr = "Tutorialspoint"
ans = countSort(arr)
print ("Sorted character array is "+str("".join(ans)))

出力結果

Sorted character array is Taiilnooprsttu

コード内で宣言されたすべての変数はローカルスコープに存在し、それぞれの値は上記の処理フローの中で更新されていきます。

処理の流れを解説

このプログラムの動作は、主に次の3つのステップで構成されています。

1. カウントフェーズ： 入力文字列の各文字を ord() 関数でASCIIコードに変換し、対応するインデックスにあるカウント配列の値を1ずつ増やします。
2. 累積計算フェーズ： カウント配列に対して累積和を取ることで、「その文字以下の文字が全体で何個あるか」を求めます。これにより、各文字が出力配列のどこに配置されるべきかが確定します。
3. 配置フェーズ： 入力文字列を先頭から順に走査しながら、累積カウントを基準に出力配列へ文字を配置し、配置済みの分だけカウントを減らしていきます。

まとめ

この記事では、Pythonでカウントソートを実装するプログラムの作成方法について学びました。カウントソートは、キーの範囲が限定されたデータに対して O(n + k) という高速な整列を実現できる強力なアルゴリズムです。ぜひ実際にコードを動かして、その挙動を確認してみてください。