algorithm
비둘기 구멍 정렬

비둘기 구멍 기본 정보 정렬

Pigeonhole Sort 는 요소 수 (n)와 가능한 키 값 (N)의 수가 거의 같은 요소 목록을 정렬하는 데 적합한 정렬 알고리즘입니다. 그것은 O (n + Range) 시간이 필요합니다. 여기서 n은 입력 배열의 요소 수이고 'Range'는 배열의 가능한 값 수입니다.

Pigeonhole에 대한 작업 (의사 코드) 정렬 :

1. 배열의 최소값과 최대 값을 찾습니다. 최소값과 최대 값을 각각 '최소'와 '최대'로합시다. 또한 'max-min-1'로 범위를 찾으십시오.
2. 처음에는 비어있는 "pigeonholes"의 배열을 범위와 같은 크기로 설정하십시오.
3. 배열의 각 요소를 방문한 다음 각 요소를 비둘기 구멍에 넣습니다. 요소 입력 [i]는 인덱스 입력 [i] - min의 구멍에 놓입니다.
4. 비둘기 배열 전체에 루프를 순서대로 시작하고 비어 있지 않은 구멍의 요소를 원래 배열에 다시 넣습니다.

pigeonhole 정렬은 counting 정렬과 유사하므로 여기에서는 Pigeonhole Sort와 Counting 정렬을 비교합니다.

비둘기 구멍의 예 :

우주 보조 장치 : 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;
    }
}