📌 nth_element
nth_element는 주어진 범위에서 n번째로 작은 원소를 해당 위치로 이동시키고
이를 기준으로 왼쪽에는 더 작은 원소들, 오른쪽에는 더 큰 원소들이 반정렬 상태로 배치되도록 만든다.
- 완전히 정렬된 상태는 아니지만, 특정 원소의 위치를 빠르게 찾아낼 때 유용하다.
- 내부적으로 퀵소트(Quick Sort)의 파티셔닝 로직과 유사한 방식으로 작동한다.
- 평균 시간 복잡도는 O(n)이다.
📍세 번째로 작은 원소 구하기
#include <iostream>
#include <vector>
#include <algorithm> // nth_element
using namespace std;
int main() {
vector<int> v = {9, 1, 4, 7, 2, 6};
// 세 번째로 작은 원소를 위치시킴
nth_element(v.begin(), v.begin() + 2, v.end());
cout << "세 번째로 작은 원소: " << v[2] << endl; // 출력: 4
return 0;
}
- v.begin() + 2는 세 번째로 작은 원소가 있어야 할 위치를 나타낸다.
- nth_element를 호출하면 배열은 다음과 같은 형태가 될 수 있다:
{1, 2, 4, (나머지 원소들)} → 왼쪽은 4보다 작고, 오른쪽은 4보다 크다.
📍짝수 중, 세 번째로 큰 원소 찾기
#include <iostream>
#include <vector>
#include <algorithm> // nth_element
using namespace std;
int main() {
vector<int> v = {15, 3, 9, 8, 5, 2, 10, 7, 6};
vector<int> temp;
// 짝수만 temp 벡터에 추가
for (int i = 0; i < v.size(); ++i) {
if (v[i] % 2 == 0) {
temp.push_back(v[i]);
}
}
// 짝수 중 세 번째로 큰 값을 찾기 위해 내림차순 정렬 기준으로 nth_element 적용
nth_element(temp.begin(), temp.begin() + 2, temp.end(), greater<int>());
cout << "짝수 중 세 번째로 큰 값: " << temp[2] << endl; // 출력: 6
return 0;
}
- 짝수만 따로 벡터 temp에 저장한다: {8, 2, 10, 6}
- greater<int>()를 사용하여 내림차순 기준으로 정렬하도록 한다.
- 세 번째로 큰 값이 temp[2] 위치에 저장되며 출력된다.
✅ nth_element의 장단점
🟢 장점
- 빠른 실행 속도: O(n)의 평균 시간 복잡도를 가지기 때문에, 특정 순위의 원소를 찾을 때 전체 정렬을 수행하는 것보다 효율적이다.
- 메모리 절약: 전체 정렬 대신 필요한 부분만 정렬하기 때문에 메모리 사용량이 적다.
🔴 단점
- 정확한 정렬이 필요한 경우 부적합: 전체 배열을 정렬하는 목적이 아니라 특정 위치의 원소만 정렬하기 때문에 완전한 정렬이 필요하면 별도의 정렬 알고리즘(sort)을 사용해야 한다.
- 최악의 경우 O(n²): 불균형한 분할이 발생할 경우 퀵소트와 마찬가지로 시간 복잡도가 최악의 경우 O(n²)까지 증가할 수 있다.
🔔 정리
- nth_element는 전체를 정렬하지 않고 특정 위치의 원소를 빠르게 찾을 때 유용하다.
- 완전한 정렬이 필요하지 않다면, 효율적으로 데이터를 처리하는 데 적합하다.
- 정렬 기준(오름차순, 내림차순)을 잘 설정하면 다양한 상황에서 활용 가능하다.