여러 가지 정렬법 - feat. BOJ 수 정렬하기 시리즈

들어가기에 앞서..

단순히 빠른 정렬 방법이 아니라, 특정 상황에서 좋은 정렬법에 대해 설명하고자 한다. BOJ의 '수 정렬하기(시리즈)'의 문제들을 통해 여러 정렬의 방법들을 알아보고자 한다.

 

본론

2750번: 수 정렬하기는 다루지 않도록 하겠다.

먼저, 10989번: 수 정렬하기 3을 보자. 딱 봐도 Counting Sort의 냄새가 난다. 시간 복잡도는 수의 범위의 크기가 T일 때, O(T+N)이다. Counting Sort는 정렬하고자 하는 수를 배열의 index로 생각하고 배열에서 Count 한 뒤 Count 한 횟수만큼 출력하는 것으로 이루어진다. Counting Sort를 모르는 사람은 많지 않을 것으로 생각한다. 이 Counting Sort의 단점은 수의 범위가 클 때 처리하기 어렵다는 것이다. 중복되는 수가 많지만, 처리해야 할 수의 범위가 큰 경우를 생각해보자. map을 사용하면 된다. 수를 key값으로 하고, 정렬된 key 값에 따라 Counting Sort와 같은 작업을 하는 것으로 해결할 수 있다.

아래는 Counting Sort와 Map을 이용한 Sort의 코드이다.

#include <bits/stdc++.h>
using namespace std;
map<int,int>mp;
int main(){
    int N;scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int a;scanf("%d",&a);
        mp[a]++;
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        int k=it->second;
        while(k--)printf("%d\n",it->first);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int A[10003];
int main(){
    int N;scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int a;scanf("%d",&a);
        A[a]++;
    }
    for(int i=1;i<=10000;i++){
        while(A[i]){
            printf("%d\n",i);
            A[i]--;
        }
    }
    return 0;
}

2751번: 수 정렬하기 2를 보면, 수가 중복되지 않으며 수의 범위가 고작 1000000이다. 위의 두 방법 모두 적용 가능하며, 시간제한을 통과하기에 충분히 빠르게 작동한다.

 

또다시 더 특정한 상황을 고려하자. 큰 수가 있어 Counting Sort를 사용하기 힘들며, 수가 중복되지 않게 주어진다. 이런 경우 Bit Set을 이용하여 문제를 해결할 수 있다. 하지만 이러한 방식은 수가 매우 클 때 많은 연산을 요구함으로 하지 않도록 하자. 속도가 더 빠른 정렬 방법이 아니다. Counting Sort를 사용해야 하지만, 메모리 제한이 너무 심하다면 이용할 수 있다. 실제 상황에서 정렬을 해야 하지만 하드웨어 성능이 좋지 않을 경우를 가정하면 괜찮은 방법이다. 아래는 위 방법을 이용한 2751번의 코드이다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int sz=31250;
ll A[sz+3];
int main(){
    int N;scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int a;scanf("%d",&a);
        a+=1e6;
        A[a/64]|=(1LL<<(a%64));
    }
    for(int i=0;i<=2e6;i++){
        if(A[i/64]&(1LL<<(i%64)))printf("%d\n",i-(int)1e6);
    }
    return 0;
}