비둘기집 정렬(Pigeonhole Sort)은 비교 연산 없이 데이터를 정렬하는 기법의 대표적인 예입니다. 정렬할 항목의 개수와 키 값의 범위가 대략 비슷할 때 특히 효율적으로 동작합니다. 이름은 '비둘기집 원리(Pigeonhole Principle)'에서 유래했으며, 각 값을 고유한 공간에 분류해 넣는 방식으로 정렬을 수행합니다.
이 정렬을 수행하려면 먼저 '구멍(hole)'이라 불리는 공간들을 만들어야 합니다. 필요한 구멍의 개수는 데이터 값의 범위에 따라 결정되며, 각 요소는 자신에게 맞는 구멍에 삽입됩니다. 마지막으로 구멍을 순서대로 순회하며 요소를 꺼내 배열에 저장하면 정렬된 결과를 얻을 수 있습니다.
비둘기집 정렬의 복잡도
- 시간 복잡도: O(n+2^k)
- 공간 복잡도: O(2^k)
입력 및 출력 예시
입력: 정렬되지 않은 목록: 802 630 20 745 52 300 612 932 78 187 출력: 정렬 전 데이터: 802 630 20 745 52 300 612 932 78 187 정렬 후 데이터: 20 52 78 187 300 612 630 745 802 932
알고리즘
pigeonHoleSort(array, size)
입력 − 데이터 배열과 배열 내 전체 요소 개수
출력 − 정렬된 배열
시작
배열에서 최댓값(max)과 최솟값(min)을 찾는다
holeRange := max − min + 1
holeRange 개수만큼 리스트(구멍)를 생성한다
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]가 비어 있지 않으면 do
array[count] := hole[j]의 첫 번째 노드를 꺼내 저장하고 삭제
count := count + 1
done
done
종료
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 pegionHoleSort(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);
pegionHoleSort(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
비둘기집 정렬의 장단점
장점
- 구현이 간단하고 직관적입니다.
- 키 범위가 좁고 데이터 개수와 비슷하면 선형 시간(O(n))에 가까운 속도를 냅니다.
- 삽입 순서를 유지하면 안정 정렬(stable sort)로 구현할 수 있습니다.
단점
- 키 값의 범위가 넓으면 구멍 수가 급증해 메모리 낭비가 커집니다.
- 정수처럼 범위를 명확히 알 수 있는 키에만 적용할 수 있습니다.
- 부동소수점 실수나 문자열 같은 일반적인 데이터에는 부적합합니다.
정리하면, 비둘기집 정렬은 데이터 개수와 키 범위가 비슷한 특수한 상황에서 매우 빠른 성능을 보이는 정렬 기법입니다. 범위가 넓은 데이터에는 계수 정렬(counting sort)이나 기수 정렬(radix sort) 같은 다른 비교 기반 외 정렬을 함께 고려하는 것이 좋습니다.