Практическое задание №2
1. Изучить методы сортировки: включением; выбором; обменом; Шелла; Хоара; пирамидальная.
2. Реализовать методы сортировки. Проанализировать время, затрачиваемое на каждый метод сортировки при одинаковом количестве измерений (количестве элементов в массиве).
3. Изучить алгоритмы поиска:
· в неупорядоченном массиве: линейный; быстрый линейный.
· в упорядоченном массиве: быстрый линейный; бинарный; блочный.
4. Реализовать алгоритмы поиска в одном файле в виде отдельных подпрограмм (функций).
Указания к выполнению работы.
При выполнении каждого задания необходимо написать программу на языке C++. Все алгоритмы сортировки реализовать в одном файле в виде отдельных подпрограмм (функций), которые сортируют один и тот же массив. Аналогично, все алгоритмы поиска реализовать в одном файле в виде отдельных функций. Для заполнения массива использовать генератор случайных чисел. С помощью функции clock() определить время, затраченное на каждый алгоритм сортировки. Разработать и программно реализовать средство для проведения экспериментов по определению временных характеристик алгоритмов сортировки. Провести эксперименты по определению временных характеристик алгоритмов сортировки. Результаты экспериментов представить в виде таблицы, клетки которой содержат время выполнения алгоритма сортировки массива с заданным количеством элементов. Провести эксперимент для упорядоченных, неупорядоченных и упорядоченных в обратном порядке массивов (для каждого типа массива заполнить отдельную таблицу). Построить графики функций временной сложности алгоритмов сортировки.
Выполнение задания необходимо проводить в соответствии с приведенными этапами:
• разработать графическую схему алгоритмов;
• записать алгоритмы на языке C++;
• разработать контрольный тест к программе;
• отладить программу;
• представить отчет по работе.
Требования к отчету
Структура отчета должна соответствовать приведённым выше этапам:
• Титульный лист.
• Алгоритм решения задачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80).
• Листинг программы.
• Контрольный тест.
• Выводы.