비둘기집 정렬(Pigeonhole Sort)은 비교 기반이 아닌 정렬 기법의 대표적인 예입니다. 이 알고리즘은 정렬할 항목의 개수(n)와 가능한 키 값의 범위(N)가 거의 비슷한 경우에 효과적으로 사용됩니다.
이 정렬을 수행하려면 먼저 '구멍(홀)'을 만들어야 합니다. 필요한 구멍의 개수는 숫자의 범위에 따라 결정되며, 각 항목은 자신에 해당하는 구멍에 삽입됩니다. 마지막으로 구멍에서 요소들을 꺼내어 배열에 순서대로 저장하면 정렬이 완료됩니다.
비둘기집 정렬은 카운트 정렬(count sort)이라고도 불리며, 요소의 개수(n)와 가능한 키 값의 개수(N)가 거의 같은 리스트를 정렬하는 데 적합한 알고리즘입니다. 시간 복잡도는 O(n + N)입니다.
입력: arr[]={7,4,2,6,3,1,5}
출력: 1 2 3 4 5 6 7알고리즘 동작 원리
최솟값과 최댓값 찾기: 배열에서 최소 요소(min)와 최대 요소(max)를 각각 찾은 후, 범위(range)를 '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
정리
비둘기집 정렬은 데이터 값의 분포 범위가 좁고 요소 개수와 비슷할 때 매우 빠른 성능을 보여주는 정렬 방식입니다. 다만 값의 범위가 넓으면 그만큼 많은 메모리가 필요하므로, 데이터 특성에 따라 적절히 활용하는 것이 중요합니다.