鳩の巣ソート（Pigeonhole Sort）とは？仕組み・計算量とC++実装を解説

鳩の巣ソートとは

鳩の巣ソート（Pigeonhole Sort）は、非比較型ソートに分類される整列アルゴリズムの一つです。比較演算によって大小関係を判定するクイックソートやマージソートとは異なり、値そのものを「穴（ホール）」に振り分けることで並べ替えを行います。

この手法は、ソート対象の要素数と、キーとなり得る値の範囲がほぼ同じである場合に特に高い効果を発揮します。

具体的な手順は以下のとおりです。まず、値の範囲に応じた個数の「穴」を用意します。次に、各要素をその値に対応する穴へ挿入し、最後に穴から先頭の要素を順番に取り出して配列へ格納すれば、整列された結果が得られます。

鳩の巣ソートの計算量

• 時間計算量：O(n + 2^k)
• 空間計算量：O(2^k)

入力と出力の例

Input:
The unsorted list: 802 630 20 745 52 300 612 932 78 187
Output:
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932

アルゴリズム

pigeonHoleSort(array, size)

入力 − データの配列と、配列内の要素の総数

出力 − ソート済みの配列

Begin
    find max and min from the array list
    holeRange := max – min +1
    define holeRange number of Lists

    for i := 0 to n-1 do
        hole[array[i]-min].append(array[i])
    done

    count := 0
    for j := 0 to holeRange-1 do
        while hole[j] is not empty do
            array[count] := get first node of hole[j] and delete it
            count := count +1
        done
    done
End

処理の流れのポイント

1. 配列内の最大値と最小値を求めます。
2. 範囲の大きさ max − min + 1 を算出し、その数だけリスト（穴）を用意します。
3. 各要素を「要素の値 − 最小値」で計算したインデックスの穴に追加します。
4. 小さい方の穴から順に要素を取り出し、配列の先頭から詰めていくことで整列が完了します。

C++による実装例

#include<iostream>
#include<list>
#include<cmath>
using namespace std;

void getMaxMin(int *arr, int n, int &maximum, int &minimum) {
    maximum = minimum = arr[0]; // 最初は最大値・最小値ともにarr[0]

    for(int i = 1; i<n; i++) {
        if(arr[i] > maximum)
            maximum = arr[i];   // 最大値を取得
        if(arr[i] < minimum)
            minimum = arr[i];   // 最小値を取得
    }
}

void pigeonHoleSort(int *arr, int n) {
    int max, min;
    getMaxMin(arr, n, max, min);
    int holeRange = max - min + 1;
    list<int> hole[holeRange];  // 穴となるリストの配列を作成

    for(int i = 0; i<n; i++) {
        hole[arr[i]-min].push_back(arr[i]);
    }

    int count = 0;
    for(int j = 0; j<holeRange; j++) {
        // 連結リストから削除しながら配列へ格納
        while(!hole[j].empty()) {
            arr[count] = *(hole[j].begin());
            hole[j].erase(hole[j].begin());
            count++;
        }
    }
}

void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n]; // 指定された要素数の配列を作成
    cout << "Enter elements:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "Data before Sorting: ";
    display(arr, n);
    pigeonHoleSort(arr, n);
    cout << "Data after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 10
Enter elements:
802 630 20 745 52 300 612 932 78 187
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932

まとめ

鳩の巣ソートは、値の分布が密なデータに対しては非常に高速に動作するシンプルなアルゴリズムです。一方で、値の範囲が広いデータ（例：最大値と最小値の差が極端に大きい場合）では、必要なメモリ量が膨大になるため不向きです。データの特性を見極めた上で使い分けることが重要です。