ranges::partial_sort
ranges::partial_sort (부분 정렬 — ranges)
범위의 앞부분만 정렬된 상태로 만들어주는 ranges 버전 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
std::ranges::partial_sort는 [first, middle)에 가장 작은 middle - first개가 정렬된 순서로 오도록 재배열해요.
namespace std::ranges {
template< std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I partial_sort( I first, I middle, S last,
Comp comp = {}, Proj proj = {} );
}
- 복잡도:
(last - first)·log(middle - first)번의 비교. range오버로드도 있어요.
std::vector<int> v{9, 2, 7, 1, 5, 3, 8};
std::ranges::partial_sort(v, v.begin() + 3);
// 앞 3개가 가장 작은 3개로 정렬됨
전체 정렬 없이 "앞 k개만 정렬된 채로" 얻는 ranges 버전이에요.