Сортировки (1 октября 2024)

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

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

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

  4. [5 минут] Напоминание. Сравнение трёх решений задачи о пересечении множеств
    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. Выбор разделяющего элемента в qsort: 1/2, median(1/4, 2/4, 3/4), random
    4. Что такое время работы вероятностного алгоритма? 1/R ∑1..R ti
    5. [10 минут] Оценка времени #1: вероятности
    6. [10 минут] Оценка времени #2: мы считаем T(n) = 1/n ∑ x=1..n-1 [T(x) + T(n-x)], далее интегралы
    7. IntroSort (std::sort = qsort + hsort + inssort)