Алгоритмы и структуры данных поиска: Функции быстрой сортировки и сортировки слиянием. Бабенко Максим

Бабенко Максим рассказывает о функциях быстрой сортировки и сортировки слиянием.

1. Понятие о методе «разделяй и властвуй».
2. Алгоритм Merge-Sort.
3. Слияние двух упорядоченных списков.
4. Оценка сложности.
5. K-way Merge-Sort для работы во внешней памяти.
6. Сортировка слиянием без использования дополнительной памяти.
7. Общая схема алгоритма Quick-Sort.
8. Два варианта реализации Partition.
9. Примеры неудачного выбора опорных элементов.
10. Рандомизированный выбор опорного элемента.
11. Сложность Quick-Sort в худшем и среднем случаях.
12. Глубина рекурсии в худшем и среднем случаях.
13. Элиминация хвостовой рекурсии.
14. Задача об оптимальном дереве слияний.
15. Коды Хаффмана.
16. Слияние двух упорядоченных последовательностей различной длины.
17. Теоретико-информационная нижняя оценка.
18. Бинарный поиск «от края» (galloping).