5. 카운팅 정렬 counting sort

10989. 수 정렬하기 3

https://www.acmicpc.net/problem/10989

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 

10
5
2
3
1
4
2
3
5
1
7

예제 출력 

1
1
2
2
3
3
4
5
5
7

1. 카운팅 정렬 소개

이제 소개할 카운팅 정렬은 매애우 간단하고 빠른 알고리즘이다. 간단하고 빠른 만큼 제한적이고, 메모리를 많이 소비한다.

쉬운 버블 / 삽입 정렬은 O(n ^ 2) 이었고, 병합 / 힙 정렬은 O(n * log n) 이었다.

카운팅 정렬은 O(n) 으로 선형시간이다!

카운팅 정렬은 말 그대로 숫자가 몇 번이나 나오는지 세는 알고리즘이다. 소개하기도 뭐한 매우 간단한 알고리즘인데,

필요한 배열은 숫자가 몇 번 나오는지 기록할 배열이다. 위의 문제에선 등장할 수가 10,000 보다 작거나 같은 자연수로 제한되어 있기 때문에 만칸의 배열만 준비하면 된다.

따라서 카운팅 정렬은 정렬할 원소들의 범위를 알고 있는 상황에서만 쓸 수 있다.

또한 그 범위는 메모리에 올릴 수 있을 정도여야한다.

[1, 100, 2, 1, 50] 이라면 백 칸짜리 배열이 필요하겠다.

이제 정렬한 결과를 출력하는데는 두 가지 방법이 있다.

첫째로는 걍 백 칸짜리 배열을 앞에서 부터 보면서 기록된 갯수만큼 출력하는 것이다.

인덱스 1을 보고 기록된 숫자가 2 이므로 1을 두 번 출력한다.

이 경우에 메모리 사용량은 숫자 등장 범위에 영향을 받는다.

두번째 방법으로는 백 칸짜리 기록용 배열을 누적합으로 바꿔주는 것이다.

-> 누적합[1] = 2 / 누적합[2] = 3 / ... / 누적합[50] = 4 / ... / 누적합[100] = 5

이제 기록용 배열은 해당 숫자가 정렬된 배열의 어떤 범위에 존재해야 하는지 나타낸다.

즉, 누적합[1] = 2 이므로, 배열의 앞에서 부터 두칸을 차지한다는 뜻이고,

바로 뒤의 누적합[2]는 3이니까 세번째 칸을 차지한다는 뜻이다.

누적합[3] [4] ... [49] 는 연속해서 3이므로 정렬결과용 배열에 들어가지 않는다.

또한 이 방법은 입력순서를 기억해야한다. 마지막 입력은 50 이었고 누적합[50] = 4 였으므로,

50은 정렬용 배열 네번째 칸에 들어간다. 누적합[50] = 3으로 줄어든다.

50의 전 입력은 1이었다. 누적합[1] = 2 이므로 1은 정렬용 배열 두번째 칸에 들어간다. 누적합[1] = 1로 줄어든다.

이 방법은 따라서 입력의 갯수에 비례해서 연산을 하고, 메모리도 차지한다.

두 방법중에 알맞은 방법을 쓰기로 하자.

위의 문제에선 숫자 등장범위가 10,000 이고 입력은 10,000,000 개 이니까 첫번째 방법을 쓰기로 했다.

2. 코드

#include <stdio.h>
using namespace std;
 
int n, tmp;
int count[10001];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &tmp);
        count[tmp]++;
    }
 
    for (int i = 1; i <= 10000; ++i)
        while (count[i]--)
            printf("%d\n", i);
 
    return 0;
}

3. 시간 복잡도

일단 입력이 n개 들어오므로 입력엔 O(n)이 걸린다. 출력도 결국엔 n개를 출력해야 하므로 O(n)이다.