анализируем базовые свойства различных методов сортировки; их очень важно знать при оценке возможности использования того или иного алгоритма в условиях конкретных приложений. Затем мы подробно рассмотрим реализацию трех элементарных методов: сортировки выбором, сортировки вставками и пузырьковой сортировки. После этого будут подробно анализироваться рабочие характеристики упомянутых алгоритмов. Далее мы рассмотрим сортировку методом Шелла, которой не очень-то подходит характеристика элементарная , однако она достаточно просто реализуется и имеет много общего с сортировкой методом вставки. Углубляясь в математические свойства сортировки методом Шелла, мы займемся изучением проблемы разработки интерфейсов типов данных, наряду с программами, которые рассматривались в главах 3 и 4 и которые предназначены для распространения изучаемых алгоритмов на сортировку различных видов файлов данных, какие встречаются на практике. Затем мы рассмотрим методы сортировки по косвенным ссылкам на данные, а также методы сортировки связных списков. Данная глава завершается обсуждением специализированного метода, который целесообразно использовать, когда известно, что ключи принимают значения в ограниченном диапазоне.

Многие из возможных приложений сортировки часто отдают предпочтение простейшим алгоритмам. Во-первых, очень часто программа сортировки используется всего лишь один или небольшое число раз. После того как удалось решить проблему сортировки для некоторого набора данных, в дальнейшем потребность в программе сортировки в приложениях, которые манипулируют этими данными, отпадает. Если элементарная сортировка работает не медленней других частей приложения, осуществляющего обработку данных - например, считывание данных или их вывод на печать - то отпадает необходимость в поиске более быстрых методов сортировки. Если число сортируемых элементов не очень большое (скажем, не превышает нескольких сотен элементов), можно просто воспользоваться простым методом и не ломать голову над тем, как работает интерфейс для системной сортировки, или как написать и отладить программу, реализующую какой-нибудь сложный метод сортировки. Во-вторых, элементарные методы всегда годятся для файлов небольших размеров (состоящих из нескольких десятков элементов) - сложные алгоритмы в общем случае обусловливают непроизводительные затраты ресурсов, а это приводит к тому, что на файлах небольших размеров они работают медленнее элементарных методов сортировки. Эта проблема не попадет в фокус нашего внимания до тех пор, пока не возникнет необходимость сортировки большого числа файлов небольших размеров, однако следует иметь в виду, что приложения с подобного рода требованиями встречаются достаточно часто. Другими типами файлов, сортировка которых существенно упрощена, являются файлы, с почти (или уже) завершенной сортировкой или файлы, которые содержат большое число дублированных ключей. Далее можно будет убедиться в том, что некоторые методы из числа простейших особенно эффективны при сортировке хорошо структурированных файлов.

Как правило, для сортировки случайно упорядоченного файла из 7V элементов с применением элементарных методов, которые обсуждаются в данной главе, требуется время, пропорциональное 7V. Если 7V не велико, то такое время выполнения сортировки может оказаться вполне приемлемым. Как только что было отмечено, эти методы, примененные для сортировки файлов небольших размеров, а также в ряде дру-

гих специальных случаев, по эффективности могут превзойти более сложные методы сортировки. Однако методы, которые исследуются в настоящей главе, не годятся для сортировки файлов больщих размеров с произвольной организацией, поскольку время их сортировки будет недопустимо большим, даже если она выполняется на сверхбыстродействующих компьютерах. В этом плане заслуживающим внимания исключением может послужить сортировка методом Шелла (см. раздел 6.6), для которого при большом yv требуется гораздо меньше, чем Л шагов, при этом можно утверждать, что данный метод является одним из наилучших для сортировки файлов средних размеров и для ряда других специальных случаев.

6.1. Правила игры

Прежде чем переходить к рассмотрению конкретных алгоритмов, полезно обсудить общую терминологию и базовые принципы построения алгоритмов сортировки. Мы будем рассматривать методы сортировки файлов элементов, обладающих ключами. Эти понятия являются естественными абстракциями для современных сред программирования. Ключи, которые - суть лишь часть (зачастую очень небольшая часть) элементов, используются для управления сортировкой. Цель метода сортировки заключается в переупорядочении элементов таким образом, чтобы их ключи следовали в соответствии с четко определенными правилами (обычно это цифровой или алфавитный порядок). Специфические характеристики ключей и элементов в разных приложениях могут существенно отличаться друг от друга, однако абстрактное понятие размещения ключей и связанной с ними информации в определенном порядке и представляет собой суть проблемы сортировки.

Если сортируемый файл полностью помещается в оперативной памяти, то используемый в этом случае метод сортировки называется внутренним. Сортировка файлов, хранящихся на магнитной ленте или диске, называется внешней. Основное различие между этими двумя методами заключается в том, что в условиях внутренней сортировки доступ к любому элементу не представляет трудностей, в то время как в условиях внешней сортировки возможен только последовательный метод доступа или, по меньшей мере, доступ к блокам больших размеров. Некоторые из внешних методов сортировки рассматриваются в главе 11, однако большая часть исследуемых алгоритмов принадлежит к категории внутренней сортировки.

Мы будем рассматривать как массивы, так и связные списки. Как проблема сортировки массивов, так и проблема сортировки связных списков представляют несомненный интерес: в процессе разработки собственных алгоритмов мы столкнемся с некоторыми базовыми задачами, для которых лучше всего подойдет последовательное распределение элементов, для других же задач больше подходит структура связных списков. Некоторые из классических методов обладают столь высокой степенью абстракции, что могут одинаково эффективно применяться как к массивам, так и к связным спискам; в то же время другие максимально эффективно проявляют себя на каком-то одном виде указанных выше объектов сортировки. Другие виды ограничений доступа также иногда представляют определенный интерес.

Для начала стоит акцентировать внимание на сортировке массивов. Программа 6.1 может служить иллюстрацией соглашений, которые будут соблюдаться во всех реал и-

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

Программа 6.1. Пример сортировки массива с помощью управляющей программы

Данная программа служит иллюстрацией принятых нами соглашений, касающихся реализации базовых алгоритмов сортировки массивов. Функция main - суть драйвер, который инициализирует массив целыми значениями (случайными значениями либо значениями, полученными из стандартного ввода), вызывает функцию sort с целью выполнения сортировки заполненного массива, после чего выводит на печать упорядоченный результат сортировки.

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

Можно внести соответствующие изменения в программу-драйвер, чтобы она смогла выполнять сортировку любых типов данных, для которых определена операция operator<, не внося при этом никаких изменений в функцию sort (см. раздел 6.7).

#include <iostream.h> #include <stdlib.h> template <class Item> void exch(Item &A, Item &B)

{ Item t = A; A = B; В = t; } template <class Item> void compexch (Item &A, Item &B) { if (B < A) exch(A, B) ; } template <class Item> void, sort(Item a[], int 1, int r) { for (int i = 1+1; i <= r; i++) for (int j = i; j > 1; j -) compexch(a[j-1] , a[j]);

int main(int argc, char *argv[]) { int i, N = atoi(argv[l]) , sw = atoi (argv[2]) ; int *a = new int [N] ; if (sw)

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

a[i] = 1000*(1.0*rand()/RAND MAX);

else

{ N = 0; while (cin a[N]) N++; } sort(a, 0, N-l);

for (i = 0; i < N; i++) cout a[i] ; cout endl;