Лекция 2. Сортировки (Алгоритмы и структуры данных, часть 1)

Задача о поддержании динамического максимума в стеке и очереди. Задача сортировки. Разрешающие деревья. Нижняя оценка сложности в модели разрешающих деревьев. Сортировка сравнениями. Понятия устойчивости и in-place. Понятие о методе «разделяй и властвуй»: quicksort и mergesort. Алгоритм Quick-Sort. Процедура Partition, два варианта её in-place реализации. Примеры неудачного выбора опорных элементов. Рандомизированный выбор опорного элемента. Сложность Quick-Sort в худшем и среднем случаях. Глубина рекурсии в худшем и среднем случаях. Подробности реализации (кратко): сортировка вставками для малых подмассивов, удаление хвостовой рекурсии, медиана трёх, переход в другому виду сортировки. Алгоритм Merge-Sort. Слияние двух упорядоченных списков. Оценка сложности. Нерекурсивная реализация. Сортировка слиянием без использования дополнительной памяти: swap вместо присваивания, использование части массива в качестве буфера, слияние с перекрыванием входа и выхода. Лекция №2 в курсе “Алгоритмы и структуры данных, часть 1“, осень 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница лекции на сайте CS центра: Все видео курса по порядку: