Обычно функция упорядочения не вычисляется по KaKOMy-fj специальному правилу, а содержится в каждом элемент^ в виде явной компоненты (поля). Ее значение называете, ключом элемента. Следовательно, для представления эле, мента а,- особенно хорошо подходит структура записи. Пц. этому мы определяем тип item (элемент), который буд^}

Рис. 2.2. Сортировка файла.

использоваться в последующих алгоритмах сортировки следующим образом:

iype item = record key: integer;

[описание других компонент]

(2.2)

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

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не ме няется при сортировке. Устойчивость сортировки часто бывает желательна, если элементы упорядочены (рассортированы) по каким-то вторичным ключам, т. е. по свойствам, не отраженным в первичном ключе.

Не следует считать, что данная глава представляет собой ерпывающий обзор методов сортировки. Здесь лишь осо-л^нно подробно разбираются некоторые избранные методы. Чяинг^ресовэнного читателя, желающего получить полное оедставление о сортировке, мы отсылаем к блестящей и всеобъемлющей работе Д. Кнута [2.7] (см. также [2.10]).

jj. сортировка массивов

Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте) и что методы, которые пересылают элементы из массива а в массив Ь, не представляют для нас интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов мы проводим в соответствии с их эффективностью, т. е. экономией времени или быстродействием. Удобная мера эффективности получается при подсчете числа С - необходимых сравнений ключей ц М - пересылок элементов. Эти числа определяются некоторыми функциями от числа п сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n-\ogn сравнений, мы сначала обсудим несколько несложных и очевидных способов сортировки, называемых простыми методами, которые требуют порядка сравнений ключей. Мы решили рассмотреть простые методы прежде, чем перейти к более быстрым алгоритмам, по следующим трем важным причинам:

1. Простые методы особенно хорошо подходят для разъяснения свойств большинства принципов сортировки.

2. Программы, основанные на этих методах, легки для понимания и коротки. Следует помнить, что программы также занимают память!

3. Хотя сложные методы требуют меньшего числа операций, эти операции более сложны; поэтому при достаточно малых п простые методы работают быстрее, но их не следует Использовать при больших п.

Методы, сортирующие элементы In situ, можно разбить три основных класса в зависимости от лежащего в их пове приема:

Сортировка включениями. Сортировка выбором. - Сортировка обменом.

перь мы рассмотрим и сравним эти три принципа. Про-Раммы работают с переменной-массивом а, компоненты

которой нужно рассортировать in situ. В этих программах используются типы данных item (2.2) и index, определенны^ так:

type index == О.. и;

var а: аггауЦ .. и] of item

(2.3)

2.2.1. Сортировка простыми включениями.

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность

1.....ai-i и входную последовательность Ui, а„. На

каждом шаге, начиная с i = 2 и увеличивая i на единицу, берут jj элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

Таблица 2.1. Пример сортировки простыми включениями

Процесс сортировки включениями показан на примере восьми случайно взятых чисел (см. табл. 2.1). Алгоритм сортировки простыми включениями выглядит следующим образом:

for i := 2, to п do beginA;:=a[t];

вставить X на подходящее место в а, ... а^

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

1. Найден элемент а,- с ключом меньшим, чем ключ х.

2. Достигнут левый конец готовой последовательности.

Этот типичный пример цикла с двумя условиями окончаний дает нам возможность рассмотреть хорошо известный приен'