비둘기집 정렬

비둘기집 정렬

분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	$O(N+n)$ (여기서 N은 키 값들의 범위, n은 입력 크기)
공간복잡도	$O(N+n)$

비둘기집 정렬 또는 피존홀 정렬(Pigeonhole sort)은 요소들의 수 n과 잠재적인 키 값들의 범위 길이 N이 대략적으로 동일한, 요소의 정렬 나열에 적합한 정렬 알고리즘이다. O(n + N) 시간이 요구된다. 계수 정렬과 비슷하지만 두 번 움직인다는 점에서 차이가 있다.

비둘기집 알고리즘은 다음과 같이 동작한다:

1. 초기 상태에서 빈 비둘기집 정렬의 배열을 준비한다. 각각의 비둘기집에는 정렬키의 1개의 값이 대응하고 있다. 각 비둘기집에는 정렬 키가 있는 요소 목록이 들어있다.
2. 입력 배열을 순서대로 살펴보고 각 요소를 해당 비둘기집 목록에 넣는다.
3. 비둘기집의 배열을 순서대로 스캔하고 비어있지 않은 비둘기집의 요소를 순차적으로 정렬한다.

같이 보기

• 비둘기집 원리
• 기수 정렬