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_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 함수는 아래와 같은 형태를 취해야 한다.

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

참고 자료

• partial_sort_copy : 범위 내의 원소들을 부분적으로 정렬한 뒤 복사한다.

• stable_sort : 안정 정렬을 수행한다.

• sort : 정렬을 수행한다.

첫 댓글을 달아주세요!

강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요

다음으로 로그인

또는 직접 입력하세요 (댓글 수정시 비밀번호가 필요합니다)

댓글 달기

댓글을 불러오는 중입니다..