アルゴリズム

[Python] 分布数えソートアルゴリズムを実装する方法

2025-01-18更新日: 2025-01-18

分布数えソート(Counting Sort)は、整数の範囲が限られている場合に効率的なソートアルゴリズムです。

基本的な手順は次の通りです。

まず、入力配列の各要素の出現回数をカウントするための配列(カウント配列)を作成します。

次に、カウント配列を累積和に変換し、入力配列の各要素を正しい位置に配置します。

Pythonでは、range()を使ってカウント配列を初期化し、forループで要素をカウントし、最終的にソートされた配列を生成します。

目次から探す

分布数えソートとは

分布数えソート(Counting Sort)は、特定の範囲にある整数を効率的にソートするためのアルゴリズムです。

このアルゴリズムは、配列内の各要素の出現回数をカウントし、その情報を基にソートを行います。

分布数えソートは、比較ベースのソートアルゴリズムとは異なり、計算量がO(n)であるため、大量のデータを扱う際に非常に高速です。

ただし、ソート対象の値の範囲が広い場合には、メモリ消費が大きくなるため、適用する場面を選ぶ必要があります。

特に、整数や小数点以下の数値を扱う場合に有効です。

分布数えソートのアルゴリズムの流れ

分布数えソートは、以下の5つのステップで実行されます。

各ステップの詳細を見ていきましょう。

ステップ1: 配列の最大値と最小値を見つける

まず、ソート対象の配列から最大値と最小値を見つけます。

これにより、カウント配列のサイズを決定します。

最大値と最小値を知ることで、どの範囲の数値を扱うかが明確になります。

ステップ2: カウント配列を作成する

次に、最大値と最小値の範囲に基づいてカウント配列を作成します。

この配列は、各数値の出現回数を記録するためのもので、サイズは最大値と最小値の差に1を加えたものになります。

初期値はすべて0に設定します。

ステップ3: カウント配列を累積和に変換する

カウント配列が作成されたら、次にその配列を累積和に変換します。

これにより、各要素が元の配列におけるその数値の位置を示すようになります。

具体的には、カウント配列の各要素に前の要素の値を加算していきます。

ステップ4: 元の配列をソートする

累積和に変換されたカウント配列を使用して、元の配列をソートします。

元の配列の各要素をカウント配列を参照しながら、正しい位置に配置していきます。

この際、元の配列の要素を逆順に処理することで、安定なソートを実現します。

ステップ5: 結果を出力する

最後に、ソートされた配列を出力します。

これで分布数えソートの処理が完了します。

ソートされた配列は、元の配列の要素が昇順に並んだものになります。

Pythonでの分布数えソートの実装

分布数えソートをPythonで実装する方法を見ていきましょう。

まず、必要なライブラリを確認し、その後に基本的な実装例を示します。

さらに、実装の詳細について解説し、最後に完全なサンプルコードを提供します。

必要なライブラリ

分布数えソートの実装には、特別なライブラリは必要ありません。

Pythonの標準機能のみで実装可能です。

基本的な実装例

以下は、分布数えソートの基本的な実装例です。

def counting_sort(arr):
    # 配列の最大値と最小値を見つける
    max_val = max(arr)
    min_val = min(arr)
    
    # カウント配列の初期化
    range_of_elements = max_val - min_val + 1
    count = [0] * range_of_elements
    
    # カウントの集計
    for num in arr:
        count[num - min_val] += 1
    
    # 累積和の計算
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # ソートされた配列の生成
    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    
    return output

実装の詳細解説

カウント配列の初期化

カウント配列は、ソート対象の数値の範囲に基づいて初期化されます。

最大値と最小値の差を計算し、そのサイズの配列を作成します。

すべての要素は0で初期化されます。

カウントの集計

元の配列をループし、各要素の出現回数をカウント配列に記録します。

ここでは、各要素の値から最小値を引くことで、カウント配列のインデックスを調整します。

累積和の計算

カウント配列を累積和に変換することで、各要素が元の配列におけるその数値の位置を示すようになります。

これにより、ソートの際に正しい位置に配置することが可能になります。

ソートされた配列の生成

累積和を利用して、元の配列を逆順に処理し、ソートされた配列を生成します。

これにより、安定なソートが実現されます。

実装の注意点

分布数えソートは、整数や小数点以下の数値に対して効果的ですが、範囲が広い場合にはメモリ消費が大きくなるため注意が必要です。
浮動小数点数や文字列など、他のデータ型には適用できないことがあります。

完全なサンプルコード

以下は、分布数えソートの完全なサンプルコードです。

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val + 1
    count = [0] * range_of_elements
    
    for num in arr:
        count[num - min_val] += 1
    
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    
    return output
# 使用例
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)