34. Counting Sort

앞에서 설명한 정렬 기법들은 데이터끼리 서로 비교하면서 정렬을 수행하는데, 이 방법으로는 시간복잡도가 $\Theta(n\text{ lg }n)$보다 작게 할 수 없다. 하지만 데이터의 범위에 제약이 있는 경우 $\Theta(n\text{ lg }n)$보다 작은 시간복잡도로 정렬을 수행할 수 있다. 그 중 가장 대표적인 방법이 계수 정렬(카운팅 정렬, Counting Sort)이다. 계수 정렬은 각각의 원소가 등장하는 횟수를 센 뒤 앞에 나오는 원소부터 그 원소가 등장하는 횟수만큼 나열하는 것이다. 이 방법은 정렬할 원소의 범위가 크지 않을 때만 쓸 수 있다.

 

카운팅 정렬의 간단한 구현은 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
int n,a[100005],p[100005];
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        p[a[i]]++;
    }
    for(int i = 1; i <= 100000;)
    {
        if(p[i])
        {
            cout << i << ' ';
            p[i]--;
        }
        else i++;
    }
}

 

[연습문제]

 

BOJ 10989. 수 정렬하기 3 (Silver V)

백준의 카운팅 정렬 기본 문제이다.

 

CodeUp 3014. 정렬을 빠르게!

코드업의 카운팅 정렬 기본 문제이다.

 

koistudy 008F. O(n·log2·n) (NTTP) 정렬

이 문제는 입력값의 범위가 $1$억 이하이긴 한데 크기가 $1$억인 전역 배열을 선언하면 된다.

 

→ solved.ac tag: sorting