비둘기집 정렬
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
비둘기집 정렬은 정렬할 값의 키 값 범위에 해당하는 "비둘기집" 배열을 준비하여 작동하는 정렬 알고리즘이다. 각 비둘기집은 특정 키 값을 가진 요소들을 저장하며, 입력 배열의 각 요소를 해당 비둘기집에 배치한 후 비둘기집 배열을 순서대로 훑어 요소를 나열하여 정렬한다. 계수 정렬과 유사하지만, 계수 정렬은 요소의 개수만 저장하는 반면, 비둘기집 정렬은 요소 자체를 저장한다. 키 값의 범위가 넓을 경우 버킷 정렬이 더 효율적일 수 있다.
더 읽어볼만한 페이지
- 안정 정렬 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 안정 정렬 - 삽입 정렬
삽입 정렬은 미정렬 부분의 원소를 정렬된 부분의 올바른 위치에 삽입하여 정렬을 완성하는 간단하고 효율적인 알고리즘이지만, 데이터 세트가 클수록 성능이 저하되어 이를 개선하기 위한 변형 알고리즘이 존재한다. - 정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
| 비둘기집 정렬 | |
|---|---|
| 개요 | |
| 범주 | 정렬 알고리즘 |
| 자료 구조 | 배열 |
| 시간 복잡도 | , 여기서 N은 키 값들의 범위, n은 입력 크기 |
| 공간 복잡도 | |
| 최적 조건 | 인 경우 또는 해당 케이스에만 해당 |
2. 작동 원리
비둘기집 정렬은 다음과 같이 작동한다.
1. 초기 상태로 비어있는 "비둘기집" 배열을 준비한다. 개별 비둘기집은 정렬 키의 한 값에 대응한다. 각 비둘기집에는 해당 정렬 키를 가진 요소의 리스트를 저장한다.
2. 입력 배열을 순서대로 살펴보고, 각 요소를 해당 비둘기집의 리스트에 넣는다.
3. 비둘기집 배열을 순서대로 훑어보며, 비어있지 않은 비둘기집에 있는 요소를 순차적으로 나열한다.
예를 들어 다음과 같은 값의 쌍을 각각의 첫 번째 값을 키로 하여 정렬한다.
- (5, "hello")
- (3, "pie")
- (8, "apple")
- (5, "king")
키의 값은 3부터 8까지이므로, 각 값에 대해 비둘기집을 설정하고 각 요소를 비둘기집으로 이동하는 과정은 하위 섹션에서 자세히 설명되어 있다.
계수 정렬과 비슷하지만, 비둘기집 정렬은 보조 배열에 키별 요소 목록을 저장하고 계수 정렬은 횟수만 저장한다는 차이점이 있다.
''N''이 ''n''보다 훨씬 큰 경우, 더 일반적인 버킷 정렬이 더 효율적이다.
2. 1. 비둘기집 준비
정렬할 키 값의 범위를 나타내는 "비둘기집" 배열을 준비한다. 각 비둘기집은 해당 키 값을 가진 요소들을 담는 역할을 한다.[1]예를 들어, 다음과 같은 값 쌍을 첫 번째 요소를 기준으로 정렬한다고 가정해 보자.[1]
- (5, "hello")
- (3, "pie")
- (8, "apple")
- (5, "king")
키 값의 범위는 3부터 8까지이므로, 3부터 8까지의 각 값에 해당하는 비둘기집을 준비한다.[1]
2. 2. 요소 배치
입력 배열을 순회하면서 각 요소를 해당 키 값에 맞는 비둘기집에 넣는다. 예시를 통해 이 과정을 자세히 살펴보자.다음과 같은 값 쌍을 첫 번째 요소를 기준으로 정렬한다고 가정한다.
- (5, "hello")
- (3, "pie")
- (8, "apple")
- (5, "king")
먼저, 3에서 8 사이의 각 값에 대해 비둘기집을 설정한다. 그런 다음 각 요소를 해당 비둘기집으로 옮긴다.
| 비둘기집 | 내용 |
|---|---|
| 3 | (3, "pie") |
| 4 | |
| 5 | (5, "hello"), (5, "king") |
| 6 | |
| 7 | |
| 8 | (8, "apple") |
이렇게 하면 각 요소가 자신의 키 값에 맞는 비둘기집에 배치된다.
2. 3. 결과 생성
비둘기집 배열을 순서대로 훑으면서 비어 있지 않은 비둘기집의 요소들을 순서대로 나열하여 정렬된 결과를 얻는다. 예를 들어, 다음과 같은 값 쌍을 첫 번째 요소를 기준으로 정렬한다고 가정해 보자.- (5, "hello")
- (3, "pie")
- (8, "apple")
- (5, "king")
3에서 8 사이의 각 값에 대해 비둘기집을 설정한 다음 각 요소를 해당 비둘기집으로 옮긴다.
- 3: (3, "pie")
- 4:
- 5: (5, "hello"), (5, "king")
- 6:
- 7:
- 8: (8, "apple")
그런 다음 비둘기집 배열을 순서대로 반복하여 요소를 원래 목록으로 다시 이동하면 정렬된 결과를 얻을 수 있다.
계수 정렬과의 차이점은, 계수 정렬에서는 보조 배열이 입력 요소의 목록이 아닌 횟수만 포함한다는 것이다. 위 예시를 계수 정렬의 보조 배열로 나타내면 다음과 같다.
- 3: 1
- 4: 0
- 5: 2
- 6: 0
- 7: 0
- 8: 1
''N''이 ''n''보다 훨씬 큰 경우, 버킷 정렬이 공간과 시간에서 더 효율적이다.
3. 예시
다음은 값 쌍을 첫 번째 요소를 기준으로 정렬하는 예시다.
- (5, "hello")
- (3, "pie")
- (8, "apple")
- (5, "king")
3에서 8 사이의 각 값에 대해 비둘기집을 설정하고, 각 요소를 해당 비둘기집으로 옮긴다. 그런 다음 비둘기집 배열을 순서대로 반복하여 요소를 원래 목록으로 다시 이동한다.
계수 정렬과의 차이점은, 계수 정렬에서는 보조 배열에 입력 요소 목록이 아닌 횟수만 포함한다는 것이다.
| 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 0 | 0 | 1 |
''N''이 ''n''보다 훨씬 큰 경우, 버킷 정렬이 더 효율적이다.
3. 1. 비둘기집 구성
키 값의 범위가 3부터 8까지이므로, 각 값에 대한 비둘기집을 구성한다. 주어진 예시를 바탕으로 비둘기집을 구성하면 다음과 같다.[1]- 3: (3, "pie")
- 4:
- 5: (5, "hello"), (5, "king")
- 6:
- 7:
- 8: (8, "apple")
이렇게 구성된 비둘기집을 순서대로 나열하면 정렬된 결과를 얻을 수 있다. 비둘기집 정렬은 각 비둘기집에 해당 키 값을 가진 요소들을 저장하는 방식으로 동작한다.[1]
3. 2. 정렬 결과
비둘기집 배열을 순서대로 훑어 정렬된 결과를 얻으면 (3, "pie"), (5, "hello"), (5, "king"), (8, "apple")이 된다.4. 계수 정렬 및 버킷 정렬과의 비교
비둘기집 정렬은 계수 정렬과 유사하지만, 계수 정렬은 보조 배열에 요소 자체가 아닌 해당 요소의 개수만 저장한다는 차이점이 있다. 예를 들어, 다음과 같은 값 쌍을 첫 번째 요소를 기준으로 정렬한다고 가정해 보자.
- (5, "hello")
- (3, "pie")
- (8, "apple")
- (5, "king")
3에서 8 사이의 각 값에 대해 비둘기집을 설정하고 각 요소를 해당 비둘기집으로 옮기면 다음과 같다.
- 3: (3, "pie")
- 4:
- 5: (5, "hello"), (5, "king")
- 6:
- 7:
- 8: (8, "apple")
그런 다음 비둘기집 배열을 순서대로 반복하여 요소를 원래 목록으로 다시 이동한다. 반면, 계수 정렬에서는 보조 배열에 다음과 같이 횟수만 저장한다.
- 3: 1
- 4: 0
- 5: 2
- 6: 0
- 7: 0
- 8: 1
버킷 정렬은 비둘기집 정렬의 일반화된 형태로, 가능한 키 값의 범위(''N'')가 매우 클 때(''n''보다 훨씬 큰 경우) 더 효율적이다.
5. 한계
비둘기집 정렬은 키 값의 범위가 제한적이고, 정렬할 항목의 수와 거의 같을 때만 효율적이다. 키 값의 범위가 매우 크거나, 중복된 키 값이 많은 경우에는 다른 정렬 알고리즘이 더 효율적일 수 있다.
배열에서 ''N''이 ''n''보다 훨씬 큰 경우, 버킷 정렬이 공간과 시간에서 더 효율적이다.
참조
[1]
웹사이트
NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort
https://xlinux.nist.[...]
[2]
웹사이트
Dictionary of Algorithms and Data Structures
https://xlinux.nist.[...]
2015-11-06
[3]
웹사이트
NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort
http://www.nist.gov/[...]
[4]
웹인용
NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort
https://xlinux.nist.[...]
[5]
웹인용
Dictionary of Algorithms and Data Structures
https://xlinux.nist.[...]
2015-11-06
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com