[Basic C++] #74_nth_element

 

#1. 개념

 

1. 정의

nth_element 알고리즘은 C++ 표준 라이브러리에서 제공하는 알고리즘으로, 주어진 범위 내에서 n번째 요소를 찾아 n번째에 위치시키고, 이 요소보다 작은 모든 요소를 해당 위치 왼쪽(앞으로), 반대로 큰 모든 요소를 해당 위치의 오른쪽(뒤쪽으로)으로 이동시키는 부분 정렬을 수행합니다. 이 알고리즘은 전체 컬렉션을 정렬하는 것보다 효율적이며, 특정 위치의 요소만 필요할 때 유용합니다.

 

2. 헤더

#include <algorithm>

 

3. sytax

// 기본 사용법
void nth_element(RandomIt first, RandomIt nth, RandomIt last);

// 사용자 정의 비교 함수를 사용하는 버전
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

 

---

 

#3. 코드

 

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

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

    // 정렬되지 않은 상태에서 4번째 요소(인덱스 3)를 찾아 해당 위치에 배치
    std::nth_element(v.begin(), v.begin() + 3, v.end());

    // v[3]은 이제 4번째로 작은 요소를 가지며, 이보다 작은 모든 요소는 왼쪽에,
    // 큰 모든 요소는 오른쪽에 위치합니다.
    std::cout << "4번째 요소: " << v[3] << '\n';

    // 벡터의 상태 출력
    for(int n : v)
        std::cout << n << ' ';
    std::cout << '\n';

    return 0;
}

 

---