[Basic C++] #32-3_STL 정렬 알고리즘

 

[Basic C++] #32-3_STL 정렬 알고리즘

 

C++ 개발에서 표준 라이브러리(STL)에 대해 알아보겠습니다.

"전문가를 위한 C"의 15 항목, "C++ 표준 라이브러리 살펴보기"에 해당하는 내용입니다.

 

---

 

Overview

 

1. 개념
2. partition
3. sort
4. make_heap

 

#0. 개념

1. 정렬 알고리즘

• 알고리즘 공부를 한 번이라도 했다면, 모를 수 없는 정렬 알고리즘을 C++의 STL에서 제공합니다.
• 물론, STL 컨테이너에 적용하여 정렬 작업을 보다 효율적으로 진행할 수 있습니다.
• STL이 제공하는 몇 가지 정렬 알고리즘들을 살펴보겠습니다. 

 

#1. partition

1. 예제

/*
    partition(begin(), end(), f) 
    : 	[b, e) 구간의 원소들 중 f(*p)가 참인 원소는 [b, p)에 나열하며,
    	그 외 원소들은 [p, e)에 나열합니다.
        이때, p 는 partition의 기준이될 "pivot"을 의미합니다.
*/

bool Predicate(int n)
{
    return n < 50;
}

int main()
{
    vector<int> v;
    
    v.push_back(20);
    v.push_back(10);
    v.push_back(68);
    v.push_back(49);
    
    auto iter_pivot = partition(v.begin(), v.end(), Predicate);
    // 50보다 작은 원소들의 순차열
    for(auto it = v.begin(); it != iter_pivot; it++)
    	cout << *it << " ";
    // 50보다 큰 원소들의 순차열
    for(auto it = iter_pivot; it != v.end(); it++)
    	cout << *it << " ";
    
}

 

Details

 

• "partition(begin(), end(), Predicate)"은 정확하게 말해서 분할 알고리즘에 해당됩니다.
• 다만, 분할 정복 알고리즘에서 분할 과정이 필수적이므로, 짚고 넘어가는 것이 좋아 보입니다. 
• "partition" 알고리즘은 "Predicate"(일명 프레디킷) 함수가 참을 리턴하는 항목을 앞으로 보내고,
• 거짓을 리턴하는 항목을 뒤로보내는 알고리즘입니다.
• 마치 퀵정렬 알고리즘에서 "pivot"으로 선정한 항목을 기준으로 왼쪽과 오른쪽으로 정렬하는 동작과 매우 흡사합니다. 
• 이때, 기존의 항목 간 순서는 유지되지 않습니다. 유지하기 위해서 우리는 "stable_partition"을 사용해야 합니다.

 

#2. sort

1. 예제

/*
	sort(begin(), end()) : 	퀵소트, 즉 퀵정렬을 기준으로 원본에서 바로 정렬합니다.
    						이때, 기존의 항목 간 순서는 유지되지 않습니다.
*/

int main()
{
    vector<int> v;
    
    v.push_back(1);
    v.push_back(5);
    v.push_back(2);
    v.push_back(3);
    v.push_back(7);
    v.push_back(8);
    v.push_back(4);
    v.push_back(6);
    v.push_back(9);
    
    auto iter = sort(v.begin(), v.end());
    
    for(auto it = v.begin(); it != v.end(); it++)
    	cout << *it << " ";
        
    // 결과 : 1 2 3 4 5 6 7 8 9
}

 

Details

 

• "sort" 알고리즘은 "퀵 정렬"을 기준으로 원본에서 바로 정렬을 수행합니다.
• 이때, 원본의 항목 간 순서는 유지되지 않습니다. 이를 원치 않을 경우, "stable_sort"를 사용합니다.

 

#2. make_heap

1. 예제

/*
    make_heap(begin(), end(), greater<>(T typename) or less<T typename>)
    :	주어진 범위의 항목들을 이용하여 힙을 구성합니다.
    	기본적으로 최대 힙을 구성하며, greater<>() 혹은 less<>()를 통해 최소 힙으로 구성 가능합니다.
*/

int main()
{
    vector<int> v;
    
    v.push_back(1);
    v.push_back(5);
    v.push_back(6);
    v.push_back(2);
    v.push_back(3);
    // 최대 힙 구성
    make_heap(v.begin(), v.end(), greater<int>());
}

 

Details

 

• "make_heap"을 통해 우리는 기존의 항목들을 이용하여 힙을 구성할 수 있습니다.
• 기본적으로 최대 힙(부모 노드가 자식 노드보다 크다)을 구성합니다.
• 함수 포인터를 통해 최소 힙을 구성하는 것도 가능합니다!