C++で実装する鳩の巣ソート（Pigeonhole Sort）の仕組みとサンプルプログラム

鳩の巣ソート（Pigeonhole Sort）とは

鳩の巣ソートは、要素同士の比較を一切行わない「非比較ソート」手法の一つです。ソート対象の要素数（n）と、キーとなりうる値の範囲（N）がほぼ同じである場合に特に適しており、計算量は O(n + N) で動作します。別名「カウントソート（Count Sort）」とも呼ばれています。

このソートを実行するには、まず「穴（ピジョンホール）」を用意します。必要な穴の数は、数値の範囲によって決定されます。各要素を対応する穴に挿入していき、最後に穴から取り出して配列へ格納することで、ソート済みの並び順が完成します。

Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7

アルゴリズムの手順

• 配列内の最小値（min）と最大値（max）を求めます。その後、範囲を「max − min + 1」として計算します。

• 求めた範囲と同じサイズの、初期状態が空の配列（ピジョンホール用の配列）を用意します。

• 元の配列の各要素を走査し、それぞれ対応する穴へ格納します。要素 arr[i] は、インデックス「arr[i] − min」の位置にある穴に入ります。

• 最後に、ピジョンホール用の配列を先頭から順番に走査し、空でない穴からすべての要素を元の配列へ書き戻します。

C++による実装例

#include <iostream>
using namespace std;
#define MAX 7
void pigeonhole_sort(int, int, int *);
int main() {
    int i, min, max;
    int a[]={7,4,2,6,3,1,5};
    min = a[0];
    max = a[0];
    for (i = 1; i < MAX; i++) {
        if (a[i] < min) {
            min = a[i];
        }
        if (a[i] > max) {
            max = a[i];
        }
    }
    pigeonhole_sort(min, max, a);
    for (i = 0; i < MAX; i++) {
        cout<< a[i]<<"\t";
    }
}
void pigeonhole_sort(int mi, int ma, int * a) {
    int size, count = 0, i;
    int *current;
    current = a;
    size = ma - mi + 1;
    int holes[size];
    for (i = 0; i < size; i++) {
        holes[i] = 0;
    }
    for (i = 0; i < size; i++, current++) {
        holes[*current-mi] += 1;
    }
    for (count = 0, current = &a[0]; count < size; count++) {
        while (holes[count]--> 0) {
            *current++ = count + mi;
        }
    }
}

出力結果

1 2 3 4 5 6 7

まとめ

鳩の巣ソートは、データの値の範囲が狭く、要素数とほぼ一致している場合に非常に効率的なソートアルゴリズムです。時間計算量は O(n + N)、補助記憶域として範囲分の配列が必要となるため、空間計算量は O(N) となります。比較ベースのソート（クイックソートやマージソートなど）とは異なるアプローチなので、用途に応じて使い分けることが重要です。