계수 정렬
계수 정렬 또는 카운팅 소트(counting sort)는 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나이다. 구별되는 키 값들을 소유하는 객체의 수를 계수하고 출력 시퀀스에 각 키 값의 위치를 결정하기 위한 해당 계수에 전위합을 적용함으로써 동작한다. 실행 시간은 항목의 수, 그리고 최대 키 값과 최소 키 값의 차이에 선형적이므로 키의 다양성이 항목의 수보다 상당히 크지 않은 상황에서 직접 사용하는 데에만 적절하다. 더 큰 키들을 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 기수 정렬의 서브루틴에 종종 사용된다.[1][2][3]
| 분류 | 정렬 알고리즘 |
|---|---|
| 자료 구조 | 배열 |
| 최악 시간복잡도 | , where k is the range of the non-negative key values. |
| 공간복잡도 |
계수 정렬은 비교 정렬이 아니다.
의사코드 편집
의사코드(pseudocode)에서 알고리즘은 다음과 같이 나타낼 수 있다:
function CountingSort(input, k)
count ← array of k + 1 zeros
output ← array of same length as 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
각주 편집
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), 〈8.2 Counting Sort〉, 《Introduction to Algorithms》 2판, MIT Press and McGraw-Hill, 168–170쪽, ISBN 0-262-03293-7. See also the historical notes on page 181.
- ↑ Edmonds, Jeff (2008), 〈5.2 Counting Sort (a Stable Sort)〉, 《How to Think about Algorithms》, Cambridge University Press, 72–75쪽, ISBN 978-0-521-84931-9.
- ↑ Sedgewick, Robert (2003), 〈6.10 Key-Indexed Counting〉, 《Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching》 3판, Addison-Wesley, 312–314쪽.
외부 링크 편집
- Counting Sort html5 visualization
- Demonstration applet from Cardiff University 보관됨 2013-06-02 - 웨이백 머신
- Kagel, Art S. (2006년 6월 2일), 〈counting sort〉, Black, Paul E., 《Dictionary of Algorithms and Data Structures》, U.S. National Institute of Standards and Technology, 2011년 4월 21일에 확인함.