[ 알고리즘 / 정렬 ] 계수 정렬 (Counting Sort)

계수 정렬

원소의 종류가 K개, 즉 원소들의 범위가 0 ~ K-1일 때, 시간복잡도가 O(N + K)밖에 되지 않는 정렬법이다.

 

예를 들어, 원소가 1, 2, 3, 4, 5로 한정되어 있을 때 어떻게 정렬하면 좋을까?

각 원소가 몇 번 등장했는지 세면 간단하게 정렬할 수있다.

 

[ 1 , 5 , 4 , 2 , 3 , 1 , 4 ] 의 경우

1 - 2번

2 - 1번

3 - 1번

4 - 2번 

5 - 1번

등장한다.

 

그렇다면 작은 수부터 등장한 횟수만큼

[ 1 , 1 , 2 , 3 , 4 , 4 , 5 ] 로 쉽게 정렬할 수 있다.

 

가장 빠른 퀵정렬의 시간복잡도는 O(nlogn)이며 최악의 경우에는 O(N^2)이다.

그렇다면 항상 계수정렬이 더 빠른걸까?

만약 10개의 데이터 (N = 10)이고 가장 큰 수가 1000일 때를 생각해보자.

O(1000 + 10) = O(N^3)이 될 수 있기 때문에 잘 선택해야 한다.

또한, 범위를 잘 파악하고 512MB에 int 변수 1.2억개를 담을 수 있다는 점을 깜안하고 메모리 제한을 잘 고려하여 계수 정렬을 쓸지 말지 정해야 한다.

 

소스코드

[백준 15688. 수 정렬하기 5] 문제

15688번: 수 정렬하기 5

/*
 범위가 -1000000 ~ 1000000 이라서
 음수를 없애주기 위해 입력 받을 때 +1000000을 해줬다.
*/
#include <iostream>
#include <algorithm>
using namespace std;

int Count[2000001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, Max = -1;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        int Tmp;
        cin >> Tmp;
        Count[Tmp + 1'000'000]++;
        Max = max(Max, Tmp + 1'000'000);
    }
    for(int i = 0; i <= Max; i++)
    {
        for(int j = 0; j < Count[i]; j++)
        {
            cout << i-1'000'000 << '\n';
        }
    }
    return 0;
}

 

 정렬 알고리즘 시간 복잡도 비교