Сортировки и порядковые статистика, MinMax куча (7 октября 2019)

1. [10 минут] Quick-Sort
1. Версия с O(logn) доп памяти в худшем случае
2. [10 минут] Оценка времени #1: мы считаем среднее время = сумма по всем рандомам = сумма по всем парам
3. [2 минут] Оценка времени #2: напоминаем историю про интеграл


2. [20 минут] Порядковые статистика за O(n)
1. QSort = get x + partition x + QSort + QSort, избавимся от одной ветки
2. [10 минут] Одноветочный QuickSort. Время работы. Простая версия, дающая асимптотику; сложная с константой 4, как упражнение.
3. [10 минут] Детерминированный partition.
4. C++: nth_element, partition

1. [40 минут] Целочисленные сортировки
1. Почему вообще числа можно сортировать быстрее?
2. Напоминание: Count Sort за O(n+m). Замечание: стабильность.
3. [15 минут] Radix sort.
1. Сортируем пары подсчётом за O(n+m)
2. Сортируем вектора за O(n×len)
3. Сортируем числа за O(nlog_nm)
4. [20 минут] Bucket Sort
1. Алгоритм: if (Min != Max) разбить на n бакетов, вызваться для каждого
2. Вариации: для каждого вызваться рекурсивно (BB), для каждого вызвать insertion sort (BI)
3. Lm #0: MAX-MIN ≤ n ⇒ BI = Θ(n), BB = Θ(n)
4. Lm #1: на равномерном распределении матожидание времние BI работает за O(n). Оценим ∑k_i²
5. Lm #2: BB работает в худшем за O(n log(MAX-MIN))

1. [15 минут] V.E.B за loglogC
1. Сформулируем задачу: heap для целых чисел от 0 до C-1. C = 2^2k (чисел битовой длины 2^k).
2. Интерфейс Min = O(1), Add и Del = O(k) = O(loglogC).
3. Случаи: size = 0, size = 1, size ≥ 2, struct Heapk: { Heapk-1 a; u_map<int,Heapk-1> b; int min, size; }.
4. Реализуем Add, пересчёт Min
5. Реализуем Del