Сортировки (2 октября 2017)

  1. [10 минут] Два указателя и ответы на запросы в offline
    1. Число различных чисел на отрезке li ≤ li+1, ri ≤ ri+1. O(n+m).
    2. Отрезки произвольны. Алгоритм Мо. O(nm1/2).

  2. [15 минут] Квадратичные сортировки
    1. Определения: число инверсий (мера упорядоченности), стабильность (через сортировку пар).
    2. Selection: n2, n, -, 1 (число сравнений, числа присваиваний, стабильность)
    3. Insertion: n+inv, inv, +, 1
    4. InsertionBS: n+inv, min(inv,nlogn), +, 1
    5. Bubble: n2, n2, +, 1
    6. ShakerBubble: n2, n2, +, 1

  3. [15 минут] Оценка снизу и сортировка подсчётом
    1. CountSort = O(n+m)
    2. Если доступны только сравнения, число сравнений: хотя бы log(n!) = Θ(nlogn)

  4. [10 минут] Сравнение трёх решений задачи о пересечении множеств
    1. Решение хеш-таблицей: Θ(n), доппамять, большая константа
    2. Сортировка + бинпоиск: O(sort) + O(nlogn), sort, lower_bound, минимум кода
    3. Два указателя: O(sort) + O(n), малая константа
− Перерыв −
  1. [20 минут] Merge Sort
    1. Рекурсивная сортировка, оценка. Пишем код, чтобы доппамять была в merge
    2. Число инверсий для каждого элемета.
    3. Нерекурсивная версия, избавляемся от копирования памяти
    4. STL: stable_sort, merge, inplace_merge

  2. [20 минут] Quick Sort
    1. Собственно сортировка, пишем код partition на python
    2. Собственно сортировка, пишем код partition на c++
    3. Что такое время работы вероятностного алгоритма?
    4. Выбор медианы 1/2, median(1/4, 2/4, 3/4), random
    5. [10 минут] Оценка времени #2: мы считаем T(n) = 1/n ∑ x=1..n-1 [T(x) + T(n-x)]
    6. IntroSort (std::sort)