Counting Sort

정렬 방식 중 범위가 한정되어 있을 때 유용한 Counting Sort (개수 정렬) 에 대해 정리하고자 한다.

 

일반적으로 Quick Sort, Merge Sort 등은 O(n log n) 복잡도를 갖지만, Counting Sort 는 O(n+k) 를 갖는다. 

여기서 n은 배열 크기, k는 최대값이다. 

최대값이 복잡도에 포함되는 이유는 Counting Sort 원리를 이해하면 알 수 있고, 복잡도 계산도 어렵지 않다. 

 

Counting Sort 원리는 다음과 같다. 

 

현재 배열이 다음과 같은 10개 숫자로 이루어진 상황이라면, 

1 2 5 1 3 9 7 1 2 5

 

이들의 개수를 먼저 구한다. -> 단순 카운트이므로 O(n)

1 : 3개

2 : 2개

3 : 1개

5 : 2개

7 : 1개

9 : 1개

 

이후 이 개수들의 누적합을 구한다. -> 누적합 계산 시, 중간에 빈 값이더라도 최대값까지는 반복해야 하므로 O(k)

~1 : 3개

~2 : 5개

~3 : 6개

~5 : 8개

~7 : 9개

~9 : 10개

 

위 과정이 사실 상 전부이다. 왜냐하면 누적합을 계산함으로써, 1은 3번째 숫자까지 있다, 2는 5번째 숫자까지 있다, ..., 9는 10번째 숫자까지 있다. 라는 의미이기 때문이다. 

 

이제 기존 배열을 순차적으로 탐색하며 누적합 결과를 index로 처리 후, 누적합 -1을 해주면 남은 숫자들에 대해 index 계산을 반복할 수 있다.

(-1을 함으로써 이제 남은 숫자 중 2는 4번째까지 있을 수 있다. 라는 의미)

 

원래 배열 : 1 2 5 1 3 9 7 1 2 5

1 => 누적합 배열 3이므로, 3번째에 1 => ? ? 1 ? ? ? ? ? ? ? => 누적합 배열 1 값에 -1 => 누적합 배열 ~1 : 2개

2 => 누적합 배열 5이므로, 5번째에 2 => ? ? 1 ? 2 ? ? ? ? ? => 누적합 배열 2 값에 -1 => 누적합 배열 ~2 : 4개

5 => 누적합 배열 8이므로, 8번째에 5 => ? ? 1 ? 2 ? ? 8 ? ? => 누적합 배열 5 값에 -1 => 누적합 배열 ~5 : 7개

.... 이를 반복한다. 

 

원리는 위와 같고, 원리에서 알 수 있듯이, countable한 경우에 대해서만 가능하며, 숫자 범위가 한정된 경우에서만 quick sort 등보다 빠르다. 

(ex. 숫자는 1000개인데, 숫자 범위가 -1억 ~ 1억 이라면 누적합 계산을 위해 크기 2억짜리 배열 필요 + 계산 시에도 누적합 루프 계산 2억번 수행)

 

아래는 예시 코드이며, 범위가 좁지만 실제 최대값이 큰 경우 (ex. 1억 5천 ~ 1억 6천 사이 값을 갖는다 등) 보정을 위해 원본 배열에서 최소값을 뺀을 기준으로 누적합을 계산하였다.

(누적된 개수를 기준으로 몇 번째인지를 구하는 것이 핵심이므로, 불필요하게 메모리 쓸 이유 없음)

#include <iostream>

using namespace std;

static unsigned long long seed = 12345;
static int pseudo_rand(void)
{
	seed = seed * 123456789ULL + 123ULL;
	return (seed >> 16) & 0x3fffffff;
}

// counting sort 복잡도 : O(n + k) 
// n : 배열 크기 
// k : 최대값 
// 정렬 대상 범위가 한정된 경우 + countable 할 때만 유용 

const int N = 100;
int MAX_NUM;
int maxNum;
int minNum;

int arr[N]; // 원본 배열
int sorted[N]; // 최종 정렬 결과 

int *counts = nullptr;
int *countSum = nullptr;

void init() {
    // 단순 초기화
    if(counts != nullptr) delete[] counts;
    if(countSum != nullptr) delete[] countSum;

    MAX_NUM = pseudo_rand() % 100 + 1;

    for(int i = 0; i < N; i++) {
        arr[i] = pseudo_rand() % MAX_NUM;
        int tmp = pseudo_rand();
        if(tmp & 1) arr[i] *= -1;
    }
}

void getMinMaxNum() {
    maxNum = -987654321;
    minNum = 987654321;
    for(int i = 0; i < N; i++) {
        if(arr[i] > maxNum) maxNum = arr[i];
        if(arr[i] < minNum) minNum = arr[i];
    }
}

void makeCounts() {
    // 누적합 계산 
    // 최소값 기준으로 배열 값 뺀 뒤 누적합 계산 (최대값 기준 누적합 배열 메모리 최소화 위함)
    // 2 ~ 5 까지 수를 정렬해야 하면, 0 ~ 3 까지 수를 정렬한 뒤 +2 하는 것과 동일 
    int diff = maxNum - minNum;

    counts = new int[diff + 1](); // 0 ~ diff 만큼 저장 필요, 0 초기화
    countSum = new int [diff + 1]();

    // 값 별 개수 계산
    for(int i = 0; i < N; i++) {
        int num = arr[i] - minNum;
        counts[num]++;
    }

    // 누적합 계산 
    countSum[0] = counts[0];
    for(int i = 1; i <= diff; i++) {
        countSum[i] = countSum[i-1] + counts[i];
    }
}

void countingSort() {
    // counting sort 계산 
    for(int i = 0; i < N; i++) {
        int num = arr[i] - minNum;
        int idx = countSum[num] - 1; // 개수는 1부터 시작하므로 배열 index 맞추기 위해 -1
        
        sorted[idx] = arr[i]; // 정렬 위치에 넣기
        countSum[num]--; // 누적합에서 개수 빼기 
    }
}

#include <algorithm>

int main() {
    init();
    getMinMaxNum();
    makeCounts();
    countingSort();

    // 원본 베열
    cout << "origin array \n";
    for(int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n\n";

    // 정렬된 배열 
    cout << "sorted array \n";
    for(int i = 0; i < N; i++) {
        cout << sorted[i] << " ";
    }
    cout << "\n\n";

    // 정렬 올바른지 체크용
    int tmp[N] = {0, };
    memcpy(tmp, arr, sizeof(int) * N);
    sort(tmp, tmp + N);

    bool success = true;
    for(int i = 0; i < N; i++) {
        if(tmp[i] != sorted[i]) {
            success = false;
            break;
        }
    }
    if(success) cout << "Sorting Success !!\n";
    else cout << "Sorting Fail !!\n";
}