(25) C++ algorithm헤더의 nth_element 사용법

용도 : sort()가 전체를 다 정렬시킨다면 nth_element()는 부분적으로 정렬을 시키는 함수이다.

 

1. 헤더파일

#include<algorithm>

2. 함수형태

- 시작과 끝 Iterator를 맨 왼쪽과 왼 오른쪽에 넣어주고, 가운데에 index로 어디 자리가 확정될 때까지 정렬을 진행할지 넣어줌.

void nth_element( RandomIt first, RandomIt nth, RandomIt last );

3. 사용방법

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> v(n);

    for (int i = 0; i < n; i++)
        cin >> v[i];

    // index : 0번째 자리가 확정날 때 까지만 정렬을 진행(가장 작은 값)
    nth_element(v.begin(), v.begin()+ 0, v.end());
    cout << v[0] << "\n"

    // index : 1번째 자리가 확정날 때 까지만 정렬을 진행(두번째로 작은 값)
    nth_element(v.begin(), v.begin()+ 1, v.end());
    cout << v[1] << "\n"

    // index : 중간 자리가 확정날 때 까지만 정렬을 진행(중간값)
    nth_element(v.begin(), v.begin()+ v.size()/2, v.end());
    cout << v[v.size()/2] << "\n"

    // index : 맨 끝 자리가 확정날 때 까지만 정렬을 진행(가장 큰 값)
    nth_element(v.begin(), v.end()-1, v.end());
    cout << v[v.size()-1] << "\n"

    // index : 맨 끝 자리가 확정날 때 까지만 정렬을 진행(두번째로 큰 값)
    nth_element(v.begin(), v.end()-1, v.end());
    cout << v[v.size()-2] << "\n"

}

4. 정렬을 내림차순으로 변경하는 법

- sort와 마찬가지로 맨 마지막 인자에 조건을 추가해주면 됨

nth_element(v.begin(), v.begin()+ 0, v.end(), greator<int>()); // 내림차순

nth_element(v.begin(), v.begin()+ 0, v.end(), less<int>());  // defualt로 오름차순