Counting Sort & Radix Sort

Counting Sort & Radix Sort

 

오랜만에 포스팅을 해보려한다.

 

해당 정렬방법은 O(N)만에 수행이 가능하다.

아마 이 정렬방법을 모르는 사람은 거의 없을거고.. counting sort도 다 짤줄 안다고 생각하겠지만,

PS를 접하지 않은 사람들은 사실 제대로 짤 줄 모르는 경우가 많다.

 

소개 순서는 다음과 같다.

 

1. int type 데이터를 Counting Sort

2. pair type 데이터를 Counting Sort

3. Radix Sort

 

 

 

 

1. Counting Sort

먼저 개념은 누구나 다 알고 있을 것이다.

이 방법으로 1,3,2,3,4를 정렬하면,

count[1]=1;

count[2]=1;

count[3]=2;

count[4]=1;

이므로 해당 개수만큼 순서대로 써주면 된다.

 

아마 대부분 아래와 같이 코딩할 것이다.

#include <cstdio>
using namespace std;
int cnt[6];
int main() {
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        int x; scanf("%d", &x);
        cnt[x]++;
    }
    for(int i=1; i<=n; i++) {
        while(cnt[i]--) printf("%d ",i);
    }
    return 0;
}
 

 

 

그런데 이런 방식으로는 stable sorting이 불가능하다.

stable sorting방식은 처음 가진 순서를 유지한 상태로 정렬을 하는 방식을 뜻한다.

같은 값을 가졌다고 해서 순서를 마음대로 배치시키는 것이 아니라 원래의 순서를 유지하는 sorting방식이다.

 

위에서와 같이 정렬하고자 하는 대상이 int 타입 하나만 있다면 stable sorting하는 것은 아무런 의미가 없겠지만,

pair(first, second)형태의 데이터인 경우는 얘기가 다르다.

이미 second기준으로 정렬이 된 상태에서 first만 가지고 비교 정렬을 할 경우,

unstable sorting과 stable sorting은 나오는 결과가 다를 수 있다.

 

참고로 C++ STL의 경우 stable sorting이 필요하면 std::stable_sort()를 쓰면 된다. 사용방법은 std::sort()함수와 같다.

(헤더도 똑같이 algorithm을 추가하면 된다.)

 

그럼 counting sort로 stable sorting을 하려면 어떻게 해야할까?

 

 

 

 

2. Counting Sort for stable sorting 

위의 질문에 대한 방법은 cnt배열 자체가 index의 의미를 갖게 하면 된다.

일단 cnt[x]++;형태로 개수를 세어주고 나서 이 값을 1부터 N까지 누적시켜주면,

cnt[x]-1은 정답(정렬된 상태)에서 x가 등장해야 할 마지막 인덱스를 가리키게 된다.

여기서 x값을 v[]라는 배열에 저장했다고 가정하면,

cnt[v[i]]-1은 정답(정렬된 상태)에서 v[i]가 등장해야 할 마지막 인덱스를 가리키게 되는 것이다.

따라서 정렬 순서를 ans[]배열에 담는다고 가정하면 다음과 같이 적을 수 있다.

ans[--cnt[v[i]] = v[i]

 

이 방법을 이용하여 pair형태를 코딩하면 다음과 같다.

#include <cstdio>
#include <vector>
#include <cassert>
using namespace std;
typedef pair<int,int> pii;
vector<pii> sort(vector<pii> &v) {
    int n=v.size();
    vector<pii> ans(n);
    vector<int> cnt(n+1,0);
    vector<int> idx(n,0);
 
    for(int i=0; i<n; i++) cnt[v[i].second]++;
    for(int i=1; i<=n; i++) cnt[i]+=cnt[i-1];
    for(int i=n-1; i>=0; i--) idx[--cnt[v[i].second]]=i;
 
    cnt.clear(); cnt.resize(n+1,0);
    for(int i=0; i<n; i++) cnt[v[i].first]++;
    for(int i=1; i<=n; i++) cnt[i]+=cnt[i-1];
    for(int i=n-1; i>=0; i--) ans[--cnt[v[idx[i]].first]]=v[idx[i]];
 
    return ans;
}
 
vector<pii> v;
int main() {
    int n; scanf("%d",&n);
    for(int i=0; i<n; i++) {
        int x,y; scanf("%d%d",&x,&y);
        assert(x>=1 && x<=n && y>=1 && y<=n); //값은 [1,n]범위로 한정한다.
        v.push_back(pii(x,y));
    }
 
    puts("\nAns: ");
    vector<pii> ans = sort(v);
    for(auto &it: ans) {
        printf("%d %d\n",it.first, it.second);
    }
    return 0;
}

 

counting sort부분은 12~19번째 줄이 전부다.

방법은 v[i].second를 기준으로 먼저 정렬한 다음 v[i].first기준으로 stable sorting을 했다.

각 줄마다 설명을 달면 다음과 같다.

 

12: cnt배열을 이용해서 v[i].second의 개수를 세준다.

13: 아까 얘기한대로 값을 누적시켜준다.

14: 이 부분부터 약간 헷갈릴 수 있는데, idx값은 second 기준으로 정렬했을 때 값이 아닌 인덱스를 저장한다.

만약 second를 기준으로만 정렬하고 말거라면, ans[--cnt[v[i].second]]=v[i].second;일 것이다.

그런데 우리는 값이 아닌 원래 정렬되기 전 상태의 인덱스가 필요하므로 ans[--cnt[v[i].second]]=i;라고 저장한 것이며,

이게 사실 답은 아니니까 ans[]배열이 아닌 idx[]배열에 저장한 것 뿐이다.

 

그럼 14번째 줄까지 하고 for(int i=0; i<n; i++) printf("%d ", idx[i]);를 실행하게 되면,

second기준으로 정렬했을 때 v[]배열의 인덱스를 순서대로 출력하는 것이다.

즉, 이 순서대로 first에 접근하면 second크기 순으로 first에 접근할 수 있으며,

다시 이전과 같은 방법으로 first를 정렬하면 second순서를 이전과 같이 최대한 유지하면서 first를 정렬할 수 있다.

((17,18,19번째 줄은 방금 위에서 다 설명함.))

 

그래서 처음 이 코드를 보고 이해가 안간다면,

카운팅 소트를 코딩할 줄 몰랐던거다.

또, 방금 얘기했던 인덱스 기준 정렬이 헷갈릴 수도 있는데,

코드를 나무처럼 뜯어보려고 하지말고 숲을 보듯이 바라보면 쉽게 이해할 수 있다.

(이해하고나면 까먹는건 불가능하다.)

 

 

 

 

3. Radix Sort

이제 Radix Sort만 남았다.

Radix Sort는 우리나라말로 기수정렬이라고도 불리는데,

사실 방금전 pair 형태를 couting sort하는 방법이 결국 radix sort와 같다.

 

radix sort는 설명만 들었을 땐, 음 그냥 그렇구나 하고 넘어갈만한 정렬이지만

이 counting sort나 radix sort에 이름이 붙은 이유는 다 활용도가 엄청나기 때문이라 말하고 싶다.

 

일단 radix sort를 짧게 설명해보겠다.

 

1234, 1324, 2132, 2211, 1141을 정렬한다고 했을 때,

1) 1의 자리 먼저 다 정렬을 한 다음 (2211, 1141, 2132, 1234, 1324)

2) 위의 순서를 최대한 유지하며 10의 자리를 정렬 (2211, 1324, 2132, 1234, 1141)

3) 다시 위의 순서를 최대한 유지하며 100의 자리를 정렬 (2132, 1141, 2211, 1234, 1324)

4) 마지막으로 위의 순서를 최대한 유지하며 1000의 자리를 정렬 (1141, 1234, 1324, 2132, 2211)

 

이 숫자들이 만약 10의자리까지만 있었으면, 아까 했었던 pair형태의 데이터를 couting sort하는 것이 결국 radix sorting인 것이다.

이 알고리즘을 학교에서 배웠을 땐

'음.. 그러쿤! 근데, 굳이 저렇게 sorting을 하면 O(NlogN) 정렬보다 딱히 성능차이도 별로 없을것 같은데?'

라는 생각이 들었다(기보다는 그냥 아무 생각이 없었다. 그 당시 내 뇌에게 조의를 표하며....

)

 

만약 값이 폐구간[1, 100만] 안에 있는 수들로 10만개의 데이터가 있다고 가정할 때, 이를 NlogN 정렬방식을 이용하면

log(100,000)이 (당연이 밑이2인 로그..) 17정도 되므로 시간복잡도는 대충 170만 정도 될 것이다.

그런데 Radix Sort를 이용하면 100만까지 자리수가 7개 이므로 계산상 70만이다.

170만 vs 70만이면 꽤 차이가 나긴 하지만,

radix sort를 제대로 이해했다면 시간복잡도를 더 줄일 수 있다.

 

이제 강력한 radix sort를 다시 한번 살펴보자.

 

값이 최대 4자리 수인 경우 radix sort는 결국 couting sort한번으로 해결한다고 생각하면 된다.

위에서는 radix sorting이라는 것을 설명하기 위해 10의 자리 단위로 쪼개서 보여줬지만, 사실 10의자리 단위로 쪼갤 필요가 없는 것이다.

다시 말하지만 위의 경우는 그냥 4자리 수를 통째로 보면서 couting sort하면 된다.

 

그럼 값이 개구간(0,10^18)까지 있는 수를 radix sort를 활용해서 풀면 어떻게 해야할까? (전체 데이터는 10만개라 하자)

 

그럼 1만진법으로 이를 해결하면 된다.

1만 단위로 묶어버리는 것이다.

위에서 개구간이라 가정했으므로 등장 할 수 있는 값의 최대값은 10^18-1이다.

이 값은 1만진법 5자리(abcde)로 표현이 가능하다.

a*(10000^4) + b*(10000^3) + c*(10000^2) + d*(10000^1) + e*(10000^0)

= a*(10^16)+b*(10^12)+c*(10^8)+d*(10^4)+e

(여기서 a,b,c,d,e,f는 0이상 10000미만인 정수)

 

이는 다르게 생각해보면 굳이 10의 x승 단위로만 쪼개는 것이 아니라 2의 x승 단위로 쪼갤 수도 있다는 뜻이 된다.

2^13이 8,192이므로 우리는 '2의 13승 진법' 형태를 써서 counting sort 5번으로 위에서 제시한 문제를 O(N)에 아주 매우 엄청나게 강력하게 풀 수 있는 것이다.

왜 굳이 2의 제곱수 형태의 진법을 써야 하냐고 묻는다면,

10의 제곱수 형태를 곱하는 것 보다 '2의 x승'은 비트로 1<<x로 표현이 가능하며

이를 어떤수 y에 곱하는 것은 결국 y<<x와 같으므로 일반 곱셈에 비해 꽤나 빠르다. (비트연산이니까...)

 

아무튼 다시 1만진법으로 돌아가서 시간복잡도를 계산해보자.

자리수 한 개를 해결할때 일단 10만(=N)개 짜리 반복문 2개와 진법 수에 해당하는 반복문 1개가 돌아간다.

1만진법으로 위의 문제를 해결했다면 자리수마다 21만번의 반복문을 돌 것이고, 5자리이므로 총 125만이란 시간복잡도로 정렬을 수행할 수 있다.

이는 170만 정도 걸리는 O(NlogN) 정렬방식과는 크게 차이가 나지 않는 것 같지만,

N이 100만인 경우 1600만 정도 걸리는 O(NlogN)정렬방식에 비해

Radix Sort 100만진법으로 잡는 경우 600만 정도면 해결이 가능하다. (수의 범위는 개구간 (0,10^18)이라 가정.)

 

한가지 더 첨언을 하자면,

이미 눈치챘겠지만 Radix Sort는 값이 들어올 수 있는 범위에 따라 진법 선정이 중요하다.

데이터의 범위가 [1,100000]인데, 진법을 100만으로 잡는 짓은 매우 멍청하다. 이는 NlogN보다 느려지는 결과를 초래한다.

또 반대로 아주 작게 10으로 잡아도 시간복잡도는 NlogN보다 느려진다.

즉, 결론은 N과 근접한 진법으로 선정하는 것이 좋다.

 

코드로 구현하면 다음과 같다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;
typedef long long ll;
int cnt[100001], idx[2][100001];
template <typename T> inline T MAX(T x, T y) { return x>y?x:y; }
 
ll tmp[100001];
void sort(vector<ll>& v) {
    ll mx=0LL;
    int n=v.size(), mask=(1<<13)-1, t=0;
    for(int i=0; i<n; i++) idx[0][i]=i, mx=MAX<ll>(mx,v[i]);
    for(int z=0; (mx>>(13*z)); z++, t^=1) {
        int shift = 13*z;
        memset(cnt,0,sizeof(cnt));
        for(int i=0; i<n; i++) cnt[(v[idx[t][i]]>>shift) & mask]++;
        for(int i=1; i<=mask; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) idx[t^1][--cnt[(v[idx[t][i]]>>shift) & mask]]=idx[t][i];
    }
    for(int i=0; i<n; i++) tmp[i]=v[idx[t][i]];
    for(int i=0; i<n; i++) v[i]=tmp[i];
}
 
vector<ll> v;
int main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n; scanf("%d",&n);
    assert(n==100000);
 
    const ll lim=1e18;
    v.clear(); v.resize(n);
    for(int i=0; i<n; i++) {
        scanf("%lld",&v[i]);
        assert(0<v[i] && v[i]<lim);
    }
    sort(v);
    for(int i=0; i<n; i++) printf("%lld\n",v[i]);
    return 0;
}

 

코드만 복잡해 보일 뿐입니다 ^^