Каталог Рефератов - Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

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

ри данной сортировке общее число сравнений приблизительно равно

При этом требуется количество проходов по данным P

Рассмотрим пошагово сортировку методом простых вставок на рис.5

Рисунок 5. Пример сортировки массива простыми включениями

Число Ci сравнений ключей при i-м просеивании составляет самое большее i-1, самое меньшее 1 и, если предположить, что все перестановки n ключей равновероятны, в среднем равно i/2. Число Мi пересылок (присваиваний) равно Ci+2 (учитывая барьер). Поэтому общее число сравнений и пересылок есть

Cmin = n-1 Mmin = 2 (n-1)

Cср. = (n2+n-2) /4 Mср. = (n2+9n-10) /4

Cmax = ( (n2+n) - 1) /2 Mmax = (n2+3n-4) /2.

Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a [1],…, a [i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения.

2.2 Сортировка массива простым обменом ("метод пузырька")
Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы массива. Пример сортировки методом "пузырька" приведен на рисунке 6.

Очевидно, что в наихудшем случае, когда минимальное значение ключа элемента имеется у самого правого элемента, число просмотров равно size ?1.

12 44 18 55

12 42 44 18 06 55 67 94

18 44

06 44

12 42 18 06 44 55 67 94

18 42

06 42

12 18 06 42 44 55 67 94

06 18

12 06 18 42 44 55 67 94

06 12

06 12 18 42 44 55 67 94

Рисунок 6. Пример сортировки массива простым обменом

Эффективность сортировки. За один проход среднее число сравнений равно С=size/2. При этом среднее число возможных пересылок М=1.5*С (в предположении, что проверяемое условие выполняется в половине случаев). Минимальное количество проходов равно1, максимальное ? size -1, а среднее ? size/2.

Следовательно,

2.3 Сортировка массива сложным выбором (с помощью двоичного дерева)

Метод сортировки основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Понятно, что поиск наименьшего ключа из n элементов требует n-1 сравнений, а поиск его среди n-1 элементов n-2 сравнений. Улучшить сортировку выбором можно в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью n/2 сравнений можно определить наименьший ключ из каждой пары, при помощи следующих n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т.д. Наконец при помощи всего n-1 сравнений мы можем построить дерево, как показано на рис.1, выбора и определит корень, как наименьший ключ. На втором шаге мы спускаемся по пути, указанном наименьшим ключом, и исключаем его, последовательно заменяя либо на "дыру" (или ключ бесконечность), либо на элемент, находящийся на противоположной ветви промежуточного узла Элемент оказывается в корне дерева, вновь имеет наименьший ключ среди оставшихся и может быть исключен. После n таких шагов дерево становится пустым (т.е. состоит из "дыр"), и процесс сортировки закончен.

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

Рисунок 7. Сортировка бинарным деревом

2.4 Пирамидальная сортировка
Пирамида определяется как последовательность ключей

hl, hl+1,..., hr, такая, что hi <= h2i, hi <= h2i+1

для всякого i =l,...,r/2. Если двоичное дерево представлено в виде массива, как показано на рис.1, то, следовательно, деревья сортировки на рис.2 и 3 являются пирамидами, и, в частности, элемент h1 пирамиды является ее наименьшим элементом h1 = min (h1... hn).

Теперь предположим, что дана пирамида с элементами 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-ом просеивании;

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

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

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

Страницы: 1, 2, 3

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.