Counting sort (카운팅 소트)

Counting sort (카운팅 소트)


counting sort는 잘 알고 있는 merge, quick, bubble, ...
들과는 종류가 다른 radix sort와 비슷한 특수 정렬 알고리즘의
하나이다.

<제한 사항>
1. 데이터가 정수로 표현이 가능해야 한다.
(문자열도 가능은한데 hashing을 해야할듯 하다. 복잡도도 NlogN으로 증가)

2. 가장 큰 수가 곧 메모리 사용량을 결정한다.
(요것도 hashing을 하면 어느정도 해결이 될듯하다. 복잡도도 NlogN으로 증가)


<과정>
아래와 같은 정렬되지 않은 배열 A가 있다.
저 배열을 가지고 새로운 배열을 T를 만든다.
배열 A를 보면 (3이 1개), (2가 2개), (1이 3개), (0이 1개)가 있다.

즉,
T[0] = 1
T[1] = 3
T[2] = 2
T[3] = 1

다음으로
T[i] = T[i] + T[i-1]을 해준다.

T[0] = 1
T[1] = 4
T[2] = 6
T[3] = 7

이 것의 의미는 0은 첫 번재위치에 올수 있다는 의미고
1은 4번째 인덱스가 마지막 위치라는 것이다.
(0 1 1 1 2 2 7)

위의 정보를 이용하여 정렬된 새로운 배열을 만들 수 있다.
정렬되지 않은 배열 A의 앞 또는 뒤부터 하나씩 보는데
앞부터 보자면 T[A[0]] -> T[3] = 7로
새로운 배열 S[7]에 3을 넣어준다. 그리고 T[3]은 1감소 한다.

다음 A[1] = 0으로 T[A[1]] -> T[0] = 1로
새로운 배열 S[1]에 0을 넣어 준다.
이런식으로 정렬된 배열 S를 만들어 나가면 된다.