계수 정렬 문서 원본 보기

==개요==
{{위키데이터 속성 추적}}
{{Infobox algorithm|class=[[정렬 알고리즘]]|data=[[배열]]|time=<math>O(n+k)</math>, where k is the range of the non-negative key values.|space=<math>O(n+k)</math>}}
'''계수 정렬''' 또는 '''카운팅 소트'''(counting sort)는 [[컴퓨터 과학]]에서 [[정렬 알고리즘]]의 하나로서, 작은 양의 [[정수]]들인 키에 따라 객체를 수집하는 것, 즉 [[정수 정렬]] 알고리즘의 하나이다. 구별되는 키 값들을 소유하는 객체의 수를 계수하고 출력 시퀀스에 각 키 값의 위치를 결정하기 위한 해당 계수에 전위합을 적용함으로써 동작한다. 실행 시간은 항목의 수, 그리고 최대 키 값과 최소 키 값의 차이에 선형적이므로 키의 다양성이 항목의 수보다 상당히 크지 않은 상황에서 직접 사용하는 데에만 적절하다. 더 큰 키들을 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 [[기수 정렬]]의 서브루틴에 종종 사용된다.<ref name="clrs">{{인용
 | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen
 | last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson
 | last3 = Rivest | first3 = Ronald L. | author3-link = Ron Rivest
 | last4 = Stein | first4 = Clifford | author4-link = Clifford Stein
 | contribution = 8.2 Counting Sort
 | edition = 2nd
 | isbn = 0-262-03293-7
 | pages = 168–170
 | publisher = [[MIT Press]] and [[McGraw-Hill]]
 | title = [[Introduction to Algorithms]]
 | year = 2001}}. See also the historical notes on page 181.</ref><ref name="edmonds">{{인용|first=Jeff|last=Edmonds|contribution=5.2 Counting Sort (a Stable Sort)|pages=72–75|title=How to Think about Algorithms|publisher=Cambridge University Press|year=2008|isbn=978-0-521-84931-9}}.</ref><ref name="sedgewick">{{인용|first=Robert|last=Sedgewick|author-link=Robert Sedgewick (computer scientist)|contribution=6.10 Key-Indexed Counting|title=Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching|edition=3rd|publisher=Addison-Wesley|year=2003|pages=312–314}}.</ref>

계수 정렬은 [[비교 정렬]]이 아니다.

== 의사코드 ==
의사코드(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

== 참고 ==
* {{위키백과}}
* [http://www.cs.usfca.edu/~galles/visualization/CountingSort.html Counting Sort html5 visualization]
* [http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html Demonstration applet from Cardiff University] {{Webarchive|url=https://web.archive.org/web/20130602221151/http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html |date=2013-06-02 }}
*{{인용|first=Art S.|last=Kagel|contribution=counting sort|title=Dictionary of Algorithms and Data Structures|editor-first=Paul E.|editor-last=Black|publisher=U.S. National Institute of Standards and Technology|date=2 June 2006|url=https://xlinux.nist.gov/dads/HTML/countingsort.html|access-date=2011-04-21}}.

{{정렬 알고리즘}}

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