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

32-разрядные целочисленные ключи ключи в виде строк

Ключи:

S Сортировка выбором (программа 6.2)

Г Сортировка вставками на основе операций обмена (программа 6.1)

I Сортировка вставками (программа 6.3)

В Пузырьковая сортировка (программа 6.4)

В* Шейкер-сортировка (упражнение 6.30)

Лемма 6.5. Сортировка вставками использует линейно зависимое (от N) число операций сравнения и обмена для файлов с не более чем постоянным количеством элементов, которые имеют более чем постоянное число соответствующих инверсий.

Время выполнения сортировки вставками зависит от общего числа инверсий в файле и не зависит от того, каким образом эти инверсии распределены в файле.

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

Лемма 6.6. Время выполнения сортировки выбором линейно зависит от размеров файлов с большими элементами и малыми ключами.

Пусть М есть отношение размера элемента к размеру ключа. Тогда можно предположить, что стоимость операции сравнения составляет 1 единицу времени, а стоимость операции обмена - М единиц времени. Сортировка выбором затрачивает на операции сравнения примерно N/2 единиц времени и порядка NM единиц времени на операции обмена. Если М больше постоянного кратного N, то произ-

ведение NM превосходит N, так что время выполнения сортировки пропорционально произведению NM, которое, в свою очередь, пропорционально количеству времени, которое требуется для перемещения всех данных.

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

Упражнения

> 6.26. Какой из трех элементарных методов (сортировка выбором, сортировка вставками и пузырьковая сортировка) выполняется быстрее на файле, элементы которого снабжены идентичными ключами?

6.27. Какой из трех перечисленных выше элементарных методов выполняется быстрее на файле, упорядоченном в обратном порядке?

6.28. Дать пример файла из 10 элементов (использовать ключи от А до J), в процессе сортировки которого пузырьковая сортировка выполняет меньше операций сравнения, чем метод вставок, либо же доказать, что такой файл не существует.

6.29, Показать, что каждый проход пузырьковой сортировки уменьшает ровно на 1 число элементов слева от текущего, превосходящих его по значению (естественно, если это число не равно 0).

6.30. Реализовать вариант пузырьковой сортировки, который попеременно применяет проходы по данным слева направо и справа налево. Этот (более быстродействующий, но в то же время более сложный) алгоритм называется шейкер-сор-тировкой {shaker sort) (см. рис.6.7).

6.31. Показать, что лемма 6.5 не характерна для шейкер-сортировки (см. упражнение 6.30).

6.32. Напишите программу сортировки на PostScript (см. раздел 4.3) и воспользуйтесь полученной программной реализацией для построения диаграмм типа 6.5 - 6.7. Можно применить рекурсивную реализацию или обратиться к справочной литературе для изучения циклов и массивов PostScript.

б.б. Сортировка методом Шелла

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

Идея заключается в переупорядочении файла таким образом, чтобы придать ему следующее свойство: совокупность А-ых элементов исходного файла (начиная с любого) образует отсортированный файл. В таком случае говорят, что файл h-упорядочен (h-sorted). Другими словами, -упорядоченный файл представляет собой h независимо отсортированных взаимно проникающих друг в друга файлов. В процессе Л-сортировки при достаточно больших значениях h можно менять местами элементы массива, расположенные достаточно далеко друг от друга, и тем самым ускорить последующую Л-сортировку при меньших значениях И. Использование такого рода процедуры для любой последовательности значений И, которая заканчивается единицей, завершается получением упорядоченного файла: именно в этом и заключается суть сортировки методом Шелла.

Один из способов реализации сортировки методом Шелла заключается в том, что для каждого И независимо используется сортировка вставками на каждом из h подфайлов. Несмотря на очевидную простоту этого процесса, возможен еще более простой подход именно благодаря тому, что подфайлы независимы. В процессе А-сортировки файла мы просто вставляем элемент среди предшествующих ему элементов в соответствующем Л-подфайле, перемещая большие по значению элементы в право (см, рис.6.8). Эта задача решается путем использования программы сортировки вставками, при которой каждый шаг перемещения по файлу в сторону увеличения или уменьшения равен h, но не равен 1. С учетом данного обстоятельства программная реализация сортировки методом Шелла сводится всего лишь к тому, что для каждого значения шага осуществляется проход по файлу, характер>ный для сортировки вставками, аналогичный реализованному в программе 6.5. Работа программы показана на рис. 6.9.

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

РИСУНОК 6.8. ВЗАИМНО ПРОНИКАЮЩИЕ 4-СОРТИРОВКИ

В верхней части данной диаграммы показан процесс 4-сортировки файла, состоящего из 15 элементов, сначала выполняется сортировка вставками подфайла, содержащего элементы в позициях О, 4, 8, 12, затем сортировка вставками подфайла на позициях 1,

5, 9, 13, далее сортировка вставками подфайла в позициях 2,

6, 10, 14 и, наконец, сортировка вставками подфайла в позициях 3,

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