[알고리즘/이론][BOJ 10989번]계수 정렬

계수정렬은 n개의 입력원소가 있고 각각의 원소가 0부터 k 사이에 있는 정수이며. k=O(n) 일 때 Θ(n) 시간에 수행되는 정렬이다.

계수 정렬은 각 입력 원소 x에 대해 x보다 작은 원소의 개수를 센다. 이 수는 출력 배열에서 원소 x의 위치를 정하는 데 사용된다. 예를 들어, x보다 작은 원소가 5개라면 x는 출력 배열에서 6번째 자리가 된다. 값이 같은 원소가 여러 개 있는 경우에는 모두 같은 자리에 둘 수 없으므로 방법을 약간 고쳐야 한다. 같거나 작은 원소의 개수를 구하여야 하며, 안정성을 유지하기 위해 입력 원소를 뒤에서부터 확인하여 출력배열의 적절한 위치에 넣어야 한다.

계수정렬의 코드에서는 입력 배열과 출력배열, 같거나 작은 원소의 개수를 저장하기 위한 임시 배열이 필요하다. 입력 원소를 임시 배열의 인덱스로 하여 임시 배열에 접근하여 같거나 작은 원소의 개수를 저장한다.

계수정렬의 특징은 안정성을 가진다는 것이다. 안정성은 입력 배열에서 같은 숫자가 동일한 순서로 나타나는 것을 의미한다. 보통 정렬되는 원소에 종속 데이터가 포함되어 있을 때 안정성이 강요된다.

다음은 계수정렬과 관련된 BOJ 10989번에 대한 코드이다. 8MB라는 메모리 제한으로 인해 입력, 출력 배열을 선언하지 않고, 원소가 입력되면 즉시 처리되어 임시배열의 값을 업데이트하도록 하였다.

#include<stdio.h>
 
int N;
int element;
int temp[10020];
 
int main(void) {
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &element);
        temp[element]++;
    }
 
    for (int i = 1; i <= 10000; i++) {
        for(int j=0;j<temp[i];j++)
            printf("%d\n", i);
        
    }
 
}