Как уже должно быть известно из глав 3 и 4, существуют многочисленные механизмы, обеспечивающие условия для выполнения сортировки и других типов данных. Мы подробно обсудим возможности использования таких механизмов в разделе 6.7. Функция sort из программы 6.1 представляет собой приведенную к шаблону реализацию, ссылающуюся на сортируемые элементы только посредством своего первого аргумента и нескольких простейших операций над данными. Как обычно, подобный подход позволяет использовать одни и те же программные коды для сортировки элементов разных типов. Например, если в программный код функции main программы 6.1, выполняющий генерацию, хранение и печать случайных ключей внести изменения, обеспечивающие возможность обработки чисел с плавающей точкой вместо целых чисел, то вообще отпадет необходимость какой-либо модификации функции sort. С целью достижения упомянутой гибкости (и в то же время явной идентификации переменных, в которых хранятся элементы сортировки), реализации должны быть снабжены такими параметрами, благодаря которым стала бы возможной работа с типом данных Item. На данном этапе под типом данных Item подразумевается int или float; в разделе 6.7 подробно рассматривается реализация типов данных, которые позволят выполнять сортировку элементов произвольной природы с ключами в виде чисел с плавающей точкой, строк и других типов, используя механизмы, описанные в главах 3 и 4.

Функцию sort можно заменить любой программой сортировки массивов, представленной в настоящей главе или в главах 7-10. Каждая из них предполагает необходимость сортировки элементов типа Item, каждая из них использует три аргумента: массив, левую и правую границы подмассива, подлежащего сортировке. В них также применяется операция operator<, осуществляющая сравнение ключей элементов, а также функции exch или compexch, выполняющие обмен элементов местами. Чтобы иметь возможность различать методы сортировки, будем присваивать различным профаммам сортировки разные имена. Переименование какой-либо из них, замена про-фаммы-драйвера или использование указателей на функции для переключения с одного алгоритма на другой в клиентской программе, подобной программе 6.1, без внесения изменений в профаммную реализацию алгоритма сортировки, не сопряжено ни с какими трудностями.

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

Пример функции сортировки, представленный программой 6.1, является одним из вариантов сортировки вставками (insertion gort), который более подробно исследуется в разделе 6.3. Так как в нем используются только операции сравнения и обмена, то его можно считать примером неадаптивной (nonadaptive) сортировки: последовательность операций, которые она выполняет, не зависит от порядка следования данных. И наоборот, адаптивная (adaptive) сортировка выполняет различные последовательности операций в зависимости от результата сравнения (вызов операции operator<).

Неадаптивные методы сортировки интересны тем, что они достаточно просто реализуются аппаратными средствами (см. главу 11), однако большинство универсальных алгоритмов сортировки, которые будут предметом наших обсуждений, суть адаптивные методы сортировки.

Как обычно, основной характеристикой алгоритма сортировки, вызывающей наибольший интерес, является время, затрачиваемое на его выполнение. Для выполнения сортировки N элементов методом выбора, методом вставок и пузырьковым методом, которые будут рассматриваться в разделах 6.2-6.4, требуется время, пропорциональное jV, как показано в разделе 6.5. Более совершенные методы, которые исследуются в главах 7-10, могут выполнить сортировку vV элементов за время, пропорциональное jVlogvV, однако эти методы не всегда столь же эффективны, как рассматриваемые здесь методы применительно к небольшим значениям N, а также в некоторых особых случаях. В разделе 6.6 обсуждается более совершенный метод (сортировка методом Шелла), который можно выполнить за время, пропорциональное N или даже за меньшее время, а в разделе 6.10 приводится специализированный метод (сортировка по ключевым индексам), которая для некоторых типов ключей выполняется за время, пропорциональное N.

Аналитические результаты, изложенные в предыдущем параграфе, получены на основе подсчета базовых операций (сравнение и обмен значениями), которые выполняет алгоритм. Как уже отмечалось в разделе 2.2, следует также учитывать затраты ресурсов на выполнение этих операций. Тем не менее, в общем случае мы считаем, что основное внимание целесообразно сосредоточить на изучении наиболее часто используемых операций (внутренний цикл алгоритма). Цель заключается в том, чтобы разработать эффективные и недорогие реализации эффективных алгоритмов. Имея перед собой эту цель, мы не только должны избегать неоправданных расширений внутренних циклов алгоритмов, но и искать пути удаления всевозможных команд из внутренних циклов, где это только возможно. В общем, наилучший способ уменьшения стоимости приложения - это переключение на более эффективный алгоритм; другой способ предусматривает минимизацию внутренних циклов по числу команд. Оба эти способа подробно исследуются на примере алгоритмов сортировки.

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

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

Adams

Black

Brown

Jackson

Jones

Smith

Thompson

Washington

White

Wilson

Adams Smith

Washington

Jackson

Black

White Wilson

Thompson

Brown

Jones

Определение 6.1: Говорят, что метод сортировки устойчив, если он сохраняет относительный порядок размещения элементов в файле, который содержит дублированные ключи.

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

Некоторые (но отнюдь не все) простые методы сортировки, которые рассматриваются в данной главе, суть устойчивые методы. С другой стороны, многие из сложных алгоритмов сортировки (опять-таки, не все), которые исследуются в нескольких последующих главах, таковыми не являются. В тех случаях, когда устойчивость должна быть неотъемлемым свойством, мы вводим его, добавляя перед сортировкой к каждому ключу небольшой индекс, либо расширяем ключ сортировки каким-нибудь другим способом. Выполнение такой дополнительной работы равносильно использованию обоих ключей для сортировки, представленной на рис.6.1; использование устойчивого алгоритма сортировки гораздо предпочтительней. Легко согласиться с необходимостью наличия свойства устойчивости; фактически, ряд более сложных алгоритмов, которые будут рассматриваться в следующих главах, достигают устойчивости без существенных дополнительных затрат памяти и времени.

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

Adams Smith

Black

Jackson

Wdshinglon

White Wilson

Brown Jones Thompson

РИСУНОК 6.1. ПРИМЕР УСТОЙЧИВОЙ СОРТИРОВКИ

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

Распечатано nporpaHHoii FmePnnt - KynHTbWrtwfmeprmt с(