2.2. Задание к лабораторной работе

1. Спроектировать, реализовать и провести тестовые испытания АТД «Вектор» для коллекции, содержащей данные произвольного типа. Размер коллекции и тип данных задаётся клиентской программой.

АТД «Вектор» представляет собой последовательность элементов, размещённых в одной сплошной области памяти. Доступ к элементам вектора осуществляется по индексу.

Интерфейс АТД «Вектор» включает следующие операции:

• опрос размера вектора,

• изменение размера вектора,

• формирование в векторе случайной выборки значений,

• формирование в векторе упорядоченной выборки значений,

• чтение/запись по индексу,

• элементарная сортировка (по варианту задания),

• эффективная сортировка (по варианту задания).

Для тестирования эффективности алгоритмов сортировки интерфейс АТД "Вектор" включает следующие дополнительные операции:

• опрос числа выполненных сравнений,

• опрос числа выполненных обменов.

2. Выполнить отладку и тестирование отдельных операций АТД "Вектор" с помощью меню операций.

3. Выполнить сравнительное тестирование трудоёмкости алгоритмов сортировки для худшего и среднего случаев.

4. Провести анализ экспериментальных показателей трудоёмкости алгоритмов сортировки.

5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

1. титульный лист,

2. цель лабораторной работы,

3. общее задание (пункты 1 – 4) и вариант задания,

4. формат АТД,

5. определение шаблонного класса для коллекции «Вектор», предназначенное для клиентской программы,

6. описание методики тестирования трудоёмкости алгоритмов сортировки,

7. таблицы и графики с полученными оценками трудоёмкости алгоритмов операций для наихудшего и среднего случаев функционирования АТД. Должны быть приведены следующие графики:

• число обменов, число сравнений для худшего и среднего случаев для элементарного алгоритма сортировки (графики совмещены в одной системе координат),

• число обменов, число сравнений для худшего и среднего случаев для эффективного алгоритма сортировки (графики совмещены),

• число сравнений алгоритмов элементарной и эффективной сортировки для среднего случая,

• число обменов алгоритмов элементарной и эффективной сортировки для среднего случая,

• сумма числа сравнений и обменов алгоритмов элементарной и эффективной сортировки для среднего случая,

8. сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,

9. сравнительный анализ экспериментальных оценок трудоёмкости для различных алгоритмов сортировки,

10. выводы,

11. список использованной литературы,

12. приложение с текстами программ:

• полное определение класса и текстов методов класса,

• текст программы тестирования трудоёмкости операций АТД.

2.1.1. Варианты заданий

1. Алгоритм сортировки выбором, алгоритм сортировки с помощью дерева выбора.

2. Алгоритм сортировки выбором, алгоритм пирамидальной сортировки.

3. Алгоритм сортировки вставками, алгоритм сортировки Шелла.

4. Алгоритм обменной сортировки, рекурсивный алгоритм сортировки разделением.

5. Алгоритм обменной сортировки, итерационный алгоритм сортировки разделением.

6. Алгоритм нисходящей сортировки слиянием, алгоритм восходящей сортировки слиянием.

7. Алгоритм поразрядной сортировки MSD-сортировки.

8. Алгоритм поразрядной сортировки LSD-сортировки.