Counting sort

$$ O(n) $$

 

입력 값의 범위가 작은 경우 유용하게 쓰이는 알고리즘

 

1. arr1 에서 각 값이 등장하는 횟수를 count

for(int i=0; i<n; i++)			// 입력 개수 n
	count[arr1[i]]++;

 

2. count 한 값을 누적합 계산

for(int i=1; i<max; i++)		// 입력 값의 최댓값 max
	count[i] += count[i-1];

 

3. arr2[누적합-1]에 arr1 값 input

for(int i=n; i>0; i++)
	arr2[--count[arr[i]]] = arr1[i]

 

arr1 : 기존 데이터

arr2 : 정렬된 데이터

 

관련 문제

BOJ 10989 수 정렬하기 3

입력 범위$$ 1  \leq n  \leq 10,000,000 $$ $$ 1 \leq num  \leq 10,000 $$

#include <stdio.h>

int main()
{
    int n, num;
    int count[10000] = {0};

    scanf("%d", &n);

    for(int i=0; i<n; i++){
        scanf("%d", &num);
        count[num-1]++;
    }
    for(int i=0; i<10000; i++){
        for(int j=0; j<count[i]; j++)
            printf("%d\n", i+1);
    }
}

 

 

관련 문제2

BOJ 1427 소트인사이드

 

숫자는 0~9 (10개)이므로 counting sort를 사용하기 적합하다고 판단

#include <stdio.h>

// counting sort

int main()
{
    int n, digit = 0;
    int count[10] = {0};
    int result[10];

    scanf("%d", &n);
    int tmp = n;

    while(tmp)
    {
        count[tmp%10]++;
        tmp /= 10;
        digit++;
    }
    for(int i=0; i<9; i++)
        count[i+1] += count[i];
    for(int i=0; i<digit; i++){
        result[--count[n%10]] = n%10;
        n /= 10;
    }
    for(int i=digit-1; i>=0; i--){
        printf("%d", result[i]);
    }
}