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

on entry: 123456789123456789 sorted: 11223344556677В899 sorted >: 998877665544332211

Пример сортировки, при которой в критерии используются функции класса элементов, приведен на с. 133.

Следующая программа демонстрирует различия между алгоритмами sortQ и stabie sort(). В ней оба алгоритма сортируют строки по количеству символов, используя критерий lessLength():

algo/sort2,cpp #include "algostuff.hpp" using namespace std:

bool lessLength (const strings si. const strings s2) {

return sl.lengthO < s2,length();

int mainO (

vector<string> colli: vector<string> coll2;

Заполнение обеих коллекций одинаковыми элементами col col col col col col col col col col col col col col col col col col

l.push back ("Ixxx"): l.push back ("2x") l.push back ("3x") l.push back ("4x") l.push back ("5xx"): l.push back ("бхххх"); l.push back ("7xx"); l.push back C"8xxx"): l.push back ("9xx"); l.push back ("lOxxx"); l,push back ("11") l.push back ("12") l.push back ("13")

14xx 15")

l.push back l.push back l.push back ("16") l.push back ("17") 2 - colli:

PRINT ELEMENTS(colll."on entry:\n ");

Сортировка no длине строк sort (coin.beginO. colli,endO.

Интервал

lessLength); Критерий

stable sort (со112.beginO, coll2.end(). Интервал lessLength); Критерий

PRINT ELEMENTS(colll."\nwith sort():\n "); PRINT ELEMENTS(coll2."\nw1th stable sort();\n O:

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

on entry:

Ixxx 2x 3x 4x 5xx бхххх 7xx 8xxx 9xx lOxxx 11 12 13 14xx 15 16 17 with sort():

17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx Ixxx lOxxx бхххх with stable sort():

2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx Ixxx 8xxx 14xx бхххх IDxxx

Только алгоритм stable sort() сохраняет относительный порядок следования элементов (начальные числа определяют порядок следования элементов в исходном состоянии коллекции).

Частичная сортировка Простая частичная сортировка

void

partial sort (RandomAccessIterator beg. RandomAccessIterator sortEnd.

RandotnAccessIterator end)

void

partial sort (RandomAccessIterator beg, RandomAccessIterator sortEnd.

RandomAccessIterator end. BinaryPredicate op)

О Первая форма сортирует элементы интервала [beg,end) оператором < так, чтобы интервал [begsortEnd) содержал упорядоченные элементы.

О Вторая форма сортирует элементы по критерию op(elemi,elem2) так, чтобы интервал [beg,sortEnd) содержал упорядоченные элементы.

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

О В отличие от sort() алгоритм partial sort() сортирует не все элементы интервала, а прекращает сортировку после того, как подинтервал от начала до sortEnd будет заполнен упорядоченными элементами. Например, если после сортировки интервала вам понадобятся только первые три элемента, этот алгоритм работает более эффективно, поскольку он не тратит время на сортировку остальных элементов.

О Если 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 (coll.beginO. Начало интервала

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

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

PRiNTJLEMENTSCcoll);

Сортировка первых пяти элементов в обратном порядке

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

соП .beginO+5. Конец упорядоченного интервала

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

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

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

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

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

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

PRiNTJLEMENTSCcoll);

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

345672345612345 122337655644345 766551223344345 122333444555667