개발/알고리즘 & 자료구조
O(n+k) 정렬 - 카운팅 정렬(Counting Sort)
수열의 길이가 매크로 선언된 RAN인 수열을 정렬하는 카운팅 정렬입니다. 시간복잡도는 O(MAX+RAN)입니다. 수열을 한 바퀴 순회하면서 ar[i]값에 따라서 cnt[ar[i]]를 1씩 증가시킵니다. #include #include 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 > n; for (int j = 0; j > ar[j]; }..