7.3.1. Меньше и другие операции сравнения

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

Если X < у ну < 2,10 X < Z.

Если X <у,т:о выражение у < х ложно.

Заметим, что оба эти утверждения справедливы для операции >, но не для >=, <=, == или !=.

7.3.2. Сортировка

void sort

(RandomAccessIterator first, RandomAccessIterator last); void sort

(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Мы обсуждали алгоритм sort, использующий оператор сравнения <, в разделе 1.4 и более общий вариант, использующий передаваемый в качестве параметра предикат сравнения, в разделах 1.11 и 1.12. Вспомним, что можно отсортировать массив целых чисел а в порядке возрастания, написав

sort(а, a+N);

тогда как для сортировки в порядке убывания мы напишем

sort(а, a+N, greater<int>());

7.3.3. Стабильная сортировка

void stable sort

(RandomAccessIterator first,

RandomAccessIterator last); void stabIe sort

(RandomAccessIterator first,

RandomAccessIterator last. Compare comp);

Чтобы обсудить концепцию стабильной сортировки, лучше сортировать структуры, а не целые числа. Следующая программа сортирует массив из 20 записей, каждая из которых содержит строку и целое число. В качестве ключей будут использованы строки, поэтому после сортировки они разместятся в лексикографическом порядке. Мы реализуем это, определяя

оператор < таким образом, что a[i] < a\j], если a[i].s лексикографически предшествует a[j].s. До сортировки в переменных-членах пит структур, храняш;ихся в элементах массива а[0], а[Ц,а[19], содержатся значения 10, И,..., 29.

sortree.срр: Сортировка структур, ♦include <iostream> ♦include <string> ♦ include <algorithin> using namespace std;

struct rectype

{ string s; int num;

bool operator<(const rectype &b)const

{ return s < b.s;

int mainO

{ const int N = 20; string t[20] =

{ Judy , John , John , Judy , John ,

Judy , Paul , Judy , Paul , Mary ,

Mary , John , Judy , Paul , John ,

Paul , Judy , John , Judy , Judy }; int k;

rectype a[N];

for (k=0; k<N; k++)

{ a[k].s = t[k]; a[k].num = 10 + k;

sort(a, a+N);

for (k=0; k<N; k++)

{ cout a[k].s

a[k].num (k % 5 == 4 ? \n : );

return 0;

Программа создает следуюш;ий вывод:

John 11 John 12 John 14 John 27 John 24

John 21 Judy 29 Judy 28 Judy 26 Judy 22

Judy 17 Judy 15 Judy 13 Judy 10 Mary 20

Mary 19 Paul 18 Paul 23 Paul 25 Paul 16

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

Поскольку до сортировки они шли в порядке возрастания, мы видим, что относительный порядок при сортировке не сохранен. Например, в сортированном массиве записи (John, 27) и (John, 24) появляются перечислением, хотя изначально запись (John, 24) была расположена раньше, чем (John, 27). Это происходит из-за того, что алгоритм sort нестабилен. Однако для него есть и стабильная версия. Чтобы использовать ее, мы просто заменим вызов алгоритма sort на следующий:

stable sort(а, a+N);

После этой модификации программа напечатает:

John 11 John 12 John 14 John 21 John 24

John 27 Judy 10 Judy 13 Judy 15 Judy 17

Judy 22 Judy 26 Judy 28 Judy 29 Mary 19

Mary 20 Paul 16 Paul 18 Paul 23 Paul 25

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

Как и для алгоритма sort, для stable sort существует версия, которая в качестве третьего аргумента принимает предикат.

7.3,4. Частичная сортировка

void partial sort

(RandomAccessIterator first,

RandomAccessIterator middle,

RandomAccessIterator last); void partiaI sort

(RandomAccessIterator first,

RandomAccessIterator middle,

RandomAccessIterator last. Compare comp); RandomAccessIterator partiaI sort copy

(Inputlterator first, Inputlterator last,

RandomAccessIterator result first,

RandomAccessIterator result last); RandomAccessIterator partiaI sort copy

(Inputlterator first, Inputlterator last,

RandomAccessIterator result first,

RandomAccessIterator result last. Compare comp);

Если нас интересуют только первые п элементов полностью отсортированной последовательности, где п меньше длины последовательности, то нет необходимости полностью сортировать эту последовательность. В следующей программе элементы а[0], а[1], а[2] и а[3] получают те же значения, которые они имели бы в полностью отсортированном массиве: