В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Алгоритмы и структуры данных, часть 1
/
осень 2018
/

Лекция 2. Сортировки

Суббота, 22 сентября 2018
НГУ, ауд. 2128, НГУ, новый корпус
Список тем / 24 записи
    1.
    Лекция 1. Сложность и модели вычислений
    2.
    1. Вводное занятие
    3.
    Лекция 2. Сортировки
    4.
    2. Разное
    5.
    Лекция 3. Кучи (начало)
    6.
    3. Динамическое программирование
    7.
    Лекция 4. Кучи (продолжение)
    8.
    Семинар 4. Динамическое программирование
    9.
    Лекция 5. Порядковые статистики
    10.
    Семинар 5. Тестирование
    11.
    Лекция 6. Хеширование
    12.
    Семинар 6. Быстрое преобразование Фурье
    13.
    Лекция 7. Деревья поиска
    14.
    Семинар 7. Хеширование, итераторы
    15.
    Лекция 8. Деревья поиска: продолжение
    16.
    Семинар 8. Метод заметающей прямой
    17.
    Лекция 9. Задачи RMQ и LCA
    18.
    Семинар 9. Дерево отрезков
    19.
    Лекция 10. Система непересекающихся множеств
    20.
    Семинар 10. Разное
    21.
    Лекция 11. Структуры данных для геометрического поиска
    22.
    Семинар 11. Дерево поиска с неявным ключом
    23.
    Лекция 12. Задача о динамической связности в ненаправленном графе
    24.
    Семинар 12. Параллельные алгоритмы

Слайды с лекции

algorithms_1_lecture_220918.pdf

Описание

Задача о поддержании динамического максимума в стеке и очереди.

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