계수 정렬

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

계수 정렬

분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	${\displaystyle O(n+k)}$, where k is the range of the non-negative key values.
공간복잡도	${\displaystyle O(n+k)}$

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

의사코드

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