partial_sort
partial_sort (부분 정렬)
범위의 처음 k개 원소만 정렬된 상태로 만들어, 나머지는 무작위로 두는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
partial_sort는 [first, middle) 구간에는 가장 작은 middle - first개 원소가 정렬된 순서로, [middle, last)에는 나머지가 오도록 재배열해요.
template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last ); // (1)
비교기 버전도 있어요.
template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp ); // (2)
- 복잡도:
(last - first)·log(middle - first)번의 비교. middle == last이면 전체 정렬과 같아요.
std::vector<int> v{9, 2, 7, 1, 5, 3, 8};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// 앞 3개가 가장 작은 3개(1,2,3)로 정렬됨
전체 정렬 없이 "가장 작은/큰 k개만 정렬된 채로 필요할 때" 써요. nth_element가 "k번째 위치만"이라면, partial_sort는 "앞 k개가 정렬된" 상태를 만들어요.