Автор работы: Пользователь скрыл имя, 26 Января 2015 в 19:13, реферат
Основными операциями, выполняемыми над массивами, являются упорядочение (сортировка) записей и поиск в массиве записи по заданному условию( по ключу ). Сортировка является операцией расстановки записей массива в определенном порядке в соответствии с некоторым критерием упорядочения. Сортировка осуществляется в соответствии со значением ключей всех записей (напр., упорядочение фамилий по алфавиту или чисел по возрастанию ).
Введение
1. Метод "Пузырька".
2. Метод Шелла.
3. Обменная сортировка с разделением (Quicksort).
4. Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort).
5. Гномья сортировка (англ. Gnome sort).
6. Сортировка вставками — простой алгоритм сортировки.
7. Блочная сортировка.
8. Сортировка подсчётом.
9. Сортировка слиянием.
10. Сортировка с помощью двоичного дерева.
11.Сортировка выбором.
12. Пирамидальная сортировка (англ. Heapsort) .
13. Быстрая сортировка.
Заключение.
Источники информации.
Алгоритм
1. Построение двоичного дерева.
2. Сборка результирующего
массива путём обхода узлов
в необходимом порядке
Эффективность
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)). Соответственно, для n объектов сложность будет составлять O(n log(n)), что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n), что может привести к общей сложности порядка O(n²).
При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.
Примеры реализации
Итеративная
Следующий алгоритм (немного модифицирован для избежания переполнения) из Стандарта Pascal [1] Никлауса Вирта:
min := 1;
max := N; {array size: var A : array [1..N] of integer}
repeat
mid := min + (max - min) div 2;
if x > A[mid] then
min := mid + 1
else
max := mid - 1;
until (A[mid] = x) or (min > max)
11.Сортировка выбором .
Алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.
Алгоритм
Шаги алгоритма:
находим минимальное значение в текущем списке
производим обмен этого значения со значением на первой неотсортированной позиции
теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.
12.Пирамидальная сортировка (англ. Heapsort).
Алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.[1] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.
Алгоритм
Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое двоичное дерево, у которого выполнены условия:
1. Каждый лист имеет глубину либо d, либо d ? 1, d — максимальная глубина дерева.
2. Значение в любой вершине больше, чем значения её потомков.
Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] —Array[2i] и Array[2i+1].
Алгоритм сортировки будет состоять из двух основных шагов:
Выстраиваем элементы массива в виде сортирующего дерева:
при .
Этот шаг требует O(n) операций.
2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.
Этот шаг требует O(nlogn) операций.
Достоинства и недостатки
Достоинства
- Имеет доказанную оценку худшего случая O(nlogn).
- Требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).
Недостатки
- Сложен в реализации.
- Неустойчив — для
обеспечения устойчивости
- На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
- На одном шаге выборку
приходится делать хаотично по
всей длине массива — поэтому
алгоритм плохо сочетается с
кэшированием и подкачкой
Сортировка слиянием при расходе памяти O(n) быстрее ( ) с меньшей константой) и не подвержена деградации на неудачных данных.
Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.
13. Быстрая сортировка.
(англ. quicksort), часто называемая
qsort по имени реализации в
Краткое описание алгоритма
выбрать элемент, называемый опорным.
сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
повторить рекурсивно для «меньших» и «больших».
Алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
Вычисляется индекс опорного элемента m.
Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.
Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.
Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты.
Заключение.
В работы был проведен обзор существующих алгоритмов сортировки, в том числе оценка их эффективности. Был сделан вывод, что методы сложных сортировок (сортировки использующие копирование массива), более эффективны в целом, чем методы простых сортировок. Причем самая эффективная из простых сортировок менее эффективна, чем худшая по производительности из сложных сортировок.
Также было выполнено теоретическое сравнение эффективности алгоритмов сортировок. В ходе теоретического сравнения было выявлено, что сортировка методом вставок эффективнее сортировки методом пузырька, благодаря меньшему числу сравнений ключей и меньшему количеству пересылок.
Данные функции интегрированы в разработанное приложение, с помощью которого можно создать массив с заданным количеством элементов, отсортировать его любым из рассмотренных в методом сортировки и узнать время сортировки массива.
Источники информации: