iinclude <algorithm> using namespace std;

int mainO

{ int a[6] = {10, 20, 30, 40, 50, 60}; random shuffle(a, a+6);

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

Когда мы запустили эту программу в первый раз, она напечатала

40 10 60 30 20 50

Мы запускали эту программу несколько раз, но результат оставался тем же самым. Это объясняется тем, что алгоритм random shuffle основан на генераторе псевдослзайных чисел, который работает одинаково (использует одну и ту же затравку ) каждый раз, когда мы запускаем программу.

Вторая версия randomjshuffle в STL принимает в качестве третьего аргумента генератор слзайных чисел. Это позволит получать разные результаты при разных запусках программы. Функция-генератор слзайных чисел должна ползать аргумент п типа int и возвращать слзайным образом выбранное целое значение в диапазоне [О, п). Генератор случайных чисел также может быть функциональным объектом, как в следующей программе:

rshuffl.cpp: Тасование; используем свой генератор.

iinclude <iostream>

iinclude <stdlib.h>

iinclude <time.h>

iinclude <algorithm>

using namespace std;

struct myrandom { myrandom()

{ srand((unsigned int)time(NULL)); }

int operator0 (int n){return rand() % n;}

int mainO

{ int a[6] = {10, 20, 30, 40, 50, 60}; random shuf f le (a, a+6, myrandomO); copy(a, a+6, ostream iterator<int>(cout, )); cout endl; return 0;

При первом запуске эта программа напечатала

50 10 30 20 40 60 Когда мы запустили ее еще раз, результат был отличный:

10 30 60 40 20 50

Кстати, вместо класса myrandom мы можем использовать функцию

int randfun(int n) { static int first = 1; if (first)

{ srand((unsigned int)time(NULL)); first = 0;

return randO % n;

если мы также заменим вызов random shuffie на следующий:

random shuffie(а, a+6, randfun);

7.2.12. Разделить

Bidirectionallterator partition (Bidirectionallterator first, Bidirectionallterator last, Predicate pred); Bidirectionallterator stable partition (Bidirectionallterator first, Bidirectionallterator last. Predicate pred);

Алгоритм partition образует два раздела в заданном диапазоне. Он размещает элементы, удовлетворяющие заданному условию, перед теми, которые этому условию не соответствуют. В следующей программе массив а содержит целые числа, часть из них меньше 50. Мы используем алгоритм partition, которому передаем предикат меньше 50 для перестановки элементов массива а таким образом, что все элементы, удовлетворяющие указанному условию, будут предшествовать элементам, чье значение больше или равно 50. Алгоритм возвращает значение итератора, ссылающееся на первый элемент во втором разделе:

partitio.cpp: Алгоритм partition, ttinclude <iostream> #include <algorithm> using namespace std;

bool below50(int x){return x < 50;)

int main О

{ int а[8] = {70, 40, 80, 20, 50, 60, 50, 10); int *р = partition(a, а+8, below50); copy(а, р, ostream iterator<int>(cout, )); cout <<

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

Массив a содержит три элемента (40, 20 и 10), которые меньше, чем 50. После вызова partition эти элементы группируются в начале массива, как показывает вывод программы:

10 40 20 80 50 60 50 70

Значение р - а равно длине (3) первого раздела. Один из двух разделов может оказаться пустым. Например, если в функции below50 мы заменим 50 на 1000, ползшимр - а = 8, а если в этой функции заменим 50 на 0,р - а станет равным 0.

Обратите внимание, что элементы 40, 20 и 10, меньшие 50, не сохраняют свой первоначальный относительный порядок, как не сохраняют его и остальные элементы (70, 80, 50, 60, 50). Если мы хотим, чтобы относительный порядок элементов в каждом из разделов остался прежним, нам достаточно заменить вызов partition на stable jpartition, написав

int *р = stable partition(а, а+8, belowSO);

В результате мы получим следующий вывод программы, где элементы в каждом из разделов сохраняют тот же порядок, что и в исходной последовательности:

40 20 10 70 80 50 60 50

Алгоритм stable jpartition обычно требует большего времени для выполнения, чем алгоритм partition; если бы это было не так, разработчики STL, без сомнения, сохранили бы только алгоритм, осуществляющий стабильное разделение последовательности.

Кстати, на разделении последовательности основан известный метод быстрой сортировки {quicksort).

7.3. Алгоритмы, связанные с сортировкой

В этом разделе собраны алгоритмы, имеющие отношение к сортировке. Для каждого из них существуют две версии: одна использует оператор <, а другая - любую заданную функцию сравнения.