partsort.cpp: Частичная сортировка. #include <iostream> #include <string> #include <algorithin> using namespace std;

int mainO

{ int a[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; partial sort(a, a+4, a+10); for (int k=0; k<10; k++)

cout a[k] (k == 3 ? : ); cout endl; return 0;

Программа выводит следующую строку:

0123 987654

Элементы после первых четырех могут появляться в любом порядке; хотя в этом примере они располагаются в том же относительном порядке, в каком были изначально, мы не должны рассчитывать на такое поведение.

Другая версия алгоритма partial sort принимает в качестве четвертого аргумента предикат для сравнения, как аналогичная версия алгоритма sort.

Если мы хотим разместить результаты в диапазоне, отличном от исходного, то можем использовать алгоритмы partial sort copy. Снова один из этих двух алгоритмов использует для сравнения оператор меньше , а другой - предикат, который передается дополнительным аргументом. Первый вариант, использующий <, встречается в следующей программе:

partsrtl.срр: partial sort copy. #include <iostream> #include <algorithm> using namespace std;

int mainO

{ int a[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}, b[40], *p;

p = partial sort copy(a, a+10, b, b+4); copy(b, p, ostream iterator<int>(cout, )); cout endl;

p = partial sort copy(a, a+10, b, b+40); copy(b, p, ostream iterator<int>(cout, )); cout endl; return 0;

Алгоритм partialsortjoopy принимает два диапазона, один задает источник, а другой - приемник. Меньший из этих диапазонов определяет, сколько

отсортированных элементов появится в выходном диапазоне-приемнике; в любом случае функция возвращает итератор, ссылающийся на элемент, расположенный сразу за отсортированным поддиапазоном. Приведенная выше программа демонстрирует две ситуации. После первого вызова partialjsortcopy мы имеем р - b = тш( 10, 4) = 4, а после второго вызова р - b = mm( 10,40) = 10, как показывает следующий вывод программы:

0 12 3

0234456789

7.3.5. N-й элемент

void nth element

(RandomAccessIterator first, RandomAccessIterator position, RandomAccessIterator last); void nth element

(RandomAccessIterator first, RandomAccessIterator position, RandomAccessIterator last, Compare comp);

После вызова алгоритма nthelement с итератором p в качестве второго аргумента значение *р принимает то же значение, какое будет после полной сортировки этого диапазона. Следующая программа иллюстрирует это:

nth elt.cpp: Алгоритм nth element. ♦include <iostream> ♦include <algorithm> using namespace std;

int main()

{ int a[10] = {4, 12, 9, 5, 6, 6, 6, 4, 8, 10}; nth element(a, a+2, a+10);

copy(a, a+10, ostream iterator<int>(cout, )); cout endl; return 0;

Вывод

4456669 12 8 10

этой программы показывает, что элемент а{2] содержит значение 5. Этот элемент будет иметь такое же значение в полностью отсортированном массиве:

44566689 10 12

Если не считать порядка, содержание массива не меняется. Кроме того, все элементы, предшествующие выбранному элементу, не превышают по значению этот элемент, а все элементы, следующие за ним, не меньше его.

Три аргумента функции nth element являются итераторами произвольного доступа. Вторая версия алгоритма имеет четвертый аргумент, который является предикатом для сравнения. Например, если мы заменим вызов nth element в вышеприведенной программе на

nth element(а, а+2, а+10, greater<int>());

ТО получим следующий вывод:

10 12 98666454

Следует обратить внимание, что а[2] = 9, как и в случае, если этот массив будет полностью отсортирован в нисходящем порядке. Элементы, предшествующие а[2], по своему значению не меньше, а те, которые следуют после, по значению не больше этого элемента.

7.3.6. Двоичный поиск

Forwardlterator lower bound

(Forwardlterator first, Forwardlterator last, const T& value); Forwardlterator lower bound

(Forwardlterator first, Forwardlterator last, const T& value. Compare comp); Forwardlterator upper bound

(Forwardlterator first, Forwardlterator last, const T& value); Forwardlterator upper bound

(Forwardlterator first, Forwardlterator last, const T& value. Compare comp); pair<ForwardIterator, ForwardIterator> egual range (Forwardlterator first, Forwardlterator last, const T& value); pair<ForwardIterator, ForwardIterator> egual range (Forwardlterator first, Forwardlterator last, const T& value. Compare comp); bool bina2ry search

(Forwardlterator first, Forwardlterator last, const T& value); bool binary search

(Forwardlterator first, Forwardlterator last, const T& value. Compare comp);

В этом разделе мы обсудим четыре алгоритма - lower bound, upper bound, equal range и binary search. В нашей программе встретятся только версии, которые используют оператор сравнения <. Для каждого из этих четырех алгоритмов существует также версия, имеющая дополнительный аргумент, предикат сравнения. Все алгоритмы предполагают, что используемый