계수정렬(counting sort)은 정렬 알고리즘의 하나이다.
비교 기반의 정렬 알고리즘이 아니라
각 항목의 출현 횟수를 세어 정렬하는 알고르즘이다.
이 알고리즘은 정렬하고자 하는 배열의 최대값을 알아내고
최대값보다 작거나 같은 수들의 출현 횟수를 세어나가며 정렬한다.
각 항목이 몇 번 출현했는 지를 세는 작업을위해 별도의 카운트 배열을 사용한다.
계수정렬은 입력 배열의 크기와 최대값에 비례하는 시간 복잡도를 가진다.
cf)계수정렬의 시간 복잡도는 입력배열의 크기를 N,최대값을 K이라고 할 때 O(N+K)가 된다.
ex)0부터 9까지의 숫자로 이루어진 배열[2, 5, 1, 7, 2, 6, 9, 2]를 계수정렬로 정렬한다고하면
First. 카운트 배열 초기화: 0으로 초기화된 크기가 10인 카운트 배열을 만든다.
[0,0,0,0,0,0,0,0,0,0]
Second. 카운트 배열 업테이트: 입력 배열의 각 숫자에 해당하는 카운트 배열의 인덱스 값을 1씩 증가시킨다.
[0,1,1,0,0,1,1,1,0,1]
Third. 누적합 배열생성: 카운트 배열의 각 인덱스에 대해, 해당 인덱스까지의 누적합을 구해 누적 배열을 생선한다.
[0,1,2,2,2,3,4,5,5,6]
Fourth. 정렬된 배열 생성: 입력 배열의 각 숫자에 해당하는 누적합 배열의 값을 인덱스로 사용하여 정렬된 배열을 생성한다.
[1,2,2,2,5,6,7,9]
이러한 방식으로 이루어진다.
문제점으로는
분포가 고르지 않을 경우 비효율적일 수 있다는 점이 있다. 입력 배열의 값들이 특정한 범위에 몰려 있거나, 불규칙하게 분포되어 있는 경우 계수정렬이 비효율적일 수 있다는 점이다.
예시를 들어본다면,
입력배열이 [1,2,3,1000]과 같이 최대값이 큰 수가 하나만 존재하는 경우, 계수정렬의 최댓값은 1000을 카운트 배열의 크리고 사용해야 한다. 이 경우에, 1부터 999까지의 값들을 카운트 할 필요는 없지만,이 값들도 포함하여 카운트 배열을 초기화 하고 누적합 배열을 생성해야 하므로 비효율적이게 된다.
따라서 계수정렬은 입력 배열의 분포가 고르지 않을 경우에는 다른 정렬 알고르즘보다 더 느릴수 있다.
But 데이터의 범위가 작을 경우 다른 정렬 알고리즘보다 빠르게 작동할 수 있다.
