[C++ STL] '정렬 알고리즘(sort algorithm)'

'컨테이너'를 사용하면서 그 안에 든 원소들을 자신이 원하는 기준으로 정렬시키고 싶을 때가 있을텐데, 이 때 '정렬 알고리즘'을 사용하시면 됩니다. 먼저, 어떤 것들이 있는지 표로 나열해보겠습니다.

정렬 알고리즘(sort algorithm)	설명(p는 구간의 반복자)
p = partition(b, e, f)	구간 [b, e)의 원소들 중 f(*p)가 참인 원소는 [b, p)에 나열하고, 거짓인 원소는 [p, e)에 나열합니다.
stable_partition(b, e, f)	위의 함수와 같은 기능을 하고, 추가적으로 원소들을 조건에 따른 참, 거짓으로 분류할 때 기존의 순서를 유지시켜줍니다.
sort(b, e)	구간 [b, e)의 원소들을 퀵 정렬을 기준으로 정렬합니다.
sort(b, e, f)	위의 알고리즘의 조건자 버전입니다.
stable_sort(b, e)	구간 [b, e)의 원소들을 합병 정렬을 기준으로 정렬합니다. 이 때, 기존 원소들의 순서를 유지시켜줍니다.
stable_sort(b, e, f)	위의 알고리즘의 조건자 버전입니다.
make_heap(b, e)	구간 [b, e)의 순차열을 '힙 구조'로 변경합니다.
push_heap(b, e)	make_heap()을 통해 생성한 힙의 원소를 추가합니다.
pop_heap(b, e)	make_heap()을 통해 생성한 힙의 원소를 제거합니다.
sort_heap(b, e)	make_heap()을 통해 생성한 힙의 원소를 정렬합니다.

 

먼저, partition() 알고리즘을 살펴보겠습니다. 만약 내가 '컨테이너'에 든 100여개의 원소들을 50을 기준으로 50보다 큰 원소들과 작은 원소들을 분류하고 싶다면 어떻게 해야 할까요? 이때 partition() 알고리즘을 사용하시면 됩니다.

bool Pred(int n) {
    return n < 40;
}

void main() {
    vector<int> v;
    v.push_back(10); v.push_back(42); v.push_back(68);
    v.push_back(20); v.push_back(56); v.push_back(31);
    
    // 40을 기준으로 보다 작은 값과 큰 값으로 분류합니다.
    auto iter_sep = partition(v.begin(), v.end(), Pred);
    
    // 40보다 작은 값의 순차열
    for (auto iter = v.begin(); iter != iter_sep; ++iter)
        cout << *iter << " ";
    
    // 40보다 큰 값의 순차열
    for (auto iter = iter_sep; iter != v.end(); ++iter)
        cout << *iter << " ";
}

 

나머지는 사용법이 비슷하니 건너뛰고, *_heap() 류의 알고리즘을 살펴보겠습니다. make_heap() 알고리즘의 설명을 보면 순차열을 '힙 구조'로 변경한다고 하는데 이게 무슨 말일까요? 여기서 말하는 '힙 구조'란 완전 이진 트리를 기반으로 한 힙 자료구조를 말합니다. 

최대 힙

 

'힙 자료구조'는 2가지가 있습니다.

   1. 부모 노드가 자식 노드보다 큰 값을 가지는 '최대 힙'

   2. 부모 노드가 자식 노드보다 작은 값을 가지는 '최소 힙'

 

'힙 자료구조'는 최댓값과 최솟값을 탐색하는 시간이 빠른 자료구조입니다. '힙'의 시간복잡도는 아래와 같습니다. $$O(\log_{10} n)$$