Видеозаписи лекций ЛКШ
Сортировки сравнением: нижняя оценка сложности.
Лектор: Олег Пестов
2008.Август
Параллель B'
Сортировки
Алгоритм быстрой сортировки Хоара (QuickSort).
Разбор задачи Kth ("K-ый минимум") из контеста первого дня: модификация алгоритма быстрой сортировки для нахождения k-й порядковой статистики.
Алгоритм сортировки слиянием (MergeSort).
Применение сортировки слиянием: количество инверсий.
Сортировки сравнением: нижняя оценка сложности.
Сортировка подсчетом (CountSort).
Цифровая (поразрядная) сортировка (RadixSort).
Реализация цифровой сортировки.
Алгоритм BucketSort.
Сортировка подсчетом по ключу.
Устойчивость сортировки.
Цифровая (поразрядная) сортировка (RadixSort).