----------------
title : C++ 레퍼런스 - nth_element 함수 (<algorithm>)
cat_title : nth_element
ref_title : nth_element, std::nth_element
path : /C++ Reference/algorithm
publish_date : 2019-07-05
----------------

##@ cpp-ref-start

#@ nth_element

`<algorithm>` 에 정의됨

```cpp-formatted
// C++ 20 까지 (1)
template <class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);

// C++ 20 부터 (1)
template <class RandomIt>
constexpr void nth_element(RandomIt first, RandomIt nth, RandomIt last);

// C++ 17 부터 (2)
template <class ExecutionPolicy, class RandomIt>
void nth_element(ExecutionPolicy&& policy, RandomIt first, RandomIt nth,
                 RandomIt last);

// C++ 20 까지 (3)
template <class RandomIt, class Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

// C++ 20 부터 (3)
template <class RandomIt, class Compare>
constexpr void nth_element(RandomIt first, RandomIt nth, RandomIt last,
                           Compare comp);

// C++ 17 부터 (4)
template <class ExecutionPolicy, class RandomIt, class Compare>
void nth_element(ExecutionPolicy&& policy, RandomIt first, RandomIt nth,
                 RandomIt last, Compare comp);
```

`nth_element` 는 `first` 부터 `last` 전 까지의 원소들을 부분적으로 정렬합니다. 이 때, 정렬하는 방식은 다음과 같습니다.

* `nth` 가 가리키고 있는 원소는 `first` 부터 `last` 전 까지의 모든 원소들을 정렬하였을 때 자리할 원소로 바뀝니다.
* 새로운 `nth` 가 가리키고 있는 원소 앞에 오는 원소들은 `nth` 가 가리키는 원소 뒤에 오는 원소들보다 작거나 같습니다.

엄밀히 말하자면 모든 $$i \in [\text{first}, \text{n})$$ 와 $$j \in [\text{n}, \text{last})$$ 인 $$i, j$$ 에 대해서 `!(*j < * i)` (혹은 `comp(*j, *i) == false`) 를 만족하게 해줍니다.

* (1) 의 경우 `operator<` 를 통해 비교합니다.
* (3) 의 경우 이항 함수인 `comp` 를 통해 비교합니다.
* (2), (4) 의 경우 각각 (1), (3) 과 동일하지만, `ExecutionPolicy` 에 따라 연산을 수행합니다.

### 인자들

* `first, last`	: 원소들을 가리키는 반복자
* `nth`	: `n` 번째 위치를 가리키는 반복자
* `policy` : 어떠한 `ExecutionPolicy` 를 사용할 것인지
* `comp` : 두 원소를 비교할 함수 객체로 첫 번째 인자로 전달된 원소가 두 번째 인자로 전달된 원소 보다 작다면 `true` 를 리턴한다.

`comp` 함수는 아래와 같은 형태를 취해야 한다.

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

참고로 `comp` 함수는 `const&` 로 인자를 꼭 받을 필요는 없지만, 전달된 원소들을 수정하면 안된다.

### 리턴값

없음

### 시간 복잡도

`std::distance(first, last)` 에 선형으로 비례한다.

### 실행 예제

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

int main() {
  std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

  std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end());
  std::cout << "중간값은 " << v[v.size() / 2] << '\n';

  std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater<int>());
  std::cout << "두 번째로 큰 원소는 " << v[1] << '\n';
}
```

```exec
중간값은 5
두 번째로 큰 원소는 7
```

### 참고 자료

* `partial_sort_copy` : 범위 내의 원소들을 부분적으로 정렬한 뒤 복사한다.
* `stable_sort` : 안정 정렬을 수행한다.
* `sort` : 정렬을 수행한다.