Структуры и алгоритмы обработки данных (ПЗ(х3))
ПРАКТИЧЕСКАЯ РАБОТА №2 СОРТИРОВКА ЧИСЛОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ Часть 2.1: УСОВЕРШЕНСТВОВАННЫЕ И БЫСТРЫЕ СОРТИРОВКИ. АСИМПТОТИЧЕСКАЯ СЛОЖНОСТЬ АЛГОРИТМА ПРОСТОЙ СОРТИРОВКИ Цель: актуализировать знания алгоритмов сортировки числовой последовательности, получить практические умения и навыки по анализу вычислительной сложности алгоритмов сортировки и определению наиболее эффективного алгоритма. Задание 1. Эмпирическая оценка эффективности простого, ускоренного и быстрого алгоритмов сортировки Требования по выполнению задания 1. Разработать алгоритм ускоренной сортировки, определённой в варианте (приложение 1), реализовать код на языке С++. Сформировать таблицу 1.1 результатов эмпирической оценки сложности сортировки по формату табл. 1 для массива, заполненного случайными числами1. 2. Определить ёмкостную сложность алгоритма ускоренной сортировки. Таблица 1. Сводная таблица результатов n время, мс Сп Мп Тп=Cп+Mп 1000 2000 5000 10000 100000 200000 500000 1000000 3. Разработать алгоритм быстрой сортировки, определённой в варианте (приложение 1), реализовать код на языке С++. Сформировать таблицу 1.2 результатов эмпирической оценки сортировки по формату табл. 1 для массива, заполненного случайными числами. 4. Определить ёмкостную сложность алгоритма быстрой сортировки. 5. Добавьте в отчёт данные по работе любого из алгоритмов простой сортировки в среднем случае, полученные в предыдущей практической работе (в отчёте – таблица 1.3). 1 Для соблюдения равенства условий при анализе эффективности, случайные массивы всех заданных длин должны быть одними и теми же для всех рассматриваемых алгоритмов. СиАОД-2.1 6. Представить на общем сравнительном графике зависимости Тп(n)=Cф+Mф для трёх анализируемых алгоритмов. 7. На основе сравнения полученных данных определите наиболее эффективный из трёх алгоритмов в среднем случае (отдельно для небольших массивов при n до 1000 и для больших массивов с n>1000). 8. По аналогии с п.п. 1, 3, 5 и 6 проанализируйте эффективность простой, ускоренной и быстрой сортировок на массивах, отсортированных а) строго в убывающем и б) строго возрастающем порядке значений элементов. Заполнить по этим данным для каждого алгоритма соответствующие таблицы 1.4, 1.5, 1.6 по формату табл. 1, также сравнительный график. 9. Сделайте вывод о зависимости (или независимости) алгоритмов сортировок от исходной упорядоченности массива на основе результатов, представленных в таблицах. Задание 2. Асимптотический анализ сложности алгоритмов Требования по выполнению задания 1. Из материалов предыдущей практической работы приведите в отчёте формулы Тт(n) функций роста алгоритма простой сортировки в лучшем и худшем случае (того же алгоритма, что и в задании 1). 2. На основе определений соответствующих нотаций получите асимптотическую оценку вычислительной сложности простого алгоритма сортировки2 в О-нотации (оценка сверху) для анализа худшего случая в Ω-нотации (оценка снизу) для анализа лучшего случая.









