안녕하세요? 김백일입니다.
이 글부터는, 자주 쓰이지는 않지만 유용한 STL 알고리듬을 소개하는 글들을 몇 개 올리겠습니다.

--------------------------------------------------------------------------------------------

nth_element 알고리듬은 partial_sort 알고리듬이나 partition 알고리듬과 유사한 알고리듬으로, partition 알고리듬이 특정 조건(predicate)에 따라 나누는 반면에, nth_element 알고리듬은 N번째 위치(물론 0번째부터)에, 시퀀스가 정렬되었을 경우 놓이게 되는 원소가 놓여지도록 하고, N번째 원소의 왼쪽에 있는 모든 원소가 오른쪽에 위치한 원소들보다 모두 작거나 같도록 시퀀스를 파티션합니다.

예제 코드는 다음과 같습니다.

// Illustrating the generic nth_element algorithm

#include <iostream>
#pragma hdrstop
#include <iterator>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
  const int N = 4, MAX = 7;
  int a[MAX] = {25, 7, 9, 2, 0, 5, 21};

  // Use nth_element to place the Nth smallest
  // element in a in the Nth position, a + N:
  nth_element(a, a + N, a + MAX);

  ostream_iterator<int> out(cout, " ");
  copy_n(a, N, out);
  cout << "[" << a[N] << "] ";
  copy(a + N + 1, a + MAX, out);

  return 0;
}

출력은 다음과 같습니다.

5 0 2 7 [9] 21 25