Выполнили: студенты группы ИУ4-33Б -
Кондратив Владимир
Салуев Евгений
Сусликов Антон
Фомичев Павел
Шадрин Юрий
Яковлев Иван
Проверил: Терехов Владимир Владимирович
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ Н. Э. БАУМАНА
Презентация на тему Реализация алгоритмов сортировки пузырьком и пирамидальной сортировки на языке программирования Си
Содержание
- 1. Реализация алгоритмов сортировки пузырьком и пирамидальной сортировки на языке программирования Си
- 2. Цель работы: изучить основные алгоритмы построения пирамидальной и
- 3. Пирамидальная сортировкаПирамидальная сортировка — алгоритм сортировки, работающий в
- 4. Пирамидальная сортировка
- 5. Достоинства и недостаткиДостоинства:· Имеет доказанную оценку худшего случая
- 6. Код программы
- 7. Структурная схема алгоритма пирамидальная сортировка
- 8. Оценка сложностиАлгоритм сортировки работает в худшем, в среднем
- 9. Сортировка пузырькомСортировка пузырьком — простой алгоритм сортировки. Для
- 10. Сортировка пузырьком
- 11. Достоинства и недостаткиДостоинство метода: не требуется дополнительных массивовНедостаток:
- 12. Код программы
- 13. Структурная схема алгоритма пирамидальная сортировка
- 14. Оценка сложностиАлгоритм сортировки работает в худшем, в среднем
- 15. ВыводыПрактическая временная сложность сортировки пузырьком получилась несколько меньше
- 16. Скачать презентацию
- 17. Похожие презентации
Слайды и текст этой презентации
Слайд 1
ФУНКЦИОНАЛЬНАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
ОТЧЕТ О ВЫПОЛНЕНИИ КОМАНДНОГО ЗАДАНИЯ НА ТЕМУ:
“Реализация
алгоритмов сортировки пузырьком и пирамидальной сортировки на языке программирования Си”
Слайд 2 Цель работы: изучить основные алгоритмы построения пирамидальной и пузырьковой сортировок. Ознакомится опытным
путем с преимуществами и недостатками данных алгоритмов.
Задачи: разработать и реализовать на языке программирования Си алгоритмы пирамидальной и пузырьковой сортировок; для данных алгоритмов дать характеристику и построить структурные схемы согласно ГОСТ 19.701-90
Задачи: разработать и реализовать на языке программирования Си алгоритмы пирамидальной и пузырьковой сортировок; для данных алгоритмов дать характеристику и построить структурные схемы согласно ГОСТ 19.701-90
Слайд 3
Пирамидальная сортировка
Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и
в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Алгоритм пирамидальной сортировки можно рассматривать как улучшенную версию алгоритма сортировки выбором: он делит входные данные на отсортированную и несортированную области, а затем последовательно уменьшает несортированную область, извлекая самый большой элемент и перемещая его в сортированную область. Улучшение состоит в том, что используется бинарная куча, а не алгоритм линейного поиска, чтобы найти наибольшее значение.
Алгоритм пирамидальной сортировки можно рассматривать как улучшенную версию алгоритма сортировки выбором: он делит входные данные на отсортированную и несортированную области, а затем последовательно уменьшает несортированную область, извлекая самый большой элемент и перемещая его в сортированную область. Улучшение состоит в том, что используется бинарная куча, а не алгоритм линейного поиска, чтобы найти наибольшее значение.
Слайд 5
Достоинства и недостатки
Достоинства:
· Имеет доказанную оценку худшего случая O(n log n).
· Требует
всего O(n log n) дополнительной памяти.
Недостатки:
· Сложен в реализации.
· Неустойчив -- для обеспечения устойчивости нужно расширять ключ.
· На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
· На одном шаге выборку приходится делать хаотично по всей длине массива -- поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
Недостатки:
· Сложен в реализации.
· Неустойчив -- для обеспечения устойчивости нужно расширять ключ.
· На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
· На одном шаге выборку приходится делать хаотично по всей длине массива -- поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
Слайд 8
Оценка сложности
Алгоритм сортировки работает в худшем, в среднем и в лучшем случае
(то есть гарантированно) за O(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Слайд 9
Сортировка пузырьком
Сортировка пузырьком — простой алгоритм сортировки. Для понимания и реализации этот
алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n2).
Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.
Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.
Слайд 11
Достоинства и недостатки
Достоинство метода: не требуется дополнительных массивов
Недостаток: время алгоритма пропорционально квадрату
количества элементов (самый медленный способ сортировки)
Слайд 14
Оценка сложности
Алгоритм сортировки работает в худшем, в среднем за O(n2), в лучшем
случае за O(n) операций при сортировке n элементов.
Слайд 15
Выводы
Практическая временная сложность сортировки пузырьком получилась несколько меньше теоретической, т.к. она оптимизирована,
однако даже с оптимизацией пузырьковая сортировка является более медленной по сравнению с пирамидальной.
