O(n+k) 정렬 - 카운팅 정렬(Counting Sort)

수열의 길이가 매크로 선언된 RAN인 수열을 정렬하는 카운팅 정렬입니다.

 

시간복잡도는 O(MAX+RAN)입니다.

 

수열을 한 바퀴 순회하면서 ar[i]값에 따라서 cnt[ar[i]]를 1씩 증가시킵니다.

 

#include<iostream>
#include<cstring>
using namespace std;
 
#define MAX 500
#define RAN 10000
int ar[MAX];
int cnt[RAN];
 
void CountingSort(int size)
{
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < size; i++)
    {
        cnt[ar[i]]++;
    }
}
 
int main()
{
    int n; cin >> n;
 
    for (int j = 0; j < n; j++)
    {
        cin >> ar[j];
    }
    CountingSort(n);
    for (int i = 0; i < RAN; i++)
    {
        while (cnt[i] != 0)
        {
            cout << i << ' ';
            cnt[i]--;
        }
    }
}