Работа выполнена качественно, с учетом всех пожеланий
Информация о работе
Подробнее о работе
алгоритмы
- 67 страниц
- 2019 год
- 79 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Введение……………………………………………………..…………….………3
Глава 1. Основные понятия……………………………………..………..………5
1.1. Понятия алгоритма. Свойства алгоритма. Виды алгоритмов..……..…..…5
1.2. Понятие сортировки. Цель сортировки. Виды сортировок………..………8
1.3.Понятие комбинаторики. Виды комбинаторики. Основные формулы………………………………….………………………………………9
1.4.Виды сортрировок…………………………………………………………11
1.5.Задачи сортировки…………………………………………………………12
1.6. Нижние оценки сложности алгоритма сортировки сравнением………16
1.7. Алгоритм сортировки вставками и оценки времени его работы……..23
1.8. Алгоритм пузырьковой сортировки и оценки времени его работы….27
1.9. Алгоритм быстрой сортировки и оценки времени его работы……….30
1.10. Алгоритм пирамидальной сортировки и оценки его трудоёмкости…40
Глава 2. Программная реализация алгоритмов сортировки..……….……..49
2.1. Сортировка с помощью бинарного дерева……………………………..49
2.2. Пирамидальная сортировка………………………………………………53
2.3. Быстрая сортировка……………………………………………………….57
2.4. Сортировка прямым выбором……………………………………………61
2.5. Интерфейс ПО………………………………………………………………64
Заключение…………………………………………………...…………………..65
Список используемой литературы……………………………………………...66
1.1. Понятия алгоритма. Свойства алгоритма. Виды алгоритмов
Алгоритм - последовательность действий, которые необходимо выполнять исполнителю для того, чтобы разрешить поставленную задачу. Аль Хорезми является математиком, который разработал правила выполнения арифметических действий, поэтому определение алгоритма происходит от его имени. Изначально под алгоритмом поднимали правила выполнения четырех арифметических действий над числами. А уже в дальнейшем его стали применять для определения последовательности действий, которые приводят к решению задач. Объектами, которые используются в алгоритме, являются данные. Поэтому под алгоритмом в совокупности можно назвать набор правил, который преобразует исходные данные в результат.
У алгоритмов есть определенные свойства, которыми являются:
1. Детерминированность - получение точного, однозначного результата при вычислении процесса с исходными данными. Данное свойство наделяет алгоритм механическим характером,
2.
...
1.2 Понятие сортировки. Цель сортировки.
Сортировкой является процесс разделения объектов по виду или сорту. Однако программисты применяют данное определение в более узком смысле - для обозначения и перестановки предметов, располагающихся в порядке возрастания или убывания.
Сортировка - расстановка элементов массива в заданном порядке. А порядок может быть любым, для чисел в большинстве случаев применяются сортировку по возрастанию или убыванию значений.
Сортировка необходима для того, чтобы быстрее найти нужную информацию, к примеру, в словарях информации расположена по алфавитному порядку для более удобного поиска.
Программисты применяют несколько способов сортировки, наиболее популярными являются: простые, но медленно работающие и сложные, но быстрые.
Сортировка массивов необходима для того, чтобы переставлять элементы в определенном порядке с целью облегчения последующих поисков элементов в ассоциативном массиве.
...
1.5. Нижние оценки сложности алгоритма сортировки сравнением.
В первую очередь рассмотрим понятие бинарного дерева и его свойства.
Корневым деревом является граф, который можно определить рекурсивно следующим образом:
1. одна вершина является деревом, вершины - корень дерева отсутствие сыновей,
2. В случае если D1,...,Dk, k ≥ 1 являются деревьями с корнями, следовательно v1,...,vk, множество вершин данных деревьев не соприкасаются. Поэтому соединим рёбра новые вершины v с каждой вершиной v1,...,vk,. Полученный граф является корневым корнем v и под деревьями D1,...,Dk. , которые соответствуют вершинам v. Для данной вершины с сыновьями будут v1,...,vk, при этом вершины является родителями каждых этих вершин. Для остальных вершин сыновьями и родителями остаются прежние.
3. Любое корневое дерево формируется по вышеописанным правилам.
...
1.6. Алгоритм сортировки вставками и оценки времени его работы.
Данный алгоритм называют сортировкой вставками. Рассмотрим сущность данного метода:
Во-первых, ключ xi вставляется в нужную позицию среди других уже упорядоченных ключей x1,...,xi−1. Первый i ключей исходной последовательности будут упорядочены. Для того, чтобы найти позиции ключа xi сохраним его в дополнительной переменной x, алее ключи xj, j = i − 1,...,1 последовательно сравниваются с x и сдвигаются вправо. Процесс происходит до тех пор, пока x < xj. В найденную позицию помещается xi. Для того чтобы прекратить данный процесс, необходимо ввести дополнительный ключ x0, так как его значения меньше любого ключа xk, k = 1,...,n.
Осуществление данного алгоритма приведено в следующим псевдокоде.
Алгоритм сортировки вставками последовательности x1,...,xn x0 := −∞; for i = 2 to n do begin
x := xi; j := i − 1; while x < xj do begin xj+1 := xj; j := j − 1
end; xj+1 := x
end.
...
1.7. Алгоритм пузырьковой сортировки и оценки времени его работы.
Рассмотрим еще один вид сортировки - пузырьковая. Для того чтобы описать основную идею рассмотрим сортируемые ключи и запишем из в массив, который «расположен вертикально».
Для сортировки ключей с большими значениями, которые будут относительны заданного линейного порядка ≤, следует располагать выше ключей с меньшими значениями. Поэтому отсюда и название сортировки, то есть ключи с большими значения являются «пузырьками» и «всплывают» над ключами с меньшими показателями.
Проход начинается снизу вверх, поэтому первый ключ сравнивается с непосредственно следующим. В случае если наверху оказывается ключ с большими показателем, то ключи меняются местами. При встрече большего ключа верхний становиться эталоном для сравнения, и дальнейшие сравнения основываются на данной новом большем ключе. При первом проходе всего массива самый большой ключ оказывается наверху. То есть всплывает.
...
1.8. Алгоритм быстрой сортировки и оценки времени его работы.
Причиной медленной работы данных алгоритмов является сравнение и объемы между ключами входной последовательности x1,...,xn происходили для пар соседних элементов. При этом для того, чтобы поставить текущий ключ в необходимую позицию сортируемой последовательности необходимо произвести много операций. Так же можно ускорить процесс, сравнивая далекие показатели друг от друга ключи.
C. A. R. Hoare внедрил данную идею, при этом сократив средне время работы алгоритма по порядку nlgn. Называется данный метод QuickSort, что отражает действительность, так как алгоритм является довольно быстрым. Сортировка входной последовательности происходит на месте.
В данном алгоритме входная последовательность ключей записывается в массив x1,...,xn. Для того чтобы отсортировать элементы, выбирается элемент y, в качестве опорного, пока не будет конкретики в выборе его способа.
Элементы массива должны отражаться так:
1.
...
1.9. Алгоритм пирамидальной сортировки и оценки его трудоёмкости.
При сортировке n-элементной входной последовательности алгоритм пирамидальной сортировки9 требует времени работы в худшем и в среднем случае Θ(nlgn) и, следовательно, является оптимальным в классе алгоритмов сортировки сравнением.
Сортировка входной последовательности происходит на месте и не затрагивает дополнительную память. Структура данных отражается в виде пирамиды, рассмотрим более подробно.
Проанализируем произвольный массив A = (a1,...,an) размерности n. Сопряжем массив A с бинарным деревом DA, которое будет определяться так:
1) Вершиной дерева DA является элемент массива A.
2) Элемент a1 располагается в корне дерева.
3) i = 1,2,...,⌊n/2⌋ вершина ai имеет двух сыновей a2i – левый сын и a2i+1- правый сын, за исключением случая, когда n чётно и i = ⌊n/2⌋. В случае если n является четным, то у вершины an/2- только один сын. У других вершин дерева DA нет сыновей.
...
2.1. Сортировка с помощью бинарного дерева.
...
Рис. 8. Пирамидальная сортировка массива A = (7,4,3,9,8,6,1,10)
По лемме 11 имеем h = ⌊lgn⌋. Рассмотрим такое наибольшее положительное целое число h′, что вершины дерева DA, имеющие глубину, не превосходящюю h′, образуют полное бинарное дерево. Тогда h′ — высота этого дерева и h − 1 ≤ h′ ≤ h. Рассмотрим число i0 ≥ 0 итераций for-цикла, после которых элементы массива A на первых n − i0 местах образуют полное бинарное дерево высоты h′. Это дерево является пирамидой. Обозначим её через D′.
Отсортируем вершины дерева D′ в порядке возрастания значений. Значение 2h′ - тяжелая вершина.
Проанализируем количество m тяжелых вершин глубины меньшей h′ в дереве D′. Предки произвольной тяжелой вершины тоже являются тяжелыми, поэтому вершины бинарного дерева D′ образуют бинарное 2h′-вершинное дерево D′′ с тем же корнем.
Используя лемму 10 (v), получаем 2h′ = m + k ≥ 2k − 1, где k — число концевых вершин глубины h′ в дереве D′′. Поэтому выполняются неравенства
2h′−1 ≤ m ≤ 2h′.
...
2.4. Сортировка прямым выбором.
Листинг программы:
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#include
1. Кнут. Д. Искусство программирования для ЭВМ. Получисленные алгоритмы./ Д. Кнут./ 2-е издание. Серия: Искусство программирования. - Киев: «Вильямс»,2000
2. Иванов И.Б. Дискретная математика. Алгоритмы и программы
3. Электронный учебник. Параграф 64 [ Электронный ресурс]: http://uchebnik-rsh-3.ucoz.com/index/64_sortirovka/0-268
4. Алгоритмы и программы 1. [ Электронный ресурс]: http://www.studfiles.ru/preview/1499161/page:10/
5. Подбельский В.В., Фомин С.С. Программирование на языке Си. Учеб. пособие. М.: Финансы и статистика, 2004.382-385 с.
6. Алгоритмы построение и анализ, Т. Кормен, Ч. Лейзерсон, Р. Ривест. Москва 2007 г.
7. Алгоритмы дискретной математики, Л.Е. Захарова. Москва 2007 г.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
