Частичная сортировка с копированием (partial_sort_copy)

template <class InputIterator, class RandomAccessIterator>

RandomAccessIterator partial_sort_copy(InputIterator first,

InputIterator last, RandomAccessIterator result_first,

RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator,

class Compare>

RandomAccessIterator partial_sort_copy(InputIterator first,

InputIterator last, RandomAccessIterator result_first,

RandomAccessIterator result_last, Compare comp);

Частичная сортировка с копированием результата в другую последовательность partial_sort_copy. Итераторы задающие входную последовательность должны быть итераторами ввода (т.е. в качестве входной последовательности может быть использован список или стандартный ввод), итераторы задающие выходную последовательность должны быть итераторы произвольного доступа.

Результат работы зависит от длинны выходной последовательности (result_last - result_first), в которую будут помещены отсортированные элементы. Если она больше или равна длине входной последовательности (last – first), то в диапазоне сresult_firstдо result_first + (last – first)после завершения работы алгоритма будет находиться вся входная последовательность в отсортированном виде (то есть действие алгоритма аналогично действиюsort, только исходная последовательность остается без изменений). В противном случае в диапазон[result_first, result_last)будут помещены первые(result_last - result_first)отсортированных элементов исходной последовательности (действие аналогичноpartial_sort, только сама последовательность не меняется). Всего производится приблизительно (last - first) * log(min(last - first, result_last - result_first)) сравнений.

Функция возвращает итератор, указывающий на последний элемент отсортированной части последовательности (или result_last, илиresult_first +(last - first), какой меньше) и являющийся итератором произвольного доступа.

N-й элемент (nth_element)

template <class RandomAccessIterator>

void nth_element(RandomAccessIterator first, RandomAccessIterator nth,

RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>

void nth_element(RandomAccessIterator first, RandomAccessIterator nth,

RandomAccessIterator last, Compare comp);

После выполнения функции nth_elementэлемент в позиции, указанной итераторомnth (условно говоря, элемент последовательности с номером n), является элементом, который оказался бы в той позиции, если бы сортировался целый диапазон. Кроме этого выполняется следующее условие, для любого итератораiв диапазоне[first, nth)и любого итератораjв диапазоне[nth, last)считается, что!(*i > *j)илиcomp(*i, *j) == false. Другими словами,n-1 минимальных элементов находятся в начале последовательности в произвольном порядке,n-ый элемент содержит тот же элемент, как если бы последовательность была отсортирована с помощьюsort, остальные элементы находятся в конце последовательности в произвольном порядке. При этом любой элемент находящийся доn-ой позиции не больше любого элемента находящегося правееn-ой позиции. В среднем данная операция линейна, то есть всего будет произведено примерно(last - first) сравнений.

Пример

#include <algorithm>

#include <vector>

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

vector<int> v1;

vector<int>::iterator i;

int k;

for (k = 0; k < 20; k++)

v1.push_back(rand()%10);

for (i=v1.begin(); i!=v1.end(); ++i) cout << *i << " ";

cout << endl;

nth_element(v1.begin(),v1.begin()+5,v1.end());

for (i=v1.begin(); i!=v1.end(); ++i) cout << *i << " ";

cout << endl;

sort (v1.begin(),v1.end());

for (i=v1.begin(); i!=v1.end(); ++i) cout << *i << " ";

cout << endl;

return 0;

}

Вывод программы:

1 7 4 0 9 4 8 8 2 4 5 5 1 7 1 1 5 2 7 6

0 1 1 1 1 22 4 4 4 5 5 5 7 8 8 9 7 7 6

0 1 1 1 1 22 4 4 4 5 5 5 6 7 7 7 8 8 9

Видно, что 5-ый элемент имеет правильное значение, все элементы слева от него меньше элементов справа, элементы справа от 5-ого элемента отсортированы не полностью.