비둘기집 정렬은 비비교 정렬 기법의 한 예입니다. 항목의 개수와 가능한 키 값의 범위가 거의 같은 경우에 사용합니다.
이런 종류의 작업을 수행하려면 몇 가지 구멍을 만들어야 합니다. 필요한 구멍의 수는 숫자의 범위에 의해 결정됩니다. 각 구멍에는 항목이 삽입됩니다. 마지막으로 구멍에서 삭제되고 정렬된 순서를 위해 배열에 저장됩니다.
카운트 정렬이라고도 하는 비둘기 구멍 정렬은 요소 수(n)와 가능한 키 값 수(N)가 거의 동일한 요소 목록을 정렬하는 데 적합한 정렬 알고리즘입니다.[1] O(n + N) 시간이 필요합니다.
Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 설명
-
배열에서 최소 및 최대 요소를 찾습니다. 최소 및 최대 요소는 각각 '최소' 및 '최대'입니다. 그런 다음 범위를 'max-min-1'로 찾습니다.
-
범위와 동일한 크기의 "비둘기 구멍"에 대해 초기에 비어 있는 배열을 설정합니다.
-
배열의 각 요소를 탐색한 다음 각 요소를 비둘기 구멍에 넣습니다. 요소 arr[i]는 인덱스 arr[i] – min의 구멍에 놓입니다.
-
루프는 순서대로 비둘기집 배열 전체에서 시작되고 비어 있지 않은 구멍의 모든 요소를 원래 배열로 다시 넣습니다.
예시
#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