В качестве нашего первого экскурса в область алгоритмов сортировки изучим несколько элементарных методов, которые целесообразно использовать для сортировки файлов небольших размеров либо для сортировки файлов со специальной структурой. Имеются несколько причин для подробного изучения этих простых алгоритмов сортировки. Прежде всего, они представляют собой контекст, в рамках которого можно изучить терминологию и базовые механизмы алгоритмов сортировки, что позволит создать соответствующие предпосылки для изучения более сложных алгоритмов. Во-вторых, эти простые методы во многих приложениях сортировки показали себя, по сути дела, более эффективными, чем мощные универсальные методы. В-третьих, некоторые из простых методов допускают расширение в более эффективные универсальные методы или же могут оказаться полезны полезными в плане повышения эффективности совершенных методов сортировки[3].
Мы рассмотрим различные ситуации, которые благоприятствуют применению того или иного алгоритма сортировки, исследуем различные виды входных файлов, а также рассмотрим различные способы сравнения методов сортировки и изучения их свойств.
Начнем с рассмотрения простой программы тестирования методов сортировки, которая обеспечивает контекст, позволяющий выработать соглашения, необходимые для того, чтобы впоследствии им следовать. Мы также проанализируем базовые свойства различных методов сортировки; их очень важно знать при оценке возможности использования того или иного алгоритма в условиях конкретных приложений. Затем мы подробно рассмотрим реализацию трех элементарных методов: сортировки выбором, сортировки вставками и пузырьковой сортировки. После этого будут подробно анализироваться рабочие характеристики упомянутых алгоритмов. Далее мы рассмотрим сортировку методом Шелла, которой не очень-то подходит характеристика элементарная, однако она достаточно просто реализуется и имеет много общего с сортировкой методом вставки. Затем мы рассмотрим методы сортировки по косвенным ссылкам на данные, а также методы сортировки связных списков. Данная глава завершается обсуждением специализированного метода, который целесообразно использовать, когда известно, что ключи принимают значения в ограниченном диапазоне.
Многие из возможных приложений сортировки часто отдают предпочтение простейшим алгоритмам. Во-первых, очень часто программа сортировки используется всего лишь один или небольшое число раз. После того как удалось решить проблему
сортировки для некоторого набора данных, в дальнейшем потребность в программе сортировки в приложениях, которые манипулируют этими данными, отпадает. Если элементарная сортировка работает не медленней других частей приложения, осуществляющего обработку данных — например, считывание данных или их вывод на печать — то отпадает необходимость в поиске более быстрых методов сортировки. Если число сортируемых элементов не очень большое (скажем, не превышает нескольких сотен элементов), можно просто воспользоваться простым методом и не ломать голову над тем, как работает интерфейс для системной сортировки, или как написать и отладить программу, реализующую какой-нибудь сложный метод сортировки. Во- вторых, элементарные методы всегда годятся для файлов небольших размеров (состоящих из нескольких десятков элементов) — сложные алгоритмы в общем случае обусловливают непроизводительные затраты ресурсов, а это приводит к тому, что на файлах небольших размеров они работают медленнее элементарных методов сортировки. Эта проблема не попадет в фокус нашего внимания до тех пор, пока не возникнет необходимость сортировки большого числа файлов небольших размеров, однако следует иметь в виду, что приложения с подобного рода требованиями встречаются достаточно часто. Другими типами файлов, сортировка которых существенно упрощена, являются файлы, с почти (или уже) завершенной сортировкой или файлы, которые содержат большое число дублированных ключей. Далее можно будет убедиться в том, что некоторые методы из числа простейших особенно эффективны при сортировке хорошо структурированных файлов.
Как правило, для сортировки случайно упорядоченного файла из N элементов с применением элементарных методов, которые обсуждаются в данной главе, требуется время, пропорциональное N2. Если N не велико, то такое время выполнения сортировки может оказаться вполне приемлемым. Как только что было отмечено, эти методы, примененные для сортировки файлов небольших размеров, а также в ряде других специальных случаев, по эффективности могут превзойти более сложные методы сортировки. Однако методы, которые исследуются в настоящей главе, не годятся для сортировки файлов больших размеров с произвольной организацией, поскольку время их сортировки будет недопустимо большим, даже если она выполняется на сверхбыстродействующих компьютерах. В этом плане заслуживающим внимания исключением может послужить сортировка методом Шелла, для которого при большом N требуется гораздо меньше, чем N2 шагов, при этом можно утверждать, что данный метод является одним из наилучших для сортировки файлов
средних размеров и для ряда других специальных случаев.
Правила игры
Прежде чем переходить к рассмотрению конкретных алгоритмов, полезно обсудить общую терминологию и базовые принципы построения алгоритмов сортировки. Мы будем рассматривать методы сортировки файлов элементов, обладающих ключами. Эти понятия являются естественными абстракциями для современных сред программирования. Ключи, которые — суть лишь часть (зачастую очень небольшая часть) элементов, используются для управления сортировкой. Цель метода сортировки заключается в переупорядочении элементов таким образом, чтобы их ключи следовали в соответствии с четко определенными правилами (обычно это цифровой или алфавитный порядок). Специфические характеристики ключей и элементов в
разных приложениях могут существенно отличаться друг от друга, однако абстрактное понятие размещения ключей и связанной с ними информации в определенном порядке и представляет собой суть проблемы сортировки[3].
Если сортируемый файл полностью помещается в оперативной памяти, то используемый в этом случае метод сортировки называется внутренним. Сортировка файлов, хранящихся на магнитной ленте или диске, называется внешней. Основное различие между этими двумя методами заключается в том, что в условиях внутренней сортировки доступ к любому элементу не представляет трудностей, в то время как в условиях внешней сортировки возможен только последовательный метод доступа или, по меньшей мере, доступ к блокам больших размеров.
Мы будем рассматривать как массивы, так и связные списки. Как проблема сортировки массивов, так и проблема сортировки связных списков представляют несомненный интерес: в процессе разработки собственных алгоритмов мы столкнемся с некоторыми базовыми задачами, для которых лучше всего подойдет последовательное распределение элементов, для других же задач больше подходит структура связных списков. Некоторые из классических методов обладают столь высокой степенью абстракции, что могут одинаково эффективно применяться как к массивам, так и к связным спискам; в то же время другие максимально эффективно проявляют себя на каком-то одном виде указанных выше объектов сортировки. Другие виды ограничений доступа также иногда представляют определенный интерес.
Для начала стоит акцентировать внимание на сортировке массивов. Программа 9 может служить иллюстрацией соглашений, которые будут соблюдаться во всех реализациях. Она состоит из управляющей программы (в дальнейшем программы-драйвера), которая заполняет массив, считывая целые значения из стандартного ввода либо генерируя случайные целые значения (соответствующий режим работы программы задается целым аргументом). Затем эта программа вызывает функцию сортировки,
которая размещает эти целые значения в определенном порядке, а в завершение выполняет печать результатов сортировки.
