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

  1. [10 минут] Два указателя и ответы на запросы в offline
    1. Число различных чисел на отрезке li ≤ li+1, ri ≤ ri+1. O(n+m).
    2. Отрезки произвольны. Алгоритм Мо. O(nm1/2).
  2. [25 минут] Quick-Sort
    1. Версия с O(logn) доп памяти в худшем случае
    2. Выбор медианы 1/2, median(1/4, 2/4, 3/4), random
    3. [10 минут] Оценка времени #1: мы считаем среднее время = сумма по всем рандомам = сумма по всем парам
    4. [10 минут] Оценка времени #2: мы считаем T(n) = 1/n ∑ x=1..n-1 [T(x) + T(n-x)]
    5. IntroSort (std::sort)
  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. [5 минут] Count Sort.
    3. [15 минут] Radix sort.
      1. Сортируем пары за O(n+m)
      2. Сортируем вектора за O(n×len)
      3. Сортируем числа за O(nlognm)
    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). Оценим ∑ki2
      5. Lm #2: BB работает в худшем за O(n log(MAX-MIN))