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

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 finclude "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<1nt>::iterator pos6:

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

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<int>());

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

ostream iterator<int>(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, при этом любой элемент первого подинтервала меньше любого элемента второго подинтервала либо равен ему. Этого может быть достаточно, если вы хотите найти п старших или младших элементов без полной сортировки всего интервала.

о Первая форма сортирует элементы оператором <.

О Вторая форма сортирует элементы по критерию ор{е1ет1 ,elem2).

О Предиьсат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь на с. 303.

О Алгоритм partitionO (см. с. 387) тоже разбивает элементы интервала на две части по заданному критерию сортировки. Отличия между partitionO и nth element() описаны на с. 330,

О Сложность в среднем линейная.

Пример использования алгоритма nth element:

algo/nthl.cpp linclude "algostuff.hpp" using namespace std;

int mainO (

deque<int> coll;

INSERT aEMENTS(coll.3.7) INSERT ELEMENTS(coll.2.6) INSERT ELEMENTS(coll.l.5) PRINTJLEMENTSCcoll);

Выделение четырех наименьших элементов nth element (coll.beginO. Начало интервала

coll .beginO+3. Граничный элемент

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

Вывод

cout « "the four lowest elements are: "; copy (coll.beginO. col 1 .begin()+4.

ostreamjterator<1nt>(cout." ")): cout « endl:

Выделение четырех наибольших элементов nth element (coll.beginO. Начало интервала

coll.end()-4. Граничный элемент

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

Вывод

cout « "the four highest elements are; "; copy (coll .end()-4. coll.endO.

ostreamJterator<int>(cout." ")); cout « endl:

Выделение четырех наибольших элементов (второй вариант) nth element (coll.beginO. Начало интервала