[C++] STL - 정렬 알고리즘 함수 (sort, stable_sort, binary_search)

정렬 알고리즘 함수는 컨테이너의 지정된 범위의 요소들이 정렬되도록 컨테이너를 변경하는 함수이다. 모든 정렬 알고리즘 함수는 올바른 정렬을 위해 임의 접근 반복자를 사용한다. 따라서 임의 접근이 가능한 컨테이너만이 사용할 수 있다.

 

sort()

#include <algorithm>

// < 를 이용한 비교 (1)
template <class RandomIt>
void sort(RandomIt first, RandomIt last);

// 비교 함수 (comp) 를 이용한 비교 (2)
template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

first부터 last 전까지의 원소들을 오름차순으로 정렬한다. first와 last는 임의 접근 반복자여야 한다. 따라서 list의 경우 sort 함수로 정렬할 수 없다. (list의 반복자는 순차 접근 반복자이다.)

 

시간 복잡도는 평균적으로 O(NlogN) 이다.

 

stable_sort()

#include <algorithm>

template <class RandomIt>
void stable_sort(RandomIt first, RandomIt last);  // (1)

template <class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIt last, Compare comp);  // (2)

범위 내 원소들의 오름차순 안정 정렬(크기가 같은 원소들의 상대적 위치가 바뀌지 않는 것)을 수행한다.

예를 들어서 (3, a), (2, b), (2, c), (1, d)라는 데이터가 있을 때 정수값으로 안정 정렬을 수행한다면 (1, d), (2, b), (2, c), (3, a)가 되지, (1, d), (2, c), (2, b), (3, a)가 될 수 없다. 왜냐하면 이전에 (2, b)가 (2, c) 앞에 있었기 때문이다.

 

N 을 전달하는 원소의 개수를 N이라고 할 때, O(N(log N)^2) 이다. 만일 추가적인 메모리를 사용할 수 있다면 복잡도는 O(NlogN) 으로 줄어든다.

 

binary_search()

#include <algorithm>

template <class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value);  // (1)

template <class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);  // (2)

first부터 last 전까지의 범위 안에서 인자로 전달한 value가 있는지 이진 탐색을 통해서 확인해서 true 또는 false를 반환한다.

binary_search는 이진 탐색을 사용하기 때문에 함수가 제대로 작동하기 위해서는 [first, last) 범위의 원소들이 최소한 value를 기준으로 부분 정렬 되어있어야 한다.