Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька (стр. 3 из 5)

Теперь предположим, что дана пирамида с элементами hl+1,..., hr для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду hl,..., hr. Возьмем, например, исходную пирамиду h1,...,h7, показанную на рис.2, и расширим эту пирамиду "влево", добавив элемент h1=44. Новый элемент x сначала помещается в вершину дерева, а затем "просеивается" по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом формируется новая пирамида. На рисунке 8 продемонстрирована пирамидальная сортировка.

Рисунок 8. Процесс построения дерева

В данном примере значение 44 сначала меняется местами с 06, затем 12, и так формируется дерево. Далее процесс просеивания будем формулировать следующим образом: i, j - пара индексов, обозначающих элементы, которые нужно менять местами на каждом шаге просеивания.

Для восьми элементов из нашего примера минимальное и максимальное количества пересылок дают следующие исходные последовательности:

Мmin = 13 для последовательности

94, 67, 44, 55, 12, 42, 18, 6

Mmax=24 для последовательности

18, 42, 12, 44, 6, 55, 67, 94

Среднее число пересылок равно приблизительно nlog (n) /2 и отклонения от этого значения сравнительно малы.

2.5 Сортировка Шелла

На рисунке 9 продемонстрирована сортировка методом Шелла:

Рисунок 9. Сортировка Шелла

На первом проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на четыре позиции. Этот процесс называется 4-сортировкой. В нашем примере из восьми элементов каждая группа содержит ровно два элемента. После этого элементы вновь объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново. Этот процесс называется 2-сортировкой. Наконец на третьем проходе все элементы сортируются обычной 1-сортировкой включением.

На каждом шаге в сортировке участвует либо сравнительно мало элементов, либо они уже довольно хорошо упорядочены и требуют относительно мало перестановок. Очевидно, что этот метод дает упорядоченный массив, и также совершенно ясно, что каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки. Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращений обозначаются через

h1, h2,..., hn с условиями ht=1, hi+1 < hi.

Каждая h-сортировка программируется как сортировка простыми включениями, при этом, для того чтобы условие окончания поиска места включения было простым, используется барьер. Ясно, что каждая h-сортировка требует собственного барьера и что программа должна определять его место как можно проще.

2.6 Сложная сортировка обменом (сортировка Хоора)

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

Ожидаемое число обменов равно приблизительно n / 6. Быстрая сортировка все же имеет свои "подводные камни". Прежде всего, при небольших значениях n ее эффективность невелика, как и у всех усовершенствованных методов. Ее преимущество по сравнению с другими усовершенствованными методами заключается в том, что для сортировки уже разделенных небольших подмассивов легко можно применить какой-либо простой метод.

2.7 Общий анализ приведенных сортировок

Приведем выводы по простым методам сортировки:

Время сортировки пропорционально квадрату размерности массива

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

Несмотря на плохое быстродействие, простые алгоритмы сортировки следует применять при малой размерности сортируемого массива.

Наряду с простыми методами сортировки существуют более сложные, обеспечивающие время сортировки пропорциональное

.

При больших размерностях массива они обеспечивают существенный выигрыш.

Сравним простые и сложные методы сортировки по производительности:

Таблица 1. Сравнительные показатели производительности различных методов сортировки массивов

Простые методы сортировки
Метод сортировки	Время сортировки для размера 256, миллисекунд	Время сортировки для размера 512, миллисекунд	Соотношение методов по производительности (относительное время сортировки)
Вставками (метод простых вставок)	356	1444	1
Выбором	509	1956	1.3
Обменом (пузырек)	1026	4054	3
Сложные методы сортировки
Обменом (Хоора)	60	116	1
Выбором (с помощью двоичного дерева	110	241	1.7
Вставками (Шелла)	127	349	2.1

Из приведенных в таблице данных следует, в частности, для относительно небольшого массива в 512 элементов:

Худшая по производительности из простых сортировок (сортировка обменом) работает в 35 раз медленнее быстрой сортировки Хоора.

Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в 4.2 раза чем худшая по производительности из сложных сортировок (сортировка Шелла).

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

2.8 Теоретическое сравнение сортировок методом простых вставок и методом пузырька

Выполним по рекомендованной литературе теоретическое сравнение алгоритмов сортировок, рассматриваемых в данном курсовом проекте. Основным критерием сравнения сортировок является их эффективность, то есть число сравнений и число пересылок. Данные показатели также влияют на время сортировки. Укажем основные формулы, использующиеся для вычисления эффективности данных сортировок:

− число сравнений ключей элементов при i-ом просеивании;

−минимальное число сравнений ключей;

− максимальное число сравнений ключей;

− среднее число сравнений ключей;

− число пересылок (присваиваний) элементов при i-ом просеивании;

− минимальное число пересылок

− максимальное число пересылок

− среднее число пересылок

− размер массива;

Рассмотрим сортировку методом простых вставок

Рассмотрим сортировку методом пузырька

На основе данных методических формул составим сравнительную таблицу для сортировок методом простых вставок и методом пузырька:

Таблица 2. Сравнительный анализ сортировок методом простых вставок и методом пузырька

Размер массива	Метод простых вставок		Метод пузырька
	Число сравнений ключей (среднее значение)	Число пересылок (среднее значение)	Число сравнений ключей (среднее значение)	Число пересылок (среднее значение)
32	263	329	256	384
64	1039	1163	1024	1536
128	4127	4379	4096	6144
256	16447	16953	16384	24576
512	65663	131835	65536	98304
1024	262399	264443	262144	393216

На основе полученных в таблице 2 значений составим сравнительные графики, для числа сравнений ключей и для числа пересылок по обоим методам сортировки: