nth_element
nth_element (n번째 원소 정렬)
범위를 재배열해 nth 위치의 원소가 "정렬했을 때 그 위치에 올 원소"가 되도록 하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
nth_element는 [first, last)의 요소를 재배열해, nth가 가리키는 위치에 정렬 순서상 올 원소를 놓아요.
template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last ); // (1)
비교기 버전도 있어요.
template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp ); // (2)
nth앞에는 그보다 작거나 같은 원소들이, 뒤에는 크거나 같은 원소들이 오지만, 그 구간들 내부는 정렬되지 않아요.- 복잡도: 평균
last - first에 선형.
std::vector<int> v{9, 2, 7, 1, 5, 3, 8};
std::nth_element(v.begin(), v.begin() + 3, v.end());
// v[3]은 정렬 시 4번째(4번째로 작은) 값. 앞쪽은 모두 이보다 작음
전체를 정렬하지 않고 "k번째로 작은 원소"를 찾거나, 상위 k개만 골라낼 때 유용해요. std::sort보다 빠르게 "부분적으로만 필요한 순서"를 얻을 수 있어요.