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

Содержание

ФУНКЦИОНАЛЬНАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВОТЧЕТ О ВЫПОЛНЕНИИ КОМАНДНОГО ЗАДАНИЯ НА ТЕМУ: “Реализация алгоритмов сортировки пузырьком Цель работы: изучить основные алгоритмы построения пирамидальной и пузырьковой сортировок. Ознакомится опытным путем с преимуществами Пирамидальная сортировкаПирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае Пирамидальная сортировка Достоинства и недостаткиДостоинства:· Имеет доказанную оценку худшего случая O(n log n).· Требует всего O(n log Код программы Структурная схема алгоритма пирамидальная сортировка Оценка сложностиАлгоритм сортировки работает в худшем, в среднем и в лучшем случае (то есть гарантированно) Сортировка пузырькомСортировка пузырьком — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, Сортировка пузырьком Достоинства и недостаткиДостоинство метода: не требуется дополнительных массивовНедостаток: время алгоритма пропорционально квадрату количества элементов (самый Код программы Структурная схема алгоритма пирамидальная сортировка Оценка сложностиАлгоритм сортировки работает в худшем, в среднем за O(n2), в лучшем случае за O(n) ВыводыПрактическая временная сложность сортировки пузырьком получилась несколько меньше теоретической, т.к. она оптимизирована, однако даже с

Слайды и текст этой презентации

Слайд 1 ФУНКЦИОНАЛЬНАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
ОТЧЕТ О ВЫПОЛНЕНИИ КОМАНДНОГО ЗАДАНИЯ НА ТЕМУ:
“Реализация

ФУНКЦИОНАЛЬНАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВОТЧЕТ О ВЫПОЛНЕНИИ КОМАНДНОГО ЗАДАНИЯ НА ТЕМУ: “Реализация алгоритмов сортировки пузырьком
алгоритмов сортировки пузырьком и пирамидальной сортировки на языке программирования Си”

Выполнили: студенты группы ИУ4-33Б -
Кондратив Владимир
Салуев Евгений
Сусликов Антон
Фомичев Павел
Шадрин Юрий
Яковлев Иван
Проверил: Терехов Владимир Владимирович

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ Н. Э. БАУМАНА


Слайд 2 Цель работы: изучить основные алгоритмы построения пирамидальной и пузырьковой сортировок. Ознакомится опытным

Цель работы: изучить основные алгоритмы построения пирамидальной и пузырьковой сортировок. Ознакомится опытным путем с преимуществами
путем с преимуществами и недостатками данных алгоритмов.

Задачи: разработать и реализовать на языке программирования Си алгоритмы пирамидальной и пузырьковой сортировок; для данных алгоритмов дать характеристику и построить структурные схемы согласно ГОСТ 19.701-90

Слайд 3 Пирамидальная сортировка
Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и

Пирамидальная сортировкаПирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае
в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Алгоритм пирамидальной сортировки можно рассматривать как улучшенную версию алгоритма сортировки выбором: он делит входные данные на отсортированную и несортированную области, а затем последовательно уменьшает несортированную область, извлекая самый большой элемент и перемещая его в сортированную область. Улучшение состоит в том, что используется бинарная куча, а не алгоритм линейного поиска, чтобы найти наибольшее значение.


Слайд 4 Пирамидальная сортировка

Пирамидальная сортировка

Слайд 5 Достоинства и недостатки
Достоинства:
· Имеет доказанную оценку худшего случая O(n log n).
· Требует

Достоинства и недостаткиДостоинства:· Имеет доказанную оценку худшего случая O(n log n).· Требует всего O(n log
всего O(n log n) дополнительной памяти.
Недостатки:
· Сложен в реализации.
· Неустойчив -- для обеспечения устойчивости нужно расширять ключ.
· На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
· На одном шаге выборку приходится делать хаотично по всей длине массива -- поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.


Слайд 6 Код программы

Код программы

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

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

Слайд 8 Оценка сложности
Алгоритм сортировки работает в худшем, в среднем и в лучшем случае

Оценка сложностиАлгоритм сортировки работает в худшем, в среднем и в лучшем случае (то есть гарантированно)
(то есть гарантированно) за O(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Слайд 9 Сортировка пузырьком
Сортировка пузырьком — простой алгоритм сортировки. Для понимания и реализации этот

Сортировка пузырькомСортировка пузырьком — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший,
алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n2).
Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.


Слайд 10 Сортировка пузырьком

Сортировка пузырьком

Слайд 11 Достоинства и недостатки
Достоинство метода: не требуется дополнительных массивов
Недостаток: время алгоритма пропорционально квадрату

Достоинства и недостаткиДостоинство метода: не требуется дополнительных массивовНедостаток: время алгоритма пропорционально квадрату количества элементов (самый
количества элементов (самый медленный способ сортировки)

Слайд 12 Код программы

Код программы

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

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

Слайд 14 Оценка сложности
Алгоритм сортировки работает в худшем, в среднем за O(n2), в лучшем

Оценка сложностиАлгоритм сортировки работает в худшем, в среднем за O(n2), в лучшем случае за O(n)
случае за O(n) операций при сортировке n элементов.

Слайд 15 Выводы
Практическая временная сложность сортировки пузырьком получилась несколько меньше теоретической, т.к. она оптимизирована,

ВыводыПрактическая временная сложность сортировки пузырьком получилась несколько меньше теоретической, т.к. она оптимизирована, однако даже с
однако даже с оптимизацией пузырьковая сортировка является более медленной по сравнению с пирамидальной.

  • Имя файла: realizatsiya-algoritmov-sortirovki-puzyrkom-i-piramidalnoy-sortirovki-na-yazyke-programmirovaniya-si.pptx
  • Количество просмотров: 15
  • Количество скачиваний: 0