[C++] STL nth_element 알고리즘 설명 및 예시

std::nth_element는 부분 정렬 알고리즘입니다.

구체적인 동작은 이름에서 알 수 있듯이 n번째 요소를 얻을 수 있게 해주는 녀석인데요.

무슨 기준으로 n번째냐고 하면 정렬되었을 때를 말합니다.

v = [1 3 2 4]이고 n을 0부터라고 하였을 때 n=2라고 하면 알고리즘 수행 후 v[2]는 3이 됩니다.

또한 v[:2]^[각주:1]은 v[2]보다 작거나 같은 수만 있게 되며 당연히 v[3:]^[각주:2]은 v[2]보다 작거나 큰 수만 있게 됩니다.

(cppreference의 설명으로 하자면 v[:2]는 v[3:]의 수 보다 작거나 같다입니다.)

비교 함수를 바꿔 주면 다르게 정렬된 상태에서의 n번째 요소를 얻을 수 있습니다.

대략적인 형태는

template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );

이렇게 생겨먹었으며 first와 last로 전체 구간을 정의하고 nth로 n번째를 지정하면 됩니다.

아래는 예시입니다.

https://ideone.com/K2N5Ko

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
 
int main()
{
    std::vector 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';
 
    std::nth_element(v.begin(), v.begin(), v.end(), std::greater<int>());
    std::cout << "가장 큰 값 : " << v[0] << '\n';
 
    std::nth_element(v.begin(), v.end() - 1, v.end(), std::greater<int>());
    std::cout << "가장 작은 값 : " << v[v.size() - 1] << '\n';
 
    std::nth_element(v.begin(), v.end() - 2, v.end(), std::greater<int>());
    std::cout << "두번째로 작은 값 : " << v[v.size() - 2] << '\n';
    
    return 0;
}

중앙값 : 5
두번째로 큰 값 : 7
가장 큰 값 : 9
가장 작은 값 : 2
두번째로 작은 값 : 3

참 쉽죠?

1. 0부터 1까지의 범위를 뜻하는 파이썬식 표현입니다. [본문으로]
2. 3부터 마지막까지의 범위를 뜻하는 파이썬식 표현입니다. [본문으로]