Лабораторная работа №2

Задача

Реализовать гибридную сортировку TimSort.

В вашей реализации обязательно должны быть реализованы все основные элементы алгоритма:

1. Сортировка вставками.
2. Поиск последовательностей run.
3. Подсчёт minrun.
4. Слияние последовательностей run.
5. Режим галопа при слиянии.

Обо всем выше перечисленном вы можете без проблем найти в предоставленном источнике выше.

Важное замечание

Когда вы реализовываете функцию с вашей сортировкой, на вход она должна принимать реализацию вашего списка из лабораторной работы №1, либо динамического массива из лабораторной работы №1. Никаких std::vector, java.util.ArrayList и т.д быть не должно**.**

fun sort(list: **MyList**){
    //FixMe before deadline
}

fun main() {
    /**
     * 1. Создать свой список
     * 2. Заполнить его случайными элементами (1_000, 100_000, 1_000_000)
     * 3. Проверить работоспособность и скорость реализованного алгоритма
     * */
}

Дополнительная задача на баллы оценки “Отлично”

Помимо предоставленного выше алгоритма сортировки вам необходимо реализовать как минимум еще один алгоритм сортировки, а для наглядности лучше два. В качестве дополнительных алгоритмов для реализации стоит выбрать те, которые работают за O(n^2) и O(n,logn). Если берете только один, то берете алгоритм, работающий за O(n,logn). Список сортировок вы можете найти в интернете, либо посмотреть здесь. P.S. Я бы выбрал MergeSort и InsertionSort

После того, как у вас будет реализовано несколько видов сортировки, вам необходимо проверить их работоспособность и скорость работы на разных объемах данных.

Ниже приведена таблица, наподобие которой должна получиться у вас. Как замерить время работы функции необходимо будет погуглить, но это совсем несложно и нетрудоемко, как может показаться на первый взгляд. Имейте в виду, что время на печать элементов в консоль учитывать не нужно 🙂

После того, как ваша таблица создана, вы должны будете представить ее графически.

Получившийся график и таблицу необходимо оформить как-нибудь в файл, на ваше усмотрение.