비둘기집 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox Algorithm
|class=[[정렬 알고리즘]]
|image=
|data=[[배열]]
|time=<math>O(N+n)</math> (여기서 N은 키 값들의 범위, n은 입력 크기)
|space=<math>O(N+n)</math>
|optimal=<math>N=O(n)</math>인 경우 또는 해당 케이스에만 해당하는 경우
}}
'''비둘기집 정렬''' 또는 '''피존홀 정렬'''(Pigeonhole sort)은 요소들의 수 n과 잠재적인 키 값들의 범위 길이 N이 대략적으로 동일한, 요소의 정렬 나열에 적합한 [[정렬 알고리즘]]이다.<ref>{{웹 인용| url = https://xlinux.nist.gov/dads/HTML/pigeonholeSort.html| title = NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort}}</ref> [[점근 표기법|O]](n + N) 시간이 요구된다. [[계수 정렬]]과 비슷하지만 두 번 움직인다는 점에서 차이가 있다.<ref>{{웹 인용|last1=Black|first1=Paul E.|title=Dictionary of Algorithms and Data Structures|url=https://xlinux.nist.gov/dads/HTML/pigeonholeSort.html|website=NIST|access-date=6 November 2015}}</ref>

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

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

== 같이 보기 ==
* [[비둘기집 원리]]
* [[기수 정렬]]

== 각주 ==
{{각주}}

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]
[[분류:안정 정렬]]