Введение в программирование 4. QuickSelect, детерминированный QuickSort, LSD

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Лекция прочитана 23 сентября 2021 года Лектор: Степанов Илья Даниилович Оператор: Мария Шкатова Монтаж: Жильцов Игорь 0:00 - QuickSort, повторение 4:50 - k-я порядковая статистика, недетерминированный QuickSelect 15:10 - Асимптотика QuickSelect 17:26 - Что даёт случайность? 22:37 - Детерминированный QuickSelect 33:12 - Иллюстрация к работе детерм. QuickSelect 39:49 - Асимптотика детерм. QuickSelect 46:17 - Детерминированный QuickSort на базе детерм. QuickSelect 49:20 - Зачем отказываться от случайности? 52:13 - Сортировка чисел 53:21 - Сортировка подсчётом 59:16 - Стабильность сортировки 1:02:04 - Стабильная сортировка подсчётом 1:10:30 - Сортировка пар чисел 1:16:30 - LSD: Сортировка больших чисел 1:21:50 - Оптимизация LSD