Сортировки (5 октября 2016)

  1. [10 минут] Сравнение трёх решений задачи о пересечении множеств
    1. Решение хеш-таблицей: Θ(n), доппамять, большая константа
    2. Сортировка + бинпоиск: O(sort) + O(nlogn), sort, lower_bound, минимум кода
    3. Два указателя: O(sort) + O(n), малая константа
  2. [5 минут] Пополняемые структуры данных
    1. Find → Del. Удалить X из структуры с Find : пометить, как удалённый
    2. Ничего → Del. Хранить отдельно две структуры: добавленные элементы, удалённые.
    3. Add → Merge. Сливаемые структуры: меньшее к большему (учим кучи и хеш-таблицы сливаться)
    4. Пополняемый массив: добавить X, посчитать количество X от L до R.
      1. Предподсчёт за O(nlogn), запрос за O(logn). Добавление нового элемента = корневая.
      2. Предподсчёт за O(nlogn), запрос за O(logn). Добавление нового элемента = пополняемые структуры.
    5. Удалить X из стурктуры с аддитивным запросом (хранить две структуры = добавленные элементы + удалённые)
− Перерыв −
  1. [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
  2. [10 минут] Оценка снизу и сортировка подсчётом
    1. CountSort = O(n+m)
    2. Если доступны только сравнения, число сравнений: хотя бы log(n!) = Θ(nlogn)
  3. [20 минут] Merge Sort
    1. Рекурсивная сортировка, оценка. Пишем код, чтобы доппамять была в merge
    2. Число инверсий для каждого элемета.
    3. Нерекурсивная версия, избавляемся от копирования памяти
    4. STL: stable_sort, merge, inplace_merge
  4. [10 минут] Quick Sort
    1. Собственно сортировка, пишем код partition на python
    2. Собственно сортировка, пишем код partition на c++
    3. Что такое время работы вероятностного алгоритма?