이번에는 정렬의 종류 중 하나인 "분포수 세기" Distribution Count에 대해서 알아보려고 한다.
일단 도수정렬 이라고 부르기도 하고, Counting Sort라고 부르기도 하고, 분포수 세기 라고 부르기도 하고, Distribution Count라고 부르기도 한다.
(도수는 거듭하는 횟수라는 뜻이다. 혹시 읽는 분들 중 모르시는 분들이 있을지도 모르니까.)
개인적으로 Counting Sort가 가장 직관적으로 이해가 잘 되긴 한다.
여튼, 분포수 세기는 아주 간단한 알고리즘으로 같은 키가 많이 있는 배열에 한해 적용할 수 있는 정렬 알고리즘으로, 특정 키값이 나오는 빈도를 저장해서 누적분포를 이용해 간단하게 정렬하는 방법이다.
분포수 세기 전략
{1, 3, 2, 2, 3, 1, 3, 2, 4, 2, 4, 3, 1, 2, 1, 2, 5, 1, 5, 3}먼저 위와 같이 키 값이 1에서 5까지로 제한된 값을 가지는 배열이 있다고 해보자.
일단은 먼저 각각 숫자가 몇번이나 나오는지 저장해야할 count 배열을 만들어야 한다.
그 다음 count배열의 1번 인덱스에는 1이라는 숫자가 몇번 나왔는지를 저장하고, 2번 인덱스에는 2번이라는 값이 몇번 나왔는지를 저장한다.
따라서 최대값이 5라면, 배열의 크기는 5 + 1인 6이 되어야 count 배열의 5번 인덱스를 사용할 수 있다.
위와같은 방법으로 각각 숫자가 몇번 나왔는지 카운팅을 해보면 아래와 같다.
count[1] = 5
count[2] = 6
count[3] = 5
count[4] = 2
count[5] = 2이 다음 과정은 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라는 키가 위치할 곳을 가리키고 있다는 의미다.
따라서! 이 count 배열을 이용해 새로운 배열 sroted에 정렬이 되어있지 않은 array배열을 정렬한 다음에 옮겨 저장할 수 있다.
우선 array배열의 값을 뒤에서부터 가져와 정확한 위치에 넣을 수 있다.
예를들어서 가장 마지막 요소인 array[19]는 3이라는 값을 갖고있다. 그러면 count[3]은 16이므로 1을뺀 15의 위치, 즉 sorted[15]에 3이라는 값을 넣은 다음 count[3]을 1개 감소시킨다.
이렇게하면 또 다음 3이라는 숫자를 만나도 정확히 빈곳을 찾아서 넣을 수 있다.
그 다음 요소인 array[18]은 5라는 값을 가지고, count[5]는 20이므로 sorted[19]에 5를 집어넣고 count[5]의 값을 하나 감소시킨다.
이런 과정을 전체 배열에 모두 동일하게 작업하면 정렬이 완료가되고, 정렬이 완료된 sorted배열을 원래 정렬되어 있지 않던 array에 그대로 복사하면 된다.
개인적으로 bubble sort보다 더 쉬운것 같다!
- count배열은 모두 0으로 초기화
- array 배열의 key의 빈도를 계산해 그 빈도를 count 배열에 저장
- count 배열을 누적분포로 변환
- array 배열을 뒤에서부터 읽어서 sorted배열에 각각 맞춰 저장
- sorted배열을 정렬되어 있지 않던 원래 배열인 array로 복사
여기서 중요한 부분은 바로 array배열 뒤에서부터 정렬을 시작한다는 부분이다.
바로 이 부분때문에 안정성이 유지가 되기 때문이다. array 배열 앞에서 부터 정렬을 하게 되면 첫번째 1이 가장 마지막 1이 있어야할 위치로 들어가기 때문이다.
Distribution Count 구현
void dist_count(int array[], int lenght, int range) {
int *count;
int *sorted;
count = (int *)malloc(sizeof(int) * range+1);
sorted = (int *)malloc(sizeof(int) * lenght);
for(int i = 0; i <= range; i++) {
count[i] = 0;
}
for(int i = 0; i < lenght; i++) {
count[array[i]]++;
}
for(int i = 2; i <= range; i++) {
count[i] += count[i-1];
}
for(int i = lenght - 1; i >= 0; i--) {
sorted[--count[array[i]]] = array[i];
}
for(int i = 0; i < lenght; i++) {
array[i] = sorted[i];
}
free(count);
free(sorted);
}코드가 길어보일지 모르지만, 자세히 살펴보면 그리 어렵지 않다.
먼저 함수 입력값으로 받는 range는 array배열의 최대값을 의미한다. 따라서 위의 예제에서는 5가된다.
분포수세기는 본격적인 정렬 알고리즘 이라고 하기에는 한정된 용도에서만 적합하다.
일단 속도가 빠른편이다, 2N번의 비교와 1번의 전체 복사 정도만 있기 때문이다.
다만 키값의 분포를 저장하는 count 배열과 또 임시로 정렬을 시킬 sorted 배열이 추가로 필요하기에 추가적인 메모리 사용이 불가피하다.
또한 N의 크기가 커지면 N크기만큼의 배열을 생성해야 하는것도 문제다.
그래서 분포수세기(카운팅 정렬)는 적당히 작은 N과 작은 범위의 키값을 가질때 유효하다고 볼 수 있다. (물론 키값은 숫자로 표현할 수 있어야 한다.)
하지만 분포수세기 알고리즘은 이후 기수 정렬에서 사용되기 대문에 눈여겨 봐둘만 하다.
