계수 정렬
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
계수 정렬은 각 항목의 키가 특정 범위 내의 정수인 항목들을 정렬하는 알고리즘이다. 이 알고리즘은 입력 컬렉션의 각 키가 나타나는 횟수를 세는 방식으로 작동하며, 시간 복잡도는 O(n + k)이다. 계수 정렬은 안정 정렬이며, 기수 정렬의 서브루틴으로 사용될 수 있다. 제자리 정렬은 아니지만, 변형을 통해 병렬화하거나 중복 키를 제거하는 데 사용할 수 있다. 계수 정렬은 1954년 해럴드 H. 시워드에 의해 발명되었다.
더 읽어볼만한 페이지
- 안정 정렬 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 안정 정렬 - 삽입 정렬
삽입 정렬은 미정렬 부분의 원소를 정렬된 부분의 올바른 위치에 삽입하여 정렬을 완성하는 간단하고 효율적인 알고리즘이지만, 데이터 세트가 클수록 성능이 저하되어 이를 개선하기 위한 변형 알고리즘이 존재한다. - 정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다. - 정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
| 계수 정렬 | |
|---|---|
| 알고리즘 정보 | |
| 종류 | 정렬 알고리즘 |
| 자료 구조 | 배열 |
| 시간 복잡도 | O(n+k), 여기서 k는 음수가 아닌 키 값의 범위이다. |
| 공간 복잡도 | O(n+k) |
| 수학적 특징 | |
| 최악 성능 | O(n+k) |
| 평균 성능 | O(n+k) |
| 최선 성능 | O(n+k) |
2. 가정
계수 정렬은 일반적인 경우, 최대값이 이하인 음이 아닌 정수 키를 각각 갖는 개의 항목 컬렉션을 입력으로 받는다.[3] 정렬할 입력이 단순히 정수의 시퀀스 자체라고 가정하기도 하지만,[1] 이는 기수 정렬의 서브루틴으로 사용되는 경우와 같이 계수 정렬의 모든 응용 분야를 포함하지는 못한다.
2. 1. 입력과 출력
계수 정렬의 가장 일반적인 입력은 최대값이 이하인 음이 아닌 정수 키를 각각 갖는 개의 항목 컬렉션으로 구성된다.[3] 일부 설명에서는 정렬할 입력이 단순히 정수의 시퀀스 자체라고 가정하지만,[1] 이러한 단순화는 기수 정렬의 서브루틴으로 사용되는 경우와 같이 계수 정렬의 많은 응용 분야를 수용하지 못한다. 예를 들어, 기수 정렬에서 계수 정렬에 대한 각 호출의 키는 더 큰 항목 키의 개별 숫자이므로, 항목과 분리된 키 숫자의 정렬된 목록만 반환하는 것으로는 충분하지 않다.기수 정렬과 같은 응용 분야에서는 최대 키 값 에 대한 경계를 미리 알고 있으며, 알고리즘 입력의 일부라고 가정할 수 있다. 그러나 값을 알 수 없는 경우, 최대 키 값을 결정하기 위해 데이터를 한 번 더 살펴보는 첫 번째 단계를 통해 계산할 수 있다.
출력은 키로 정렬된 요소의 배열이다. 기수 정렬에 적용하기 위해 계수 정렬은 안정 정렬이어야 한다. 즉, 두 요소가 동일한 키를 공유하는 경우 출력 배열에서의 상대적 순서는 입력 배열에서의 상대적 순서와 일치해야 한다.[1][2]
3. 의사코드
다음은 계수 정렬 알고리즘의 의사코드이다.[1][2][3]
'''함수''' 계수 정렬(''input'', ''k'')
:count ← 크기가 ''k'' + 1이고 모든 원소가 0인 배열
:output ← input과 길이가 같은 배열
:'''for''' ''i'' = 0 '''to''' length(input) - 1 '''do'''
::''j'' = key(input[''i''])
::count[''j''] += 1
:'''for''' ''i'' = 1 '''to''' ''k'' '''do'''
::count[''i''] += count[''i'' - 1]
:'''for''' ''i'' = length(input) - 1 '''downto''' 0 '''do'''
::''j'' = key(input[''i''])
::count[''j''] -= 1
::output[count[''j'']] = input[''i'']
:'''return''' output
여기서 `input`은 정렬할 입력 배열, `key`는 입력 배열의 각 항목의 숫자 키를 반환하는 함수, `count`는 보조 배열이다. `count`는 처음에는 각 키를 가진 항목의 수를 저장하고, 두 번째 루프 이후에는 각 키를 가진 항목이 배치되어야 하는 위치를 저장한다. `k`는 음수가 아닌 키 값의 최대값, `output`은 정렬된 출력 배열이다.
알고리즘의 작동 방식은 다음과 같다.
1. 첫 번째 루프에서 입력 항목을 반복하며 각 키가 나타나는 횟수에 대한 히스토그램을 `count` 배열에 계산한다.
2. 두 번째 루프에서 `count` 배열에 누적 합을 계산한다. `count[i]`는 키 `i`를 가진 항목이 배치되어야 하는 시작 위치를 나타낸다.
3. 세 번째 루프에서 입력 항목을 역순으로 반복하며 각 항목을 `output` 배열의 정렬된 위치로 이동한다.
이 정렬은 동일한 키를 가진 항목의 상대적인 순서가 유지되므로 안정 정렬이다.
4. 복잡도 분석
알고리즘은 재귀나 서브루틴 호출 없이 간단한 `for` 루프만 사용하기 때문에 분석이 간단하다. 카운트 배열의 초기화와 카운트 배열에 대한 누적 합을 수행하는 두 번째 for 루프는 각각 최대 ''k'' + 1번 반복되므로 시간이 걸린다. 다른 두 개의 for 루프와 출력 배열의 초기화는 각각 시간이 걸린다. 따라서 전체 알고리즘의 시간은 이러한 단계의 시간의 합인 이다.[1][2]
길이 및 의 배열을 사용하기 때문에 알고리즘의 총 공간 사용량도 이다.[1] 최대 키 값이 항목 수보다 훨씬 작은 문제의 경우, 계수 정렬은 매우 공간 효율적일 수 있으며, 입력 및 출력 배열 외에 사용하는 유일한 저장 공간은 공간을 사용하는 Count 배열이다.[4]
5. 변형 알고리즘
각 정렬 항목 자체가 정수이고 키로 사용되는 경우, 계수 정렬의 두 번째 및 세 번째 루프를 결합할 수 있다. 두 번째 루프에서 키 `i`를 가진 항목이 출력에 배치되어야 하는 위치를 계산하는 대신, 단순히 숫자 `i`의 `Count[i]` 사본을 출력에 추가한다.
이 알고리즘은 중복 키를 제거하는 데에도 사용할 수 있다. `Count` 배열을 입력에 있는 키에 대해 `1`을, 그렇지 않은 키에 대해 `0`을 저장하는 비트 벡터로 대체함으로써 가능하다. 또한 항목 자체가 정수 키인 경우, 두 번째 및 세 번째 루프를 완전히 생략할 수 있으며 비트 벡터 자체가 출력 역할을 하며, 값은 `0`이 아닌 항목의 오프셋으로 표현되고, 범위의 최솟값에 더해진다. 따라서 이 변형에서 키는 비트 배열에 배치되기만 함으로써 정렬되고 중복이 제거된다.
최대 키 크기가 데이터 항목 수보다 훨씬 작은 데이터의 경우, 계수 정렬은 입력을 대략 같은 크기의 하위 배열로 분할하고, 각 하위 배열을 병렬로 처리하여 각 하위 배열에 대한 별도의 계수 배열을 생성한 다음, 계수 배열을 병합함으로써 병렬 알고리즘으로 병렬화될 수 있다. 병렬 기수 정렬 알고리즘의 일부로 사용될 때, 키 크기(기수 표현의 밑)는 분할된 하위 배열의 크기와 일치하도록 선택해야 한다.[5] 계수 정렬 알고리즘의 단순함과 쉽게 병렬화 가능한 접두사 합산 기본 요소의 사용은 더 세분화된 병렬 알고리즘에서도 사용할 수 있게 한다.[6]
설명된 대로 계수 정렬은 제자리 정렬 알고리즘이 아니다. 계수 배열을 제외하더라도, 별도의 입력 및 출력 배열이 필요하다. 알고리즘을 수정하여 계수 배열만을 보조 저장소로 사용하여, 입력으로 제공된 동일한 배열 내에서 항목을 정렬된 순서로 배치할 수 있다. 그러나 계수 정렬의 수정된 제자리 버전은 안정적이지 않다.[3]
6. 제자리 정렬 (In-place Sorting)
설명된 대로 계수 정렬은 제자리 정렬 알고리즘이 아니다. 계수 배열은 별도로 하고라도, 별도의 입력 및 출력 배열이 필요하다. 알고리즘을 수정하여 계수 배열만을 보조 저장소로 사용해서, 입력으로 제공된 동일한 배열 내에서 항목을 정렬된 순서로 배치할 수 있다. 그러나 계수 정렬의 수정된 제자리 버전은 안정적이지 않다.[3]
7. 역사
계수 정렬과 이를 기수 정렬에 적용하는 것은 모두 1954년 해럴드 H. 시워드가 발명하였다.[1][7][8]
참조
[1]
서적
Introduction to Algorithms
MIT Press and McGraw-Hill
[2]
서적
How to Think about Algorithms
Cambridge University Press
[3]
서적
Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching
Addison-Wesley
[4]
간행물
Proceedings of the 18th annual Southeast Regional Conference
ACM
[5]
간행물
Proceedings of Supercomputing '91, November 18-22, 1991, Albuquerque, NM, USA
https://www.cs.cmu.e[...]
IEEE Computer Society / ACM
[6]
간행물
Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985)
[7]
서적
The Art of Computer Programming, Volume 3: Sorting and Searching
Addison-Wesley
[8]
간행물
Information sorting in the application of electronic digital computers to business operations
http://bitsavers.org[...]
Massachusetts Institute of Technology, Digital Computer Laboratory
[9]
서적
Introduction to Algorithms
MIT Press and McGraw-Hill
[10]
서적
How to Think about Algorithms
Cambridge University Press
[11]
서적
Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching
Addison-Wesley
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com