О Если sortEnd совпадает с end, алгоритм partial sort() сортирует весь интервал. В среднем по сложности он уступает sort(), но в худшем случае обеспечивает более высокое быстродействие (см. сравнительный анализ алгоритмов сортировки на с. 328).

О Сложность от линейной до nxlog(n) (примерно numberOfElementsx\oQ(number-OfSortedElements) сравнений). Пример использования алгоритма partial sort():

algo/psortl.cpp #include algostuff-hpp using namespace std;

int mainO

deque<int> coll:

IN5ERT ELEMENT5(coll ,3.7) INSERT ELEMENTSCcoll.2.6) IN5ERT ELEMENTS(coll.l.5) PRiNTJLEMENTSCcoll);

Сортировка первых пяти элементов partial sort Ccoll.beginO. Начало интервала

coll.beg1nC)+5. Конец упорядоченного интервала

coll.endO); Конец всего интервала

PRiNTJLEMENTSCcoll);

Сортировка первых пяти элементов в обратном порядке partial sort Ccoll.beginC). Начало интервала

coll .beginC)+5. Конец упорядоченного интервала

coll.endO. Конец всего интервала

greater<int>C)); Критерий сортировки PRiNTJLEMENTSCcoll);

Сортировка всех элементов

partial sort (coll.beginC). Начало интервала

coll.endC). Конец упорядоченного интервала

coll.endO): Конец всего интервала

PRiNTJLEMENTSCcoll);

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

345672345612345 122337655644345 766551223344345 122333444555667

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

RandomAccessIterator

partial sort copy (Inputlterator sourceBeg. Inputlterator sourceEnd. RandomAccessIterator destBeg. RandomAccessIterator destEnd)

RandomAccessIterator

partlal sort copy (Inputlterator sourceBeg. Inputlterator sourceEnd. RandomAccessIterator destBeg, RandomAccessIterator destEnd. BinaryPredicate op)

О Обе формы являются объединениями алгоритмов сору() и partial sort().

О Обе формы копирзот элементы из интервала [sourceBegsourceErtd) в приемный интервал [destBeg,destEnd).

О Количество упорядоченных и скопированных элементов равно минимальному количеству элементов в исходном и приемном интервалах.

О Обе формы возвращают позицию за последним скопированным элементом в приемном интервале (то есть позицию первого элемента, который не был скопирован).

О Если количество элементов в приемном интервале [destBegdestEnd) больше либо равно количеству элементов в источнике [sourceBeg,sourceEnd), то алгоритм копирует и сортирует все элементы источника. В этом случае он работает как комбинация алгоритмов сору() и sort().

О Сложность от линейной до nxlog(n) (примерно nu7nberOfElementsx\Qg(number-OfSorCedElements) сравнений).

Пример использования алгоритма partiaLsort copy();

algo/psort2.cpp #include algostuff.hpp using namespace std:

int mainO

deque<int> colli:

vector<int> col 16(6); Инициализация 6 зпементаии vector<int> coll3D(30): Инициализация 30 элементами

INSERT ELEMENTS(colll.3.7; INSERT ELEMENTS(colll.2.6; INSERT ELEMENTS(colll.l.5; PRINT ELEMENTS(C0111);

Копирование упорядоченных элементов colli в col 16 vector<int>::iterator pos6;

pos6 = partial sort copy (colli.beginO. colli.end().

C0II6.beginO. coll6,end());

Вывод всех скопированных элементов copy (C0II6.beginO. pos6.

ostreamjterator<i nt>(cout. )); cout endl;

Копирование упорядоченных элементов colli в соНЗО vector<int>::iterator pos30;

pos30 = partial sort copy (colli.beginO. colli.endO.

соПЗО.beginO. coll30.end(). greater<1nt>());

Вывод всех скопированных элементов copy (соПЗО.beginO , pos3D.

ostream iterator<1nt>(cout, )); cout endl;

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

345672345612345 1 2 2 3 3 3

766555444333221

При первом вызове partial sort copy() приемник содержит только шесть элементов, поэтому алгоритм ограничивается копированием шести элементов и возвращает конец соПб. При втором вызове partial sort copyO все элементы colli копируются в соНЗО; места для них достаточно, поэтому копирование и сортировка выполняются со всеми элементами.

Разбиение по п-му элементу

void

nth element (RandomAccessIterator beg. RandomAccessIterator nth.

RandomAccessIterator end)

void

nth element (RandomAccessIterator beg. RandomAccessIterator nth.

RandomAccessIterator end. BinaryPredicate op)

О Обе формы сортируют элементы интервала lbeg,end) так, чтобы элемент в позиции nth занимал правильное место в порядке сортировки, все предшествующие элементы были меньше либо равны этому элементу, а все последующие элементы - больше или равны ему. Таким образом, алгоритм создает два подинтервала, разделенных элементом в позиции nth, при этом любой элемент первого подинтервала меньше любого элемента второго подинтервала либо равен ему. Этого может быть достаточно, если вы хотите найти п старших или младших элементов без полной сортировки всего интервала.