비둘기집 정렬

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

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

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

같이 보기 
 비둘기집 원리
 기수 정렬

각주 

정렬 알고리즘
안정 정렬