Алгоритмы сортировки

Тема: Алгоритмы сортировки.

Реализация алгоритмов

Реализуйте 4 алгоритма сортировки:

• 2 со сложностью $O(N^2)$ (Bubble, Insertion, Selection, Shell).
• 2 со сложностью $O(N log(N))$ (Heap, Merge, Quick).
• Можете также реализовать Radix Sort, этот алгоритм в некотором смысле особенный.

Алгоритм должен быть сделан в виде функции, принимающей параметром std::span<T>, а также любой другой контекст, необходимый для сортировки (например, функция сравнения элементов). Функция должна возвращать либо void, когда сортировка присходит in-place, либо отсортированную копию массива, когда не in-place (merge sort), в котором случае память входного std::span не должна быть изменена. Разрешается засунуть параметры в единую структуру контекста, если считаете это необходимым.

Сбор данных для анализа

Аналогично 2 лабе, запустите алгоритмы для:

• Разных размерностей массива (большой массив это 1000+ элементов);
• Разных изначальных конфигураций расположения элементов в массиве.

Сохраняйте как результат выполнения алгоритмов:

• Затраченное время на выполнение;
• Количество совершенных проверок между двумя элементами;
• Количество совершенных swap-ов или копирований;
• Другие данные, как считаете нужным.

Подсчитывайте общее и среднее время выполнения алгоритмов.

Анализ полученных данных

Проведите анализ полученных данных:

• Сравните, как время выполнения и прочее зависит от входных данных (алгоритм, размерность массива, расположение элементов).
• Выведите практическую сложность времени выполнения и затраченной памяти алгоритмов (как увеличивается время выполнения в зависимости от размерности массива).
• Выведите теоретическую сложность времени выполнения и затраченной памяти выполненных алгоритмов, или исходя из описания алгоритма, или исходя из написанного кода.
• Объясните, какие плюсы и минусы алгоритмов со сложностью выполнения $O(N log(N))$ между собой. Как подход к проблеме влияет на наилучшее и наихудшее время выполнения (зависит от расположения элементов?).