본문으로 바로가기

[Ex준비] C++ Radix & Counting Sort

category Algorithm/Sort 2018. 11. 9. 18:19

익스시험 볼 때마다 Radix Sort는 template을 사용하지 않고 그때 그때 필요할때마다 짜서 썼는데,

한번 구조화 해보고 싶어서 구현해봤다.


막상 시험볼때 보면 int같은 기본타입 sorting하다가

구조체 sorting하려고 하면 다시 하나 더 짜야해서 귀찮았는데,

구조화를 하니 붕어빵 찍어내듯이 쓸 수 있어서 편한거 같다.


※ 해당 코드 사용하려면 내 블로그에 올린 C++ Vector.h의 코드가 필요하다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include "Vector.h"
#include <cstdio>
using namespace std;
template <class T>
class Less{
public:
    Less() {}
    bool operator()(const T& lhs, const T& rhs) const { return lhs<rhs; }
};
template <class T>
class Greater{
public:
    Greater() {}
    bool operator()(const T& lhs, const T& rhs) const { return rhs<lhs; }
};
template <class T=intclass Cmp = Less<T> >
void sort(int MAX, Vector<T>& v, Vector<int>& idx, Vector<int>& ret) {
    Cmp cmp;
    int n = v.size();
    Vector<T> cnt; cnt.resize(MAX+1);
    for(int i=0; i<=MAX; i++) cnt[i] = 0;
    ret.clear(); ret.resize(n);
 
    for(int i=0; i<n; i++) cnt[v[i]]++;
    for(int i=1; i<=MAX; i++) cnt[i]+=cnt[i-1];
    if(cmp(0,1)) {
        for(int i=n-1; i>=0; i--) ret[--cnt[v[idx[i]]]] = i;
    } else {
        for(int i=n-1; i>=0; i--) ret[n-cnt[v[idx[i]]]--= i;
    }
}
int main() {
    freopen("input2.txt""r", stdin);
    Vector<int> v;
    int n;
    scanf("%d"&n);
    for(int i=0; i<n; i++) {
        int x; scanf("%d",&x);
        v.push_back(x);
    }
 
    Vector<int> idx, ans;
    for(int i=0; i<v.size(); i++) idx.push_back(i);
    sort(20, v, idx, ans);
    for(int i=0; i<ans.size(); i++) {
        printf("%d ", v[ans[i]]);
    }
    return 0;
}
cs


'Algorithm > Sort' 카테고리의 다른 글

Counting Sort & Radix Sort  (3) 2017.10.28

댓글을 달아 주세요