계수 정렬

계수 정렬 또는 카운팅 소트(counting sort)는 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나이다. 구별되는 키 값들을 소유하는 객체의 수를 계수하고 출력 시퀀스에 각 키 값의 위치를 결정하기 위한 해당 계수에 전위합을 적용함으로써 동작한다. 실행 시간은 항목의 수, 그리고 최대 키 값과 최소 키 값의 차이에 선형적이므로 키의 다양성이 항목의 수보다 상당히 크지 않은 상황에서 직접 사용하는 데에만 적절하다. 더 큰 키들을 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 기수 정렬의 서브루틴에 종종 사용된다.

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

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

각주

외부 링크 
 Counting Sort html5 visualization
 Demonstration applet from Cardiff University 
.

정렬 알고리즘
안정 정렬