Функция nth_element

Функция nth_element из заголовочного файла algorithm переставляет элементы диапазона так, чтобы на позиции, указанной итератором nth, оказался именно тот элемент, который стоял бы на этом месте после полной сортировки. При этом все элементы перед nth будут не больше него, а все элементы после - не меньше. В первый параметр мы передаем итератор на начало диапазона, во второй - итератор на позицию n-го элемента, в третий - итератор на конец диапазона, а в четвертый (необязательный) - функцию сравнения.

Функция не гарантирует, что элементы слева и справа от nth будут отсортированы между собой - только то, что они правильно разделены относительно n-го элемента. Это делает nth_element быстрее полной сортировки: в среднем она работает за линейное время.

Синтаксис

nth_element(first, nth, last)
nth_element(first, nth, last, comp)

Пример

Давайте найдем медиану вектора, то есть элемент, который оказался бы в середине после сортировки:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> v = {5, 1, 4, 2, 3};
	nth_element(v.begin(), v.begin() + 2, v.end());
	cout << v[2] << endl;
	return 0;
}

Результат выполнения кода:

3

Пример

Давайте найдем второй по величине элемент вектора, поставив на предпоследнюю позицию нужный элемент:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> v = {1, 2, 3, 4, 5};
	nth_element(v.begin(), v.begin() + 3, v.end());
	cout << v[3] << endl;
	return 0;
}

Результат выполнения кода:

4

Пример

Давайте используем свою функцию сравнения, чтобы найти n-й элемент по убыванию:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> v = {1, 2, 3, 4, 5};
	nth_element(v.begin(), v.begin() + 1, v.end(), greater<int>());
	cout << v[1] << endl;
	return 0;
}

Результат выполнения кода:

4

Смотрите также

функция sort,
которая сортирует весь диапазон
функция partial_sort,
которая сортирует только часть диапазона
функция stable_sort,
которая устойчиво сортирует диапазон
функция is_sorted,
которая проверяет, отсортирован ли диапазон