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

계수 정렬(Counting sort)

 

#include <stdio.h>
#include <stdlib.h>

#define MAX_NUMBER 10000

int main()
{
    int maxnum =0, i = 0;
    int *arr = NULL, *sort = NULL, *cnt = NULL;

    scanf("%d", &maxnum);

    arr = (int*)calloc(maxnum, sizeof(int));
    sort = (int*)calloc(maxnum+1, sizeof(int));
    cnt = (int*)calloc(MAX_NUMBER, sizeof(int));

    //입력.
    for(i=0; i<maxnum; i++)
    {
        scanf("%d", &arr[i]);
    }

    //counting 배열.
    for(i=0; i<maxnum; i++)
    {
        cnt[arr[i]]++;
    }

    //누적합 배열.
    for(i=1; i<=maxnum; i++)
    {
        cnt[i] += cnt[i-1];
    }

    //결과 배열에 저장.
    for(i=0; i<maxnum; i++)
    {
        sort[cnt[arr[i]]] = arr[i];
        cnt[arr[i]]--;
    }

    for(i=1;  i<=maxnum; i++)
        printf("%d", sort[i]);

    free(arr);
    free(sort);
    free(cnt);

    return 0;
}