04. 정렬 (Sorting Theory, c++) - Counting Sort

Counting Sort?

O(NlogN) 에 정렬하지 않으려면 배열의 요소를 비교하는 것 외에 다른 정보를 이용해야 합니다.

 

Counting Sort는 만약 배열 내의 모든 요소가 0...c 사이의 정수라면 c = O(N)에 배열을 정렬합니다.

 

Counting Sort는 bookkeeping 배열을 사용하며, 이 배열은 원본 배열의 값을 인덱스로 갖습니다.

 

원본 배열을 1회 순회하면서 이 배열에서 등장하는 빈도 수를 계산 합니다.

 

예를 들어, { 1 3 7 9 8 9 5 1 } 이라는 배열이 있을 때

이것에 대한 bookkeeping 배열은 { 2 0 1 0 1 0 1 1 2 } 입니다.

 

bookkeeping 배열 생성에는 O(N) 시간이 걸리고, 이 작업이 끝나게 되면 앞에서 부터 읽으면서 갯수 만큼 배열에 입력하는 것으로 정렬 또한 O(N)에 수행할 수 있습니다.

 

Counting Sort는 매우 효과적인 방식이지만 공간적 한계로 c가 작은 숫자일 때에만 사용할 수 있습니다.

---

아래는 N개의 배열 요소를 입력받아 Counting Sort를 수행합니다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N, c[10001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(c, 0, sizeof c);
    cin >> N;
    int x;
    REP(i, 0, N) {
        cin >> x;
        c[x]++;
    }
    REP(i, 0, 10001) {
        if (c[i] > 0) {
            REP(k, 0, c[i]) {
                cout << i << "\n";
            }
        }
    }
    return 0;
}