정렬 알고리즘 (Sorting Algorithms) - 비둘기집 정렬 (Pigeonhole Sort)

Pigeonhole 정렬

Pigeonhole 정렬은 특정 범위 내에 속하는 데이터를 정렬하는 데 유용한 알고리즘입니다. 주어진 데이터를 "비둘기집 원리"에 따라 분류하여 정렬합니다. 이 정렬 알고리즘은 데이터가 균일한 범위에 걸쳐 분포되어 있을 때 매우 효율적이며, 정수 기반 정렬에서 주로 사용됩니다.

---

1. 알고리즘 특징

1. 범위 기반 정렬:
   • 데이터 값의 범위(min, max)를 기준으로 "비둘기집"이라는 버킷을 생성하여 데이터를 정렬합니다.
2. 비둘기집 원리:
   • n개의 항목을 n개의 버킷에 배치하면 적어도 하나의 버킷에는 항목이 2개 이상 들어가게 된다는 수학적 원리를 기반으로 합니다.
3. 제약:
   • 데이터 범위가 작아야 효율적입니다.
   • 데이터가 정수 형태로 표현될 수 있어야 합니다.
4. 안정성:
   • 기본 구현은 안정적이지 않으나, 수정하여 안정적으로 만들 수 있습니다.

---

2. 동작 원리

단계:

1. 최소값과 최대값 찾기:
   • 배열에서 최소값(min)과 최대값(max)을 계산합니다.
2. 비둘기집 생성:
   • 범위 크기만큼의 비둘기집(버킷) 배열을 초기화합니다.
3. 데이터 분배:
   • 입력 데이터를 각각 해당하는 비둘기집 인덱스에 추가합니다.
4. 정렬된 데이터 수집:
   • 비둘기집에 저장된 데이터를 순서대로 출력합니다.

---

3. 시간 및 공간 복잡도

• 시간 복잡도:
  • O(n + r), 여기서 n은 데이터 수, r은 값의 범위 (max − min + 1)입니다.
• 공간 복잡도:
  • O(r), 값의 범위 크기만큼 추가 공간이 필요합니다.

---

4. 장단점

장점:

1. 빠른 정렬:
   • 데이터 범위가 좁을 때 매우 효율적입니다.
2. 간단한 구현:
   • 알고리즘이 직관적이고 이해하기 쉽습니다.

단점:

1. 메모리 사용량 증가:
   • 값의 범위가 클 경우 많은 메모리를 사용합니다.
2. 제약 조건:
   • 범위가 너무 넓거나 데이터가 정수 형태가 아니면 비효율적입니다.

---

5. 예제 코드

Java 구현

import java.util.ArrayList;

public class PigeonholeSort {
    public static void pigeonholeSort(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        int n = arr.length;

        // Find the minimum and maximum values
        for (int i = 1; i < n; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int range = max - min + 1; // Range of the values in the array
        ArrayList<Integer>[] pigeonholes = new ArrayList[range];

        // Initialize pigeonholes
        for (int i = 0; i < range; i++) {
            pigeonholes[i] = new ArrayList<>();
        }

        // Place elements into pigeonholes
        for (int num : arr) {
            pigeonholes[num - min].add(num);
        }

        // Collect sorted elements
        int index = 0;
        for (ArrayList<Integer> hole : pigeonholes) {
            for (int num : hole) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {8, 3, 2, 7, 4, 6, 8, 1, 9};
        System.out.println("Original Array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        pigeonholeSort(arr);

        System.out.println("\nSorted Array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

---

Python 구현

def pigeonhole_sort(arr):
    # Find minimum and maximum values
    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1

    # Create pigeonholes
    pigeonholes = [[] for _ in range(range_size)]

    # Place elements into pigeonholes
    for num in arr:
        pigeonholes[num - min_val].append(num)

    # Collect sorted elements
    sorted_arr = []
    for hole in pigeonholes:
        sorted_arr.extend(hole)

    return sorted_arr


# Example usage
if __name__ == "__main__":
    arr = [8, 3, 2, 7, 4, 6, 8, 1, 9]
    print("Original Array:", arr)

    sorted_arr = pigeonhole_sort(arr)
    print("Sorted Array:", sorted_arr)

---

6. 실행 예제

입력:

• 배열: [8, 3, 2, 7, 4, 6, 8, 1, 9]

과정:

1. 최소값 = 1, 최대값 = 9, 범위 크기 = 9.
2. 비둘기집 생성: 빈 배열 9개.
3. 각 숫자를 해당 비둘기집에 분류:
   • [1], [2], [3], [4], [6], [7], [8, 8], [9].
4. 정렬된 데이터를 순서대로 수집.

출력:

• [1, 2, 3, 4, 6, 7, 8, 8, 9]

---

7. 사용 사례

1. 점수 정렬:
   • 시험 점수와 같이 데이터 범위가 작고 정수로 표현되는 경우.
2. 카운팅 기반 분류:
   • 데이터가 고정된 범위 내에 분포된 경우 매우 효율적입니다.

Pigeonhole 정렬은 단순하면서도 범위 기반 문제를 해결하는 데 특화된 알고리즘으로, 특정 조건에서 매우 유용합니다.