계수 정렬

-9. 계수 정렬(counting sort) ㅇㅖ시

이전에 배운 정렬 알고리즘 중 가장 빠른 알고리즘은 O(N*logN)이 나오는 퀵, 병합, 힙 정렬 중 하나를 말할텐데, 이보다 빠르게 정렬을 해야 한다면 어떻게 해야 할까?

ex. 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

위와 같이 데이터의 갯수가 30개가 있을 때의 예시를 보면 모든 데이터가 1~5 사이에 속했다는 특징이 있다. 이처럼 '범위 조건'이 있는 경우에 한해 굉장히 빠른 알고리즘[속도, 시간 복잡도가 O(N)]이 있는데 이 정렬이 계수 정렬이다. 이는 '크기를 기준으로' 세는 알고리즘이다.

이전에는 데이터들의 위치를 바꾸어가면서 정렬하는 알고리즘이었다면 계수 정렬은 크기를 기준으로 갯수만 세주면 되기 때문에 위치를 바꿀 필요가 없다. 또한 모든 데이터를 앞에서부터 한 번씩만 접근하면 된다는 점에서 무척 효율적이다.

: 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1
예시에 대한 정렬 이전의 초기 상태는 1,2,3,4,5에 대해 크기가 모두 0이다.

: 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1
1번째를 거쳐 상태는 1에 대한 크기가 1이 증가하며 나머지는 0이다.

: 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1
2번째를 거쳐 상태는 3에 대한 크기가 1이 증가해 1=1, 3=1, 나머지는 0이다.

~이후 7번째 상황까지 갔을 때~

: 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1
7번째를 거쳐 상태는 1=1, 2=2, 3=2, 4=1, 5=1 이다.

~이와 같은 방식을 반복한 결과는 다음과 같다~
크기는 1=8, 2=6, 3=8, 4=4, 5=4 이다. == 즉 1을 8번 출력, 2를 6번 출력 … 5를 4번 출력하면 정렬이 이루어짐.
정렬은 다음과 같다: 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5


자세한 설명표 

* 계수 정렬은 정렬할 데이터 자체의 크기에 매우 의존을 받는 정렬 알고리즘이다. 때문에 매우 빠르다 하더라도 자주 사용하는 케이스는 아니다.