[알고리즘] Counting Sort 구현

Counting Sort는 O(n)의 시간을 가지고 있다.

매우 빠른 시간복잡도임을 알 수 있다.

 

대신 한정된 입력에서 나온다는 보장이 있어야 한다.

 

5, 2, 1, 3, 4, 2, 1, 3, 2, 4, 5, 1, 2, 4, 5 이 배열을 Sorting 하면

1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5 이렇게 된다.

 

그럼 구현은 굉장히 단순하게 할 수 있다.

그냥 1,2,3,4,5 각각의 개수를 세서 배열에 저장한 후 출력하면 된다.

 

근데 만약 1, 100 같은 경우에는 어떻게 될까?

1을 출력한 뒤, 100을 출력하려면 2~99까지의 의미없는 반복을 진행하여야 한다.

 

이런 문제점을 없앤게 바로 아래의 코드이다.

각각의 좌표를 지정한 후에, 좌표에 숫자를 꽂아넣는 방식이다.

 

소스코드 :

#include <stdio.h>

#define MAX_N 100
#define MAX_DIGIT 10

int N;  // # of data set
int arr[MAX_N];
int cnt[MAX_DIGIT];
int sortedArr[MAX_N];

void calculateDigitNumber()
{
    for (int i = 0; i < N; i++)
    {
        cnt[arr[i]]++;
    }

    for (int i = 1; i < MAX_DIGIT; i++)
    {
        cnt[i] = cnt[i-1] + cnt[i];
    }
}

void executeCountingSort()
{
    for (int i = N-1; i >= 0; i--)
    {
        sortedArr[--cnt[arr[i]]] = arr[i];
    }
}

int main(void)
{
    int T;
    scanf("%d", &T);

    for (int test_case = 1; test_case <= T; test_case++) 
    {
        scanf("%d", &N);

        for (int i = 0; i < N; i++)
        {
            scanf("%d", &arr[i]);
        }

        // initialize
        for (int i = 1; i < MAX_DIGIT; i++)
        {
            cnt[i] = 0;
        }

        calculateDigitNumber();
        executeCountingSort();

        //print the sorted digits
        printf("#%d ", test_case);
        for (int i = 0; i < N; i++) 
        {
            printf("%d ", sortedArr[i]);
        }
        printf("\n");
    }
    return 0;
}