Алгоритмы сортировки выбором, вставками и пузырьковая сортировка по времени выполнения находятся в квадратичной зависимости от числа элементов как в наиболее трудных, так и в обычных случаях, но в то же время они не нуждаются в дополнительной памяти. Таким образом, время их выполнения отличается только постоянным коэффициентом пропорциональ- ности этой зависимости, хотя принципы их работы существенно различаются, о чем свидетельствуют рис. 22, 23 и 24 [3].
В общем случае время выполнения алгоритма сортировки пропорционально количеству операций сравнения, выполняемых этим алгоритмом, количеству перемещений или перемен местами элементов, а, возможно, и обоим сразу. В случае ввода данных, упорядоченных случайным образом, сравнение указанных методов сортировки предполагает изучение различий между соответствующими постоянными коэффициентами пропорциональности в зависимости от числа выполняемых операций сравнений и перемены сортируемых элементов местами, а также различий соответствующих постоянных коэффициентов пропорциональнос- ти в зависимости от числа выполняемых операций во внутренних циклах. В случае ввода данных со специальными характеристиками времена выполнения различных видов сортировок могут отличаться в большей степени, нежели по значениям указанных выше постоянных коэффициентов пропорциональности. В данном разделе подробно рассматриваются аналитические результаты, свидетельствующие в пользу этого заключения.
Лемма 2: Сортировка выбором производит примерно N2/2 операций сравнения и N операций обмена элементов местами.
Можно легко проверить это свойство на примере данных, приведенных на рис.19, представляющих собой таблицу размерностью N на N, на которой незаштрихованные буквы соответствуют сравнениям. Примерно половина элементов этой
таблицы не заштрихована, эти элементы расположены над диагональю. Каждому из N — 1 элементов (за исключением завершающего элемента) на диагонали соответствует операции обмена. Точнее, исследование программного кода показывает, что на каждое i от 1 до N -1 приходится одна операция обмена и N — i сравнений, так что всего производится N — 1 операций обмена и (N— 1) + (N — 2) +...+ 2+1 = N(N—l) /2 операций сравнения. Эти свойства сохраняются независимо от природы входных данных; единственный показатель сортировки выбором, зависящий от характера входных данных — это число операций присваивания переменной min новых значений. В наихудшем случае эта величина также становится квадратично зависимой, однако в среднем она характеризуется значением O(NlogN), так что мы вправе рассчитывать на то, что время выполнения сортировки выбором не чувствительно к природе входных данных.
Лемма 3: Сортировка вставками производит в среднем приблизительно N2/4 операций сравнения и N2/4 операций полуобмена элементов местами (перемещений) и в два раза больше операций в наихудшем случае.
Сортировка, реализованная программой 11, выполняет одно и то же число сравнений и перемещений. Так же, как и лемма 2, эта величина легко прослеживается на диаграмме размером N на N, представленной на рис. 20, которая подробно иллюстрирует работу алгоритма сортировки вставками. Здесь ведется подсчет элементов, лежащих под главной диагональю, причем в наихудшем случае учитываются все такие элементы. Можно ожидать, что для случайно распределенных входных данных каждый элемент пройдет в среднем половину пути назад, следовательно, необходимо учитывать только половину элементов, лежащих ниже
диагонали.
Лемма 4: Пузырьковая сортировка производит в среднем примерно N2/2 операций сравнения и N2/ 2 операций обмена как в среднем, так и в наихудшем случаях.
На i -м проходе пузырьковой сортировки нужно выполнить
N - i операций сравнения-обмена, следовательно, лемма 4 доказывается так же, как и случае сортировки выбором. Если алгоритм усовершенствован таким образом, что его выполнение прекращается, как только он обнаруживает, что файл уже отсортирован, то время его выполнения зависит от природы входных данных. Если файл уже отсортирован, то достаточно всего лишь одного прохода, однако i -й проход требует выполнения N — i операций сравнения и обмена, если файл отсортирован в обратном порядке. Как отмечалось ранее, эффективность сортировки для обычного случая ненамного выше, чем для самого трудного случая, однако анализ, благодаря которому был установлен этот факт, достаточно сложный.
И хотя понятие частично отсортированного файла уже по своей природе содержит в себе неопределенность, сортировка вставками и пузырьковая сортировка показывают хорошие результаты при работе с файлами, не обладающими произвольной организацией, которые довольно часто встречаются на практике. Применение в такого рода приложениях универсальных методов сортировки нецелесообразно. Например, рассмотрим, как работает сортировка вставками на файле, который уже является отсортированным. Сразу же выясняется, что все элементы файла находятся на своих местах, а общие затраты времени на сортировку линейно зависят от числа элементов. Это же утверждение справедливо и в отношении пузырьковой сортировки, но для сортировки выбором эта зависимость остается квадратичной.
Определение 7: Инверсией называется пара ключей, которые нарушают порядок в файле.
Для подсчета количества инверсий в файле для каждого элемента потребуется просуммировать число элементов слева, которые превосходят его по величине (мы будем называть это значение числом инверсий, соответствующих выбранному элементу). Но это число есть в точности расстояние, которое должны пройти эти элементы во время сортировки вставками. В частично отсортированном файле меньше инверсий, чем в произвольно упорядоченном файле.
Существуют такие типы частично отсортированных файлов, в которых каждый элемент находится достаточно близко к своей окончательной позиции. Например, некоторые игроки в карты сортируют имеющиеся у них на руках карты, сначала располагая их по масти, тем самым помещая близко к их окончательным позициям, а затем упорядочивают карты каждой масти по старшинству. Далее мы рассмотрим некоторое число методов сортировки, которые действуют примерно таким же образом — на начальной стадии они размещают элементы вблизи окончательных позиций, в результате чего образуется частично упорядоченный файл, в котором каждый элемент расположен недалеко от той позиции, которую он в конечном итоге должен занять. Высокую эффективность при сортировке таких файлов демонстрируют сортировка вставками и пузырьковая сортировка (но не сортировка выбором).
Рис.22. Динамические характеристики сортировок выбором и вставками
Рис.23. Операция сортировок и обмена в условиях элементарных методов сортировки
Лемма 5: Методы вставок и пузырьковой сортировки выполняют линейно зависимое от N число операций сравнения и обмена при сортировке файлов с не более чем постоянным числом инверсий, приходящихся на каждый элемент.
Как было только что отмечено, время выполнения сортировки вставками прямо пропорционально количеству инверсий в сортируемом файле. Что касается пузырьковой сортировки (здесь мы ссылаемся на программу 12, скорректированную таким образом, что ее выполнение прекращается, как только завершена сортировка файла), то доказательство подобного утверждения требует дополнительных рассуждений. Каждый проход пузырьковой сортировки уменьшает справа от любого элемента число меньших его элементов точно на 1 (если, естественно, это число не было равным 0), следовательно, пузырьковая сортировка использует не более чем постоянное число проходов для типов файлов, которые сейчас рассматриваются (т.е. частично упорядоченных), и поэтому количество выполняемых операций сравнения и обмена линейно зависит от N.
Другой тип частично отсортированных файлов может быть получен за счет добавления нескольких элементов к уже отсортированному файлу либо путем соответствующего изменения ключей нескольких элементов отсортированного файла. Подобные типы файлов наиболее часто встречаются в приложениях сортировки. Для таких файлов наиболее эффективным является сортировка вставками: сортировка выбором и пузырьковая сортировка таковыми не являются.
Рис.24. Динамические характеристики двух пузырьковых сортировок
Таблица 1. Эмпирические исследования элементарных алгоритмов сортировки
На файлах небольших размеров быстродействие сортировки вставками и выбором примерно в два раза выше, чем у пузырьковой сортировки, но время выполнения этого вида сортировки находится в квадратичной зависимости от размера файла (если размер файла возрастает в 2 раза, то время его сортировки возрастает в 4 раза). Ни
один из этих методов не следует использовать для сортировки больших случайно упорядоченных файлов — например, соответствующие показатели, относящиеся к алгоритму сортировки методом Шелла (см. раздел 5.6), возрастают менее чем в 2 раза. В тех случаях, когда выполнение операций сравнения сопряжено с большими затратами, — например, когда ключи представлены в виде строк — сортировка вставками работает гораздо быстрее, чем два других рассматриваемых способа, поскольку в условиях сортировки вставками выполняется меньшее количество операций
сравнения. Здесь мы не обсуждаем ситуации, когда дорогостоящими являются операции обмена; в таких случаях наилучшей является сортировка выбором.
Ключи:
S Сортировка выбором (программа 10)
I* Сортировка вставками на основе операции обмена (программа 9)
I* Сортировка вставками (программа 11)
В Пузырьковая сортировка(программа 12)
В* Шейкер-сортировка
Лемма 6: Сортировка вставками использует линейно зависимое (от N) число операций сравнения и обмена для файлов с не более чем постоянным количеством элементов, которые имеют более чем постоянное число соответствующих инверсий.
Время выполнения сортировки вставками зависит от общего числа инверсий в файле и не зависит от того, каким образом эти инверсии распределены в файле.
Чтобы сделать выводы относительно времени выполнения сортировок на сновании лемм 2—6, необходимо проанализировать затраты на операции сравнения и обмена, а этот фактор, в свою очередь, зависит от размеров элементов и ключей (см. таблицу 1). Например, если элементы представляют собой ключи в виде одного слова, то операция обмена (требующая четырех доступов к массиву) должна стоить в два раза дороже операции сравнения. В такой ситуации значения времени, затрачиваемого на выполнение сортировок вставками и выбором, можно в первом приближении считать соизмеримыми, в то время как пузырьковая сортировка выполняется медленнее. Но если сами элементы больше ключей, то лучше всего подходит сортировка выбором.
Лемма 7: Время выполнения сортировки выбором линейно зависит от размеров файлов с большими элементами и малыми ключами.
Пусть М есть отношение размера элемента к размеру ключа. Тогда можно предположить, что стоимость операции сравнения составляет 1 единицу времени, а стоимость операции обмена — М единиц времени. Сортировка выбором затрачивает на операции сравнения примерно N2/ 2 единиц времени и порядка NM единиц
времени на операции обмена. Если М больше постоянного кратного N, то произведение NM превосходит N2, так что время выполнения сортировки пропорционально произведению NM, которое, в свою очередь, пропорционально количеству времени, которое требуется для перемещения всех данных.
Например, если требуется выполнить сортировку 1000 элементов, каждый из который состоит из ключа в виде одного слова и 1000 слов данных, а мы фактически должны переупорядочить эти элементы, то трудно найти что-либо лучшее, чем сортировка выбором, поскольку основной составляющей времени выполнения для нее будет стоимость перемещения в конечном итоге 1 миллиона слов данных.