algorithm
ピジョンホールソート

ピジョンホールの基本情報のソート

Pigeonhole Sortは要素の数（n）と可能なキー値（N）の数がほぼ同じ要素のリストをソートするのに適したソートアルゴリズムです。ここで、nは入力配列の要素数であり、 'Range'は配列可能な値の数であるO（n + Range）時間が必要です。

Pigeonholeの作業（擬似コード）Sort：

1. 最小値と最大値を配列で検索します。最小値と最大値をそれぞれ「min」と「max」とします。また、 'max-min-1'として範囲を見つける。
2. 最初に空の "pigeonholes"の配列を範囲と同じサイズに設定します。
3. 配列の各要素にアクセスし、各要素をピジョンホールに配置します。要素input [i]はindex input [i] - minの穴に入れられます。
4. ピジョンホール配列全体をループで順番に開始し、空でない穴の要素を元の配列に戻します。

ピジョンホールの並べ替えは、並べ替えの種類に似ているので、ピジョンホールの並べ替えとカウントの並べ替えを比較します。

ピジョンホールソートの例：

スペース補助： O(n)
時間複雑度： O(n + N)

C＃の実装

public class PigeonholeSort
{
    private static void SortPigeonhole(int[] input, int n)
    {
        int min = input[0], max = input[n];
        for (int i = 1; i < n; i++)
        {
            if (input[i] < min) min = input[i];
            if (input[i] > max) max = input[i];
        }
        int range = max - min + 1;
        int[] holes = new int[range];

        for (int i = 0; i < n; i++)
        {
            holes[input[i] - min] = input[i];
        }
        int index = 0;

        for (int i = 0; i < range; i++)
        {
            foreach (var value in holes)
            {
                input[index++] = value;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortPigeonhole(input, input.Length);
        return input;
    }
}