Подготовительная программа

#include <iostream.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 (Itern a[] , int m, int r)

{ for (int i = m+1; i <= r; i++)

for (int j = i; j > m; j--)

compexch(a[j-1], a[j]);

}

6.2. Сортировка выбором

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

Программа 6.2 – суть реализация сортировки выбором, в которой выдержаны все принятые нами соглашения. Внутренний цикл представляет собой сравнение текущего элемента с наименьшим из выявленных к тому времени элементом (плюс программный код, необходимый для увеличения на единицу индекса текущего элемента и проверки того, что он не выходит за границы массива); трудно себе представить более простой метод сортировки. Действия по перемещению элементов выходят за пределы внутреннего цикла: каждая операция обмена элементов местами устанавливает один из них в окончательную позицию, так что всего потребуется выполнить N–1 таких операций (для последнего элемента эту операцию выполнять не нужно). Таким образом, основную составляющую времени выполнения сортировки представляет количество осуществленных операций сравнения. В разделе 6.5 будет показано, что это время пропорционально N², а также представлены способы вычисления общего времени выполнения программы сортировки и корректного сравнения сортировки выбором и других элементарных методов.

Программа 6.2. Сортировка выбором

Для каждого i от m до r–1 поменять местами элемент a[i] с минимальным элементом в последовательности a[i],...,a[r],. По мере продвижения индекса i слева направо, элементы слева от него занимают свои окончательные позиции в массиве (дальнейшим перемещениям они не подлежат), таким образом, массив будет полностью отсортирован, когда i достигнет его правого конца.

template <class Item>

void selection (Item a[], int m, int r)

{ for (int i = m; i < r; i++)

{ int min = i;

for (int j = i+1; j <= r; j++)

if (a[j] < a[min]) min = j;

exch(a[i], a[min]);

}

}

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

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

6.3. Сортировка вставками

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

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

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

Прежде всего, можно отказаться от выполнения операций compexch,если встречается ключ, который не больше ключа вставляемого элемента, поскольку подмассив, находящийся слева, уже отсортирован. А именно, если справедливо условие a[j-l] < a[j],то выполняя команду break,можно выйти из внутреннего цикла for в функции sortпрограммы 6.1. Всвязи с таким изменением реализация превращается в адаптивную сортировку, благодаря чему быстродействие программы, примененной для сортировки ключей, упорядоченных случайным образом, повышается примерно в два раза (см. лемму 6.2). Внеся усовершенствования, описанные в предыдущем параграфе, получаем два условия прекращения выполнения внутреннего цикла – можно изменить программой_: код и представить в виде цикла while,дабы отобразить этот факт наглядно. Менее очевидное улучшение реализации следует из того факта, что проверка условия k>1 обычно оказывается излишней: и в самом деле, она достигает цели только в случае, когда вставляемый элемент является наименьшим из просмотренных к этому моменту, благодаря чему он достигает начала массива. Широко используемая альтернатива этому заключается в том, чтобы сохранять сортируемые ключи в элементах массива от а[1]до a[N],а сигнальный ключ (sentinel key) поместить в а[0],устанавливая его значение, по меньшей мере, не превышающим наименьшего ключа в сортируемом массиве. Теперь проверка того факта, что обнаружен ключ меньше сигнального, одновременно становится проверкой обоих представляющих интерес условий, благодаря чему внутренний цикл становится меньше, а быстродействие программы повышается.

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

Программа 6.3, Сортировка вставками

Этот программа представляет собой усовершенствованный вариант функции sort из программы 6.1, поскольку: (1) он помещает наименьший элемент массива в первую позицию; в этом качестве наименьший элемент может быть использован как сигнальный ключ; (2) во внутреннем цикле он выполняет лишь одну операцию присваивания; операция обмена исключается; и (3) он прекращает выполнение внутреннего цикла, когда вставляемый элемент уже находится в требуемой позиции. Для каждого i он сортирует элементы а[1],..., a[i], перемещая на одну позицию вправо элементы а[1],..., а[i–1] из отсортированного списка, которые по значению больше a[i], после чего a[i] попадает в соответствующее место.

template <class Item>

void insertion (Item a[], int m, int r)

{ int i;

for (i=r; i>m; i––) compexch(a[i-l], a[i]);

for (i=m+2; i<=r; i++)

{

int j=i;

Item v=a[i];

while (v<a[j-l])

{ a[j]=a[j-l]; j––;}

a[j]=v;

}

}

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

t = a[j]; a[j] = a[j-lj; a[j-l] = t;

за которым следует

t = a[j-l]; a[j-l] = a[j-2]; a[j-2] = t

и т.д. Значение t в этих двух последовательностях не изменяется, но при этом происходит бесполезная трата времени на его запоминание и последующее чтение с целью следующего обмена значениями. Программа 6.3 передвигает большие элементы на одну позицию вправо вместо того, чтобы воспользоваться операцией обмена, тем самым избегая напрасной траты времени.

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

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

6.4. Пузырьковая сортировка

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

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

Программа 6.4. Пузырьковая сортировка

Для каждого i от m до г-1 внутренний цикл (j) помещает минимальный элемент среди элементов последовательности a[i],..., a[r] в а[1], переходя от элемента к элементу справа налево и выполняя при этом операции сравнения значений соседних элементов и обмена местами следующих друг за другом элементов. Наименьший элемент беспрепятственно перемещается при всех таких операциях сравнения влево и "всплывает как и пузырек" в начале файла. Как и в случае сортировки методом выбора, в условиях которой индекс i перемещается по файлу слева направо, элементы слева от него находятся в своих окончательных позициях.

template <class Item>

void bubble (Item a[], int m, int r)

{ for (int i=m; i<r; i++)

for (int j=r; j>i; j--)

compexch(a[j-l], a[j]);

}

Быстродействие программы 6.4 можно повысить за счет экономной реализации внутреннего цикла, выполняя те же приемы, которые применялись в разделе 6.3 при разработке программы сортировки вставками (см. также упражнение 6.25). В самом деле, если сравнивать программные коды, то программа 6.4 оказывается практически идентичной неадаптивной сортировке вставками, реализованной в программе 6.1. Различия между ними состоят в том, что в условиях сортировки вставками внутренний цикл for продвигается вдоль левой (отсортированной) части массива, а в условиях пузырьковой сортировки – вдоль правой (не обязательно отсортированной) части массива.

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