ПРАКТИЧЕСКАЯ РАБОТА №1

Практическая работа №1 (2 часа)

Тема: «Оценка сложности алгоритмов сортировки»

Цель: Изучение и исследование основных алгоритмов сортировки данных, размещенных в оперативной памяти

Задачи:
1.                ппп
2.
Формируемые компетенции: ПК 1.1., ОК 1-10.
Материально-техническое обеспечение: доска, учебники, сборник практических работ, комплект нормативных документов; классификация объектов технического регулирования, Общероссийский классификатор стандартов (ОКС), приложение 2-3.
Обеспечивающие средства: компьютеры, совместимые с IBM PC.

Ход работы:
1.                   Проверка готовности к ПР: тестирование
2.                   Выполнение заданий
3.                   Заполнение отчета

Задания:
1.     1.           Написать программу, включающую следующие функции:
1)                   сортировка 1;
2)                   сортировка 2;
3)                   проверка массива на упорядоченность;
2.     В основной программе выполнить в зависимости от выбранного в диалоге способ заполнения массива
1)                   заполнение массива случайными числами;
2)                    ввод массива с клавиатуры для небольших массивов.
3.     Подсчитать характеристики сортировок (время, число сравнений, число обменов или сдвигов) для каждого из алгоритмов и время для стандартной сортировки и оформить полученные данные в виде таблиц.
4.     Построить графики для характеристик (время) и сравнить время выполнения
5.     . Провести анализ и оценку временной сложности алгоритма

В пп.1.1-2 продемонстрировать соответствующую сортировку для массива из 10-15 элементов. Вывести на экран исходный массив и промежуточные результаты каждого прохода.
Программа должна решать указанную задачу, динамически создавая в функции main массив для хранения данных на требуемое количество элементов и заполняя его числами. При реализации алгоритма нельзя создавать ни в функции main, ни в других функциях дополнительные рабочие массивы, длина которых явно или неявно зависела бы от длины исходных данных.
Программа должна содержать функции, получающие в качестве параметров указатель на начальный элемент массива и длину массива, а также, возможно, другие параметры, необходимые для решения конкретной задачи.

Варианты.
1.   Сортировка с переменным шагом (Шелла) и сортировка вставками.
2.   Сортировка с переменным шагом (Шелла) и сортировка бинарными вставками
3.   Сортировка Хоара (быстрая) с рекурсией и сортировка простым обменом (пузырьковая)
4.   Сортировка Хоара (быстрая) с рекурсией и шейкерная сортировка.
5.   Сортировка Хоара (быстрая) с рекурсией и выбором опорного элемента ( средний, медиана из 3 элементов: первый, средний и последний).
6.   Сортировки с переменным шагом (Шелла) с различным шагом.
7.   Пирамидальная сортировка и сортировка простым выбором .
8.   Пирамидальная сортировка и пузырьковая сортировка .
9.    Сортировка Хоара (быстрая) с рекурсией и модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры.
10.   Сортировка слиянием и сортировка подсчетом.
11.   Сортировка слиянием рекурсивная и итерационная(восходящая).
12.   Сортировка слиянием и сортировка выбором.
13.   Сортировка слиянием и шейкерная сортировка
14.   Пирамидальная сортировка и сортировка подсчетом
15.   Сортировка Хоара (быстрая) с рекурсией и подсчетом

Технология выполнения задания 1.
1.Прочитайте внимательно задание
2. Выберите свой вариант и выполните задание 1-5.

Контрольные вопросы
1.     Какова сложность каждого из рассмотренных выше алгоритмов сортировки?
2.     Определить среднее число обрабатываемых элементов для каждого из алгоритмов сортировки. Эту оценку можно получить из произведения среднего числа проходов и среднего количества элементов, обрабатываемых на каждом проходе.

Форма отчетности: работа, оформленная на листах формата А4, устная защита
1.       Название и цель работы.
8.        Схемы всех исследуемых алгоритмов в соответствии с ГОСТ 19.701-90 (ИСО 5807-85).
2.        Листинг программы
3.        Результаты сортировки для небольших примеров с промежуточнымие результатами каждого прохода.
4.        Теоретические оценки исследуемых алгоритмов.
5.        Таблица сравнительных характеристик работы алгоритмов для различных по размеру массивов данных (не менее 10 различных размеров от 10 до 100000).
6.        Графики функций
7.        Выводы по работе.