Сортировки и порядковые статистика (9 октября 2017)

1. [10 минут] Забытое на прошлой паре
1. Сравнение трёх решений задачи о пересечении множеств
2. Ленивое удаление из кучи: while isDeleted(heap.getMin()) do heap.extractMin()


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


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


2. [20 минут] Sort: Kirkpatrick за loglogC
1. Записать общую рекурсивную функцию
2. Показать, где хеш-таблицы,
3. Главная оптимизация: не передаём максимум вектора в рекурсию

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