Задание 3 (1). Тема Алгоритмы сортировки. Анализ алгоритмов

• Название: Тема Алгоритмы сортировки. Анализ алгоритмов
• Дата: 26.11.2022
• Размер: 18.22 Kb.
• Имя файла: Задание 3 (1).docx
• Тип: Документы; #813647

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

Тема 5.1. Алгоритмы сортировки. Анализ алгоритмов
Цель работы: изучить основные алгоритмы поиска и сортировки; провести сравнительный анализ различных алгоритмов поиска и сортировки.
Формулировка задания 3

1. 
   Изучите методы сортировки:
   

– включением;

– выбором;

– обменом;

– Шелла;

– Хоара;

– пирамидальную.

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

• 
  в неупорядоченном массиве:
  

– линейный;

– быстрый линейный;

• 
  в упорядоченном массиве:
  

– быстрый;

– бинарный;

– блочный;

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

5. Проанализируйте, на какой итерации при разных алгоритмах поиска было найдено искомое число.


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

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

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

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

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

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

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

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

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

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

• титульный лист;

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

• листинг программы;

• контрольный тест;

• выводы.