algorithm_partial_sort
algorithm_partial_sort (부분 정렬)
std::partial_sort는 대상 범위의 처음 middle - first개 요소를 정렬된 상태로 [first, middle)에 배치해요. 나머지 요소는 지정되지 않은 순서로 남겨요.
출처: cppreference
본문
std::partial_sort는 대상 범위 [first, last)에서 처음 middle - first개 요소를 정렬해서 [first, middle)에 놓아요. 나머지 요소들은 [middle, last)에 지정되지 않은 순서로 배치돼요. <algorithm> 헤더에 정의되어 있어요.
template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );
template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last,
Compare comp );
- 1번 오버로드 — 요소를
operator<(즉std::less{})로 정렬해요. - 2번 오버로드 — 요소를 비교 함수
comp로 정렬해요. - 병렬 실행 정책을 받는 오버로드도 있어요.
복잡도 (Complexity)
N을 std::distance(first, last), M을 std::distance(first, middle)이라고 하면 𝓞(N·log M)번의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
출력 예:
2 3 3 6 4 6 7 9 5