모두의 코드
C++ 레퍼런스 - nth_element 함수 (<algorithm>)

작성일 : 2019-07-05 이 글은 88 번 읽혔습니다.

아직 C++ 에 친숙하지 않다면 씹어먹는 C++ 은 어때요?

nth_element

<algorithm> 에 정의됨

// 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_elementfirst 부터 last 전 까지의 원소들을 부분적으로 정렬합니다. 이 때, 정렬하는 방식은 다음과 같습니다.

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

인자들

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

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

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

리턴값

없음

시간 복잡도

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

실행 예제

#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';
}

실행 결과

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

참고 자료

첫 댓글을 달아주세요!
프로필 사진 없음
강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요