Данная программа служит иллюстрацией принятых нами соглашений, касающихся реализации базовых алгоритмов сортировки массивов. Функция main — суть драйвер, который инициализирует массив целыми значениями (случайными значениями либо значениями, полученными из стандартного ввода), вызывает функцию sort с целью выполнения сортировки заполненного массива, после чего выводит на печать упорядоченный результат сортировки.
Шаблоны позволяют использовать данную программную реализацию для сортировки элементов, принадлежащих к различным типам данных, для которых определены операции сравнения и присваивания. В рассматриваемом случае функция sort
представляет собой частный случай сортировки вставками (см. раздел 5.3, в котором приводится подробное описание, пример и улучшенный вариант реализации). Она использует шаблонную функцию, которая сравнивает два элемента и при необходимости производит обмен их местами, чтобы второй элемент был не меньше первого.
Можно внести соответствующие изменения в программу-драйвер, чтобы она смогла выполнять сортировку любых типов данных, для которых определена операция operator <, не внося при этом никаких изменений в функцию sort.
#include <±ostream.h>
#include <stdlib.h>
template <class Item>
void exch(Item &A, Item &B)
{ Item t = A; A = В; В = 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;
}
Функция sort из программы 9 представляет собой приведенную к шаблону реализацию, ссылающуюся на сортируемые элементы только посредством своего первого аргумента и нескольких простейших операций над данными. Как обычно, подобный подход позволяет использовать одни и те же программные коды для сортировки элементов разных типов. Например, если в программный код функции main программы 9, выполняющий генерацию, хранение и печать случайных ключей внести изменения, обеспечивающие возможность обработки чисел с плавающей точкой вместо целых чисел, то вообще отпадет необходимость какой-либо модификации функции sort. С целью достижения упомянутой гибкости (и в то же время явной идентификации переменных, в которых хранятся элементы сортировки), реализации должны быть снабжены такими параметрами, благодаря которым стала бы возможной работа с типом данных Item. На данном этапе под типом данных Item подразумевается int или float.
Функцию sort можно заменить любой программой сортировки массивов. Каждая из них предполагает необходимость сортировки элементов типа Item, каждая из них использует три аргумента: массив, левую и правую границы подмассива, подлежащего сортировке. В них также применяется операция operator <, осуществляющая сравнение ключей элементов, а также функции exch или compexch, выполняющие обмен элементов местами. Чтобы иметь возможность различать методы сортировки, будем присваивать различным программам сортировки разные имена. Переименование какой-либо из них, замена программы-драйвера или использование указателей на функции для переключения с одного алгоритма на другой в клиентской программе, подобной программе 9, без внесения изменений в программную реализацию алгоритма сортировки, не сопряжено ни с какими трудностями.
Принятые соглашения позволяют проводить анализ многих естественных и компактных программных реализаций алгоритмов сортировки массивов. И хотя мы всегда будем уделять должное внимание требованиям к организации программных пакетов, основные усилия будут направляться на решение алгоритмических проблем, к рассмотрению которых мы сейчас и переходим. Пример функции сортировки, представленный программой 9, является одним из вариантов сортировки вставками (insertion gort), который более подробно исследуется в разделе 5.3. Так как в нем используются только операции сравнения и обмена, то его можно считать примером неадаптивной (nonadaptive) сортировки: последовательность операций, которые она выполняет, не зависит от порядка следования данных. И наоборот, адаптивная (adaptive) сортировка выполняет различные последовательности операций в зависимости от результата сравнения (вызов операции operator <).
Как обычно, основной характеристикой алгоритма сортировки, вызывающей наибольший интерес, является время, затрачиваемое на его выполнение. Для выполнения сортировки N элементов методом выбора, методом вставок и пузырьковым методом, которые будут рассматриваться в разделах 5.2—5.4, требуется время, пропорциональное N2, как показано в разделе 5.5. Более совершенные методы, могут выполнить сортировку N элементов за время, пропорциональное NlogN, однако эти методы не всегда столь же эффективны, как рассматриваемые здесь методы применительно к небольшим значениям N, а также в некоторых особых случаях. В разделе 5.6 обсуждается более совершенный метод (сортировка методом Шелла), который можно выполнить за время, пропорциональное N3/2 или даже за меньшее время.
В общем случае мы считаем, что основное внимание целесообразно сосредоточить на изучении наиболее часто используемых операций (внутренний цикл алгоритма). Цель заключается в том, чтобы разработать эффективные и недорогие реализации эффективных алгоритмов. Имея перед собой эту цель, мы не только должны избегать неоправданных расширений внутренних циклов алгоритмов, но и искать пути удаления всевозможных команд из внутренних циклов, где это только возможно. В общем, наилучший способ уменьшения стоимости приложения — это переключение на более эффективный алгоритм; другой способ предусматривает минимизацию внутренних циклов по числу команд. Оба эти способа подробно исследуются на примере алгоритмов сортировки.
Дополнительный объем оперативной памяти, используемый алгоритмом сортировки, является вторым по важности фактором, который также будет рассматриваться. По существу, все эти методы можно разбить на три категории: те, которые выполняют сортировку на месте и не нуждаются в дополнительной памяти, за исключением, возможно, небольшого стека или таблицы; те, которые используют представление в виде связного списка или каким-то другим способом получает доступ к данным, используя для этой цели указатели или индексы массивов, в связи с чем необходима дополнительная память для размещения N указателей или индексов, и те, которые требуют дополнительной памяти для размещения еще одной копии массива, подвергаемого сортировке.
Довольно-таки часто применяются методы сортировки элементов с несколькими ключами — иногда возникает необходимость сортировки одного и того же набора элементов в разные моменты по разным ключам. В таких случаях очень важно знать, обладает ли выбранный метод сортировки следующим свойством:
Определение 6: Говорят, что метод сортировки устойчив, если он сохраняет относительный порядок размещения элементов в файле, который содержит дублированные ключи.
Например, если сформированный по алфавиту список студентов и год окончания школы упорядочен по году, устойчивый метод сортировки выдает список, в котором студенты, окончившие школу в одном и том же году, опять-таки перечисляются в алфавитном порядке, в то время как при использовании неустойчивого метода, скорее всего, будет получен список, в котором алфавитный порядок в рамках года не сохраняется. Очень часто люди, не знакомые с понятием устойчивости, когда впервые сталкиваются с подобного рода ситуацией, с удивлением обнаруживают, до какой степени неустойчивый алгоритм сортировки нарушает начальный порядок.
Некоторые (но отнюдь не все) простые методы сортировки, которые рассматриваются в данной главе, суть устойчивые методы. С другой стороны, многие из сложных алгоритмов сортировки (опять-таки, не все), которые исследуются в нескольких последующих главах, таковыми не являются. В тех случаях, когда устойчивость должна быть неотъемлемым свойством, мы вводим его, добавляя перед сортировкой к каждому ключу небольшой индекс, либо расширяем ключ сортировки каким-нибудь другим способом. Выполнение такой дополнительной работы равносильно использованию обоих ключей для сортировки, представленной на рис.18; использование устойчивого алгоритма сортировки гораздо предпочтительней. Легко согласиться с необходимостью наличия свойства устойчивости; фактически, ряд более сложных алгоритмов, которые будут рассматриваться в следующих главах, достигают устойчивости без существенных дополнительных затрат памяти и времени.
Как уже отмечалось ранее, программы сортировки осуществляют доступ к элементам в соответствие с одним из двух следующих способов: либо доступ к ключам с последующим выполнением операции сравнения, либо доступ к элементам в целом с целью их перемещения. Если сортируемые элементы имеют большие размеры, не имеет смысла перемещать их в памяти, целесообразнее выполнять непрямую (indirect) сортировку: переупорядочиваются не сами элементы, а, скорее, массив указателей (индексов) так, что первый указатель указывает на наименьший элемент, следующий — на наименьший из оставшихся и т.д. Ключи можно хранить вместе с самими элементами (если ключи большие) либо с указателями (если ключи небольших размеров). Можно переупорядочить элементы после сортировки, но часто в этом нет необходимости, поскольку теперь уже имеется возможность обращения к ним в порядке, установленном сортировкой (косвенным путем).
Рис.18. Пример устойчивой сортировки
Сортировка выбором
Один из самых простых алгоритмов сортировки работает следующим образом. Сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом массиве. Далее, находится второй наименьший эле-
элемент и меняется местами с элементом, стоящим вторым в исходном массиве. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован. Изложенный метод называется сортировкой выбором, поскольку он работает по принципу выбора наименьшего элемента из числа неотсортированных. На рис.19 представлен пример работы этого метода[3].
Программа 10 — суть реализация сортировки выбором, в которой выдержаны все принятые нами соглашения. Внутренний цикл представляет собой сравнение текущего элемента с наименьшим из выявленных к тому времени элементом (плюс программный код, необходимый для увеличения на единицу индекса текущего элемента и проверки того, что он не выходит за границы массива); трудно себе представить более простой метод сортировки. Действия по перемещению элементов выходят за пределы внутреннего цикла: каждая операция обмена элементов местами устанавливает один из них в окончательную позицию, так что всего потребуется выполнить N — 1 таких операций (для последнего элемента эту операцию выполнять не нужно). Таким образом, основную составляющую времени выполнения сортировки представляет количество осуществленных операций сравнения. В разделе 5.5 будет показано, что это время пропорционально N2, а также представлены способы вычисления общего времени выполнения программы сортировки и корректного сравнения сортировки выбором и других элементарных методов.