Distribution Counting(분포수 세기)

1. 같은 키가 많이 있는 배열에 한해 적용할 수 있는 정렬 알고리즘.
1. 특정 키값이 출현하는 빈도를 저장하여 누적분포를 이용하여 간단하게 정렬하는 방법.

2. 다음과 같이 키값이 1에서 5까지만의 정수값을 가지는 a[]배열.
1 3 2 2 3 1 3 2 4 2 4 3 1 2 1 2 5 1 5 3

우선 count[]라는 배열에 각 숫자별로 몇번이나 출현하였는지 카운트 하여 저장한다.
count[1] = 5
count[2] = 6
count[3] = 5
count[4] = 2
count[5] = 2

3. 이 다음의 과정은 count[] 배열의 누적돗수를 구하는 것이다.
count[1] = 5
count[2] = count[2] + count[1] = 11
count[3] = count[3] + count[2] = 16
count[4] = count[4] + count[3] = 18
count[5] = count[5] + count[4] = 20

이 누적돗수의 의미는 정렬이 완료된 상태에서 1이라는 키는 0에서 4까지 차지하며, 2라는 키는 5부터 10까지, 3이라는 키는 11부터 15까지, 4라는 키는 16부터 17까지, 5라는 키는 18부터 19까지 차지한다는 것. 즉, count[i]는 i라는 키가 위치할 곳을 가리키고 있는 것.

void dist_count(int a[], int n, int m)
{
int i;
int *b, *count;

b = new int[];
count = new int[];

for(i = 0; i <= m; i++) //count배열 초기화
count[i] = 0;

for(i = 0; i < n; i++) //빈도수 계산
count[a[i]]++;

for(i = 2; i <=m; i++) //누적 분포 계산
count[i] = count[i - 1] + count[i];

for(i = n - 1; i >= 0; i--) //뒤에서부터 읽어 b에 저장
b[--count[a[i]]] = a[i];

for(i = 0; i < n; i++) //b에서 a로 복제
a[i] = b[i];

delete b; //메모리에서 해제
delete count;
}

4. 분포수세기는 한정된 용도에서만 적합하다. 약 N번의 비교와 1번의 전체복사가 있는 정도여서 속도가 빠른 편이지만 키 값의 분포를 저장하는 count배열과 작업결과를 임시로 저장할 b배열을 생성해야 하므로 메모리의 소모가 크다. 배열의 크기가 커지면 그만큼 N이 커지므로 메모리는 더 많이 필요하게 된다.

※ 분포수세기 알고리즘은 기수 정렬 알고리즘의 기초가 된다