Росдистант. Алгоритмы и структуры данных. Практическое задание №2

Практическое задание №2

1. Изучить методы сортировки: включением; выбором; обменом; Шелла; Хоара; пирамидальная.

2. Реализовать методы сортировки. Проанализировать время, затрачиваемое на каждый метод сортировки при одинаковом количестве измерений (количестве элементов в массиве).

3. Изучить алгоритмы поиска:

· в неупорядоченном массиве: линейный; быстрый линейный.

· в упорядоченном массиве: быстрый линейный; бинарный; блочный.

4. Реализовать алгоритмы поиска в одном файле в виде отдельных подпрограмм (функций).

Указания к выполнению работы.

При выполнении каждого задания необходимо написать программу на языке C++. Все алгоритмы сортировки реализовать в одном файле в виде отдельных подпрограмм (функций), которые сортируют один и тот же массив. Аналогично, все алгоритмы поиска реализовать в одном файле в виде отдельных функций. Для заполнения массива использовать генератор случайных чисел. С помощью функции clock() определить время, затраченное на каждый алгоритм сортировки. Разработать и программно реализовать средство для проведения экспериментов по определению временных характеристик алгоритмов сортировки. Провести эксперименты по определению временных характеристик алгоритмов сортировки. Результаты экспериментов представить в виде таблицы, клетки которой содержат время выполнения алгоритма сортировки массива с заданным количеством элементов. Провести эксперимент для упорядоченных, неупорядоченных и упорядоченных в обратном порядке массивов (для каждого типа массива заполнить отдельную таблицу). Построить графики функций временной сложности алгоритмов сортировки.

Выполнение задания необходимо проводить в соответствии с приведенными этапами:

• разработать графическую схему алгоритмов;

• записать алгоритмы на языке C++;

• разработать контрольный тест к программе;

• отладить программу;

• представить отчет по работе.

Требования к отчету

Структура отчета должна соответствовать приведённым выше этапам:

• Титульный лист.

• Алгоритм решения задачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80).

• Листинг программы.

• Контрольный тест.

• Выводы.