----------------
title : C++ 레퍼런스 - std::partial_sort (<algorithm>)
cat_title : partial_sort
ref_title : std::partial_sort, partial_sort
path : /C++ Reference/algorithm
publish_date : 2020-12-06
----------------

##@ cpp-ref-start

#@ partial_sort

`<algorithm>` 에 정의됨

```cpp-formatted
// 참고로 아래 두 함수는 C++ 20 부터 constexpr 함수
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)

// 위 (1), (2) 와 동일하지만 ExecutionPolicy 를 추가적으로 받을 수 있다.
template <class ExecutionPolicy, class RandomIt>
void partial_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt middle,
                  RandomIt last);

template <class ExecutionPolicy, class RandomIt, class Compare>
void partial_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt middle,
                  RandomIt last, Compare comp);
```

범위 내의 원소들을 재배치 시켜서 `first` 부터 `middle` 전 까지 범위 내의 가장 작은 원소들을 오름차순으로 배치한다. 따라서 `middle` 부터 `last` 까지에는 `first` 부터 `middle` 까지의 원소들 보다 큰 원소들이 자리하게 된다.

크기가 같은 원소들의 상대적 위치는 바뀔 수 있으며, `first` 부터 `middle` 전에 들어가지 않는 원소들의 상대적 위치 역시 바뀔 수 있다.

예를 들어서 시험 성적의 하위 100 명만 추려내고 싶다면 `partial_sort` 를 통해서 `first` 와 `middle` 을 딱 100 명만 되게 하면 된다. 이를 통해 `sort` 를 사용해서 전체 응시자를 정렬하는 것 보다 더 효율적으로 수행할 수 있다.

(1) 번 함수의 경우 `operator<` 를 사용해서 크기 비교를 수행한다.
(2) 번 함수의 경우 비교 함수인 `comp` 를 이용해서 크기 비교를 수행한다.

밑의 두 함수의 경우 추가적으로 실행 방식을 첫 번째 인자로 전달할 수 있는데, 전달하는 `policy` 의 경우 반드시 `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` 를 만족해야 한다.

### 인자들

* `first`, `last`: 정렬할 원소들의 범위를 나타낸다.
* `policy` : 사용할 실행 방식
* `comp` : 두 원소를 비교할 함수로 아래와 같은 꼴 이어야 한다.

```cpp
 bool cmp(const Type1 &a, const Type2 &b);
```

이 때 함수의 인자 타입은 반드시 `const&` 일 필요는 없으나, 함수안에선 반드시 전달받은 인자를 변경해서는 안된다. 또한 전달하는 인자들은 반드시 `Type1` 과 `Type2` 로 치환 가능해야만 한다.

### 리턴값

없음

### 시간 복잡도

전체 원소의 개수를 $$N$$ 이라 하고, `first` 와 `middle` 전 까지 원소 개수를 $$M$$ 이라고 하면, 전체 시간 복잡도는 $$N\log M$$ 이 된다.

### 구현 예시

* [libstdc++](https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1915)
* [libc++](https://github.com/llvm-mirror/libcxx/blob/a12cb9d211019d99b5875b6d8034617cbc24c2cc/include/algorithm#L5025)

### 실행 예제

```cpp-formatted
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

int main() {
  std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

  std::partial_sort(s.begin(), s.begin() + 3, s.end());
  for (int a : s) {
    std::cout << a << " ";
  }
}
```

```exec
0 1 2 7 8 6 5 9 4 3
```

### 참고 자료

* `nth_element` : 주어진 원소로 해당 범위내의 원소들을 파티션 한다.
* `stable_sort` : 범위 내의 원소들을 안정 정렬 한다.
* `sort` : 범위 내의 원소들을 오름차순으로 정렬한다.