Лабораторная работа №2
Задача
Реализовать гибридную сортировку TimSort.
В вашей реализации обязательно должны быть реализованы все основные элементы алгоритма:
- Сортировка вставками.
- Поиск последовательностей run.
- Подсчёт minrun.
- Слияние последовательностей run.
- Режим галопа при слиянии.
Обо всем выше перечисленном вы можете без проблем найти в предоставленном источнике выше.
Важное замечание
Когда вы реализовываете функцию с вашей сортировкой, на вход она должна принимать реализацию вашего списка из лабораторной работы №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
После того, как у вас будет реализовано несколько видов сортировки, вам необходимо проверить их работоспособность и скорость работы на разных объемах данных.
Ниже приведена таблица, наподобие которой должна получиться у вас. Как замерить время работы функции необходимо будет погуглить, но это совсем несложно и нетрудоемко, как может показаться на первый взгляд. Имейте в виду, что время на печать элементов в консоль учитывать не нужно
После того, как ваша таблица создана, вы должны будете представить ее графически.
Получившийся график и таблицу необходимо оформить как-нибудь в файл, на ваше усмотрение.