[알고리즘] 계수 정렬(counting sort)

각각의 원소가 몇 개 존재하는지 counting 한 후 개수를 센 배열을 통해서 정렬된 배열을 뽑아내는 방법

제한사항

• 데이터는 양의 정수여야 함
• 데이터 범위(0 ~ K)의 제한이 있음

#define N 10
#define K 40

int data[N] = {40, 6, 1, 9, 3, 5, 5, 3, 6, 6};
int cnt[K + 2];
int ans[N];

int main(void)
{
    int i;

    for (i = 0; i < N; i++)
    {
        cnt[data[i]]++;
    }

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

    for (i = N - 1; i >= 0; i--)
    {
        ans[--cnt[data[i]]] = data[i]; // 뒤에서부터 계산하는 이유는 stable sort를 위해
    }

    for (i = 0; i < N; i++)
    {
        printf("%d ", ans[i]);
    }

    return 0;
}

• 시간복잡도 : O(N+K)
• 공간복잡도 : O(N+K)