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

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

Прежде всего, можно отказаться от выполнения

А S о R т I

А©о R Т I

A@S R Т I

АО® S Т I

А О R S ® I

Лфо R S Т А I ® О А© I N A©G I

R S О R N О

А®Е G

А А Е G

ДА Е G

А А Е G

AM Р AMP

AEG I NORST®AMP

R S Т X I ® N О R S T I M N O® R S I ® M N О P R A A E®G I L M N О P AAEEG t LMNOP

РИСУНОК 6.3. ПРИМЕР ВЫПОЛНЕНИЯ СОРТИРОВКИ ВСТАВКАМИ

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

операций compexch, если встречается ключ, который

не больше ключа вставляемого элемента, поскольку подмассив, находящийся слева, уже отсортирован. А именно, если справедливо условие аЦ-1] < a[j], то выполняя команду break, можно выйти из внутреннего цикла for в функции sort программы 6.1. В связи с таким изменением реализация превращается в адаптивную сортировку, благодаря чему быстродействие программы, примененной для сортировки ключей, упорядоченных случайным образом, повышается примерно в два раза (см. лемму 6.2).

Внеся усовершенствования, описанные в предыдущем 1параграфе, получаем два условия прекращения выполнения внутреннего цикла - можно изменить профамм-ный код и представить в виде цикла while, дабы отобразить этот факт наглядно. Менее очевидное улучшение реализации следует из того факта, что проверка условия у > 1 обычно оказывается излишней: и в самом деле, она достигает цели только в случае, когда вставляемый элемент является наименьшим из просмотренных к этому моменту, благодаря чему он достигает начала массива. Широко используемая альтернатива этому заключается в том, чтобы сохранять сортируемые ключи в элементах массива от а[1] до a[N], а сигнальный ключ (sentinel key) поместить в а[0], устанавливая его значение, по меньшей мере, не превышающим наименьшего ключа в сортируемом массиве. Теперь проверка того факта, что обнаружен ключ меньше сигнального, одновременно становится проверкой обоих представляющих интерес условий.

благодаря чему внутренний цикл становится меньше, а быстродействие программы повышается.

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

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

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

элементы а[1].....a[i-1] из отсортированного списка, которые по значению больше а[[],

после чего a[i] попадает в соответствующее место.

template <class Item>

void insertion (Item a[], int 1, int r) { int i;

for (i = r; i > 1; i-) coniexch (a [i-1] , a[i]); for (i = 1+2; i <= r; i++) { int j = i; Item v = a[i] ; while (V < a [j-1])

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

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

t = a[j]; a[j] = a[j-l]; a[j-l] = t; за которым следует

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

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

на одну позицию вправо вместо тою, чтобы воспользоваться операцией обмена, тем самым избегая напрасной траты времени.

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

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

Упражнения

> 6.15. В стиле рис. 6.3 показать, как сортируется учебный файл EASYQUES Т I О N методом вставок.

6.16. Разработать программную реализацию сортировки вставками, в которой во внутреннем цикле используется оператор while, завершающийся по одному из двух условий, описание которых приводится выше.

6.17. Для каждого из условий цикла while в упражнении 6.16 дать описание файла из N элементов, для которого в момент выхода из цикла это условие всегда ложно.

о 6.18. Является ли сортировка вставками устойчивой?

6.19. Привести пример неадаптивной реализации сортировки выбором, в основе которой лежит выявление минимального элемента, с программным кодом, подобным первому оператору цикла for в программе 6.3.

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

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