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

508

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

  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).