algorithm_nth_element
algorithm_nth_element (n번째 요소 선택)
std::nth_element는 범위를 재배열해서 nth 위치의 요소가 정렬된 순서상 그 위치에 오게 해요. 완전 정렬 없이 부분적으로만 정렬해서 셀렉션(selection)에 써요.
출처: cppreference
본문
std::nth_element는 대상 범위 [first, last)의 요소를 재배열해서 nth가 가리키는 요소가 정렬된 가상 범위에서 그 위치에 오게 해요. <algorithm> 헤더에 정의되어 있어요.
template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );
template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last,
Compare comp );
- 재배열 후
[first, nth)은 정렬된 범위의 처음nth - first개 요소의 순열이에요. nth는 정렬된 범위의(nth - first)번째 요소를 가리켜요 (nth == last가 아닐 때).(nth, last)은 나머지 요소들을 지정되지 않은 순서로 담아요.
nth보다 앞의 요소들은 모두 nth의 요소 이상의(비교 기준에 따라) 순서에 있지 않고, 뒤의 요소들은 모두 그 이상이에요.
- 1번 오버로드 —
operator<(즉std::less{})를 기준으로 해요. - 2번 오버로드 — 비교 함수
comp를 기준으로 해요. - 병렬 실행 정책을 받는 오버로드도 있어요.
복잡도 (Complexity)
평균 𝓞(N) (여기서 N = std::distance(first, last)).
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end());
std::cout << "The median is " << v[v.size() / 2] << '\n';
}