Прикладное программирование

Задание: исследование алгоритмов сортировки.

Отчёт оформить в виде файла docx.

1. Описать алгоритмы и расчёт времени работы и количества используемой памяти для следующих алгоритмов сортировки: пузырьковая (bubble sort), быстрая (quick sort), слинием (merge sort), подсчётом (count sort), карманная (bucket sort) и ещё одной, выбраной самостоятельно (не больше двух сортировок одного типа в группе), например, из списка на странице (файл там ссылка) Теоретический расчёт времени работы и испольуемой памяти показать при лучших и худших данных, в среднем. Какие из данных сортировок являются стабильными? Какие из данных сортировок являются универсальными, а какие можно использовать только для данных особого вида.

2. Создать программу для создания тестовых данных. На выходе должен получаться файл (возможна реализация без файла в виде структуры vector), содержащий nTest > 10 экспериментов, каждый из экспериментов представляет собой данные размера n. Количество элементов для сортировки n задать из последовательности 10, 20, 40, 80 ... до числа, когда компьютер будет считать адекватное количество времени, например, не больше минуты, но не меньше секунды на самый большой размер данных.

3. Создать программу (на любом языке программирования) для реализации тестирования, код оформить вместе с комментариями по каждой функции (по каждой строчке не надо). Засечь время работы для каждого алгоритма (считать по выполнению всех m вариантов внутри эксперимента). Выполнить программную проверку, что данные действительно отсортрованы после выполнения соответствующей операции.

4. Предоставить таблицу и график зависимости времени работы алгоритма T от количества элементов массива n. Насколько он совпадает со временной сложностью, рассчитанной теоретически?

5. В выводах написать какой алгоритм показал лучшие результаты и в каких ситуациях. Как особенности данных могут повлиять на алгоритмы сортировки?

6. В списке источников указать не менее 5 источников, которые вы использовали (могли использовать) при работе.