_

1. 소개

정렬하는 수들의 크기가 그리 크지 않고, 모두 0 이상 정수일 때 쓰는 정렬인데, 다른 정렬들과 달리 메모리가 굉장히 많이 필요하다. 그러나 수들이 작은 원소들을 정렬한다면 이보다 빠른 정렬은 없을 것이다. 시간복잡도가 무려 \(O(n+max(arr[i]))\)로, 배열값만 적당하다면 거의 선형 (= 배열의 최댓값) 시간 안에 정렬을 할 수 있기 때문이다. 정렬의 이름답게 각 원소의 개수를 배열에 저장해 둔 뒤 그 자료를 이용해 정렬을 하는 것이다.

다만 최댓값이 9백만 정도가 넘어가면 일반적인 문제에서 메모리 초과가 나게 되는 치명적인 단점이 있다.

2. 코드

void Counting_Sort(){
    int cnt[100010];
    fill(cnt, cnt+100005, 0);
    for(int i=1; i<=N; i++)cnt[arr[i]]++;
    int num=0, pv=0;
    while(num<n){
        if(!cnt[pv])pv++;
        else{
            arr[++num]=pv;
            cnt[pv]--;
        }
    }
}