Лекция. Разделяй и властвуй: сортировки слиянием и Хоара

Лекция 5. Разделяй и властвуй: сортировки слиянием и Хоара

На лекции 3 были квадратичные сортировки и нижняя оценка $\Omega(n\log n)$ в модели сравнений. Сегодня строим алгоритмы, которые до этой границы дотягиваются: сортировку слиянием — гарантированно, быструю сортировку — в ожидании при оговорённых условиях.

Опираемся на лекцию 3 (сортировка, устойчивость, нижняя оценка) и лекцию 4 (рекурсия, база и шаг, стек вызовов). Слияние двух упорядоченных массивов уже встречалось на семинаре 2. Первые пять минут — входной тест по лекциям 2–4: три короткие задачи, чтобы проверить базу перед коллоквиумом.

План

Разминка: входной тест по лекциям 2–4 — три задачи, 5 минут. 0. Мастер-теорема: рекуррента $aT(n/b)+\Theta(n^c)$ и три случая.

Зачем ещё две сортировки: «разделяй и властвуй» и контракт сортировки.
Слияние двух упорядоченных массивов: два указателя, инвариант, устойчивость.
Сортировка слиянием: рекурсивная схема, корректность, дерево, время и память.
Идея быстрой сортировки: работа до рекурсивных вызовов.
Разбиение Ломуто.
Разбиение Хоара: другой контракт и другие границы.
Быстрая сортировка: хорошее и плохое дерево, случайный опорный, повторяющиеся ключи, память.
Закрепление базовых вопросов по асимптотике перед коллоквиумом.
Сравнение двух сортировок, семинар и программа коллоквиума.

Это лекция: рекурсивную схему смотрим кодом, внутренние циклы слияния и разбиения разбираем через инвариант и ручную трассировку. Полные реализации закрепляем на семинаре 5. Лекция идёт до семинара.

Стек, очередь и дек как абстрактные типы данных — лекция 7; в программу коллоквиума 1 этот материал не входит.

Входной тест: три задачи по лекциям 2–4

Разогрев на 5 минут перед новой теорией. Это не оценка, а проверка, что база прошлых лекций на месте: сначала отвечает группа, потом открываем ячейку с проверкой.

1. Асимптотика (лекция 2). Два последовательных прохода по массиву длины $n$ — это $\Theta(n)$ или $\Theta(n^2)$?

2. Устойчивость (лекция 3). Отсортируйте устойчиво по ключу: [(2, "б"), (1, "а"), (2, "в")].

3. Бинпоиск (лекция 4). В массиве [1, 3, 5, 7, 9] найдите lower_bound(7) — первый индекс с a[i] >= 7.

0. Мастер-теорема

Перед сортировками — короткий инструмент. Он позволит оценивать «разделяй и властвуй» одной формулой, а не рисовать дерево заново для каждой задачи. Это именно инструмент: в программу коллоквиума 1 он не входит.

Рекуррента «разделяй и властвуй». Задача размера $n$ делится на $a$ подзадач размера $n/b$, а сборка ответа (слияние, разбиение) стоит $\Theta(n^c)$:

$$T(n) = a\,T(n/b) + \Theta(n^c), \qquad T(n) = \Theta(1) \text{ при } n \le n_0.$$

Мастер-теорема. Сравним показатель сборки $c$ с $\log_b a$:

A. $c > \log_b a$: $T(n) = \Theta(n^c)$ — работа в корне перевешивает;
B. $c = \log_b a$: $T(n) = \Theta(n^c\log n)$ — уровни равнозначны, их $\log_b n$;
C. $c < \log_b a$: $T(n) = \Theta(n^{\log_b a})$ — перевешивают листья.

Откуда три случая. Дерево рекурсии: $\log_b n$ уровней, на $k$-м уровне $a^k$ вершин, каждая стоит $(n/b^k)^c$. Сумма по уровням — геометрическая прогрессия со знаменателем $a/b^c$:

$$T(n) = n^c \sum_{k=0}^{\log_b n} \left(\frac{a}{b^c}\right)^k.$$

Её режим зависит от того, больше знаменатель единицы, равен ей или меньше. Это ровно та картинка уровней, которой мы будем объяснять merge sort, только в общем виде. Полное доказательство не выводим.

Проверка без логарифмов: сравниваем $b^c$ и $a$ — это то же самое, что сравнивать $c$ и $\log_b a$.

In [2]:

def master_case(a, b, c):
    # Сравниваем b**c с a — это то же, что сравнивать c и log_b(a), но без логарифмов.
    if b ** c > a:
        return f"A: Theta(n^{c})"
    if b ** c == a:
        if c == 0:
            base = "log n"
        elif c == 1:
            base = "n log n"
        else:
            base = f"n^{c} log n"
        return f"B: Theta({base})"
    k = 0
    while b ** k < a:
        k += 1
    return f"C: Theta(n^{k})"


recurrences = [
    ("бинарный поиск", 1, 2, 0),
    ("merge sort", 2, 2, 1),
    ("слияние за Theta(n^2)", 2, 2, 2),
    ("четыре подзадачи, линейная сборка", 4, 2, 1),
]
for name, a, b, c in recurrences:
    print(f"{name}: a={a} b={b} c={c} -> {master_case(a, b, c)}")

бинарный поиск: a=1 b=2 c=0 -> B: Theta(log n)
merge sort: a=2 b=2 c=1 -> B: Theta(n log n)
слияние за Theta(n^2): a=2 b=2 c=2 -> A: Theta(n^2)
четыре подзадачи, линейная сборка: a=4 b=2 c=1 -> C: Theta(n^2)

Границы применимости. Сборка должна быть $\Theta(n^c)$, то есть полиномиальной: слияние за $\Theta(n\log n)$ в теорему не укладывается. И рекуррента обязана иметь вид $aT(n/b)$ с $b > 1$: вырожденный quick sort даёт $T(n)=T(n-1)+\Theta(n)$ — это $b=1$, и его мы разберём отдельно деревом в разделе 7.

1. Зачем ещё две сортировки

На лекции 3 квадратичные сортировки давали $\Theta(n^2)$ сравнений. Нижняя оценка говорит, что в модели сравнений быстрее $\Omega(n\log n)$ в худшем случае не получится. Осталось построить алгоритмы, которые этого порядка достигают.

Разделяй и властвуй: разделить задачу на меньшие, решить их тем же способом, собрать ответ для целого. В бинарном поиске после сравнения оставался один диапазон. Для сортировки так не выйдет: упорядочить нужно обе части, а потом соединить их.

Контракт сортировки. Результат неубывает и содержит те же элементы с теми же кратностями: ничего не потеряно и ничего не добавлено.

База рекурсии: 0 или 1 элемент — сортировать нечего. Чтобы рекурсия завершилась, каждый дочерний диапазон должен быть строго меньше родительского.

Для диапазонов массива используем полуинтервалы $[l, r)$ — тот же договор, что в бинарном поиске. Но условие остановки другое: сортировка заканчивается уже при $r - l \le 1$, а не при $l = r$.

2. Слияние двух упорядоченных массивов

Пример: [1, 4a, 7] и [2, 4b, 6]. Буквы — метки элементов; сравниваем только числовой ключ. Метка нужна, чтобы увидеть устойчивость: при равных ключах $4a$ и $4b$ порядок входа должен сохраниться.

Два указателя стоят на первых ещё не взятых элементах. Меньшую голову переносим в результат и сдвигаем её указатель. Когда один массив исчерпан, дописываем остаток другого.

Инвариант. Результат содержит уже взятые элементы в неубывающем порядке; каждый оставшийся элемент не меньше последнего выданного. Значит, минимальный из оставшихся лежит на одной из двух голов: сравнивать достаточно их.

Устойчивость. При равенстве ключей берём из левого массива. В сортировке слиянием левая половина стояла раньше правой, поэтому $4a$ останется перед $4b$.

Время $\Theta(p+q)$, где $p$ и $q$ — длины массивов: каждый элемент переносится ровно один раз. Буфер под результат — $\Theta(p+q)$.

Сравнение элементов сделаем по ключу: опишем элемент с ключом и меткой.

In [1]:

class Item:
    # Элемент с ключом и полезной нагрузкой; сравнение — только по ключу.
    def __init__(self, key, label):
        self.key = key
        self.label = label

    def __lt__(self, other):
        return self.key < other.key

    def __le__(self, other):
        return self.key <= other.key

    def __repr__(self):
        return self.label


def merge(left, right):
    # Слить два неубывающих массива в новый неубывающий.
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # при равенстве ключей берём из левого
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])              # остаток одного из массивов
    result.extend(right[j:])
    return result

In [2]:

left = [Item(1, "1"), Item(4, "4a"), Item(7, "7")]
right = [Item(2, "2"), Item(4, "4b"), Item(6, "6")]
print("слева:  ", left)
print("справа: ", right)
print("слияние:", merge(left, right))

слева:   [1, 4a, 7]
справа:  [2, 4b, 6]
слияние: [1, 2, 4a, 4b, 6, 7]

Разберём шаги на этом примере:

Шаг	Сравниваем	Берём	Результат
1	$1$ и $2$	$1$	`[1]`
2	$4a$ и $2$	$2$	`[1, 2]`
3	$4a$ и $4b$	$4a$ — берём слева	`[1, 2, 4a]`
4	$7$ и $4b$	$4b$	`[1, 2, 4a, 4b]`
5	$7$ и $6$	$6$	`[1, 2, 4a, 4b, 6]`
6	левый исчерпан	хвост `[7]`	`[1, 2, 4a, 4b, 6, 7]`

Полный цикл слияния соберёте на семинаре 5. Здесь важно, почему один проход даёт линейное время и откуда берётся устойчивость.

3. Сортировка слиянием

Схема. Делим массив пополам, сортируем обе половины тем же алгоритмом, соединяем слиянием. Сначала целиком завершается левый вызов, затем правый, и только потом выполняется слияние.

Перед запуском стоит спросить: когда выполнится первый вызов merge? Только после того, как обе половины вернутся отсортированными.

In [3]:

def merge_sort(a):
    # Вернуть новый отсортированный список; исходный не меняется.
    if len(a) <= 1:                     # база: 0 или 1 элемент
        return a[:]
    m = len(a) // 2
    left = merge_sort(a[:m])
    right = merge_sort(a[m:])
    return merge(left, right)

In [4]:

a = [5, 1, 4, 2, 8, 3, 7, 6]
print("вход:  ", a)
print("выход: ", merge_sort(a))
print("исходный не изменился:", a)

вход:   [5, 1, 4, 2, 8, 3, 7, 6]
выход:  [1, 2, 3, 4, 5, 6, 7, 8]
исходный не изменился: [5, 1, 4, 2, 8, 3, 7, 6]

На доске то же самое: вниз — деление до единичных массивов, вверх — слияние. Дерево всех вызовов и текущая цепочка активных вызовов — разные объекты: одновременно занята память только одной ветви.

Посмотрим на порядок работы явно:

In [5]:

def merge_sort_trace(a, depth=0):
    # Печатает деление и слияние, возвращает отсортированный список.
    print("  " * depth + "делим", a)
    if len(a) <= 1:
        return a[:]
    m = len(a) // 2
    left = merge_sort_trace(a[:m], depth + 1)
    right = merge_sort_trace(a[m:], depth + 1)
    result = merge(left, right)
    print("  " * depth + "слили", result)
    return result


merge_sort_trace([5, 1, 4, 2, 8, 3, 7, 6])

делим [5, 1, 4, 2, 8, 3, 7, 6]
  делим [5, 1, 4, 2]
    делим [5, 1]
      делим [5]
      делим [1]
    слили [1, 5]
    делим [4, 2]
      делим [4]
      делим [2]
    слили [2, 4]
  слили [1, 2, 4, 5]
  делим [8, 3, 7, 6]
    делим [8, 3]
      делим [8]
      делим [3]
    слили [3, 8]
    делим [7, 6]
      делим [7]
      делим [6]
    слили [6, 7]
  слили [3, 6, 7, 8]
слили [1, 2, 3, 4, 5, 6, 7, 8]

Out[5]:

[1, 2, 3, 4, 5, 6, 7, 8]

Корректность. База: массив длины 0 или 1 уже упорядочен. Шаг: по предположению обе половины отсортированы и содержат те же элементы; слияние даёт неубывающий результат и сохраняет все элементы с кратностями. Размеры половин меньше размера целого, поэтому рекурсия завершается.

Время. Пусть $n$ — степень двойки. На каждом уровне дерева слияния обрабатывают в сумме $n$ элементов, то есть $\Theta(n)$ работы на уровень, а уровней $\log_2 n$. Итого $\Theta(n\log n)$. Для произвольного $n$ округления при делении пополам порядок не меняют. Это ровно случай B мастер-теоремы: $a=2$, $b=2$, $c=1$, $b^c=a$, поэтому $T(n)=\Theta(n\log n)$. Ту же оценку полезно увидеть и деревом уровней. На уже отсортированном массиве оценка та же: слияние всегда проходит все элементы.

Память. Дополнительный буфер под слияние — $\Theta(n)$ в пике, глубина рекурсии — $\Theta(\log n)$. В показанной версии срезы a[:m] и a[m:] тоже копируют данные: они не бесплатны, и суммарно за всё выполнение копируется $\Theta(n\log n)$ элементов. Но пиковая одновременно занятая дополнительная память — $\Theta(n)$. В реализации по индексам можно переиспользовать один буфер.

Устойчивость следует из устойчивого слияния.

На коллоквиуме достаточно нарисовать дерево уровней и объяснить пиковый расход памяти: складывать все копирования за время работы не нужно.

4. Быстрая сортировка: работа до рекурсивных вызовов

Быстрая сортировка — сортировка Хоара. Важно не путать название алгоритма и конкретную схему разбиения: quick sort можно реализовать и с разбиением Ломуто, и с разбиением Хоара.

Выбираем опорное значение и переставляем элементы так, чтобы части можно было сортировать независимо. Главная работа идёт до рекурсивных вызовов; отдельного слияния результатов нет.

	Merge sort	Quick sort
Размеры частей	всегда примерно равны	зависят от опорного
Как разделены	по позициям, значения перемешаны	по значениям
Основная работа	слияние после вызовов	разбиение до вызовов

Именно из-за неравных частей у quick sort появляется худший случай.

5. Разбиение Ломуто

Договор. Обрабатываем полуинтервал [l, r), опорный — последний элемент: pivot = a[r-1]. В проходе сравнение строгое: a[j] < pivot.

Перед обработкой позиции j выполнено:

[l, i) — элементы < pivot;
[i, j) — элементы >= pivot;
[j, r-1) — ещё не просмотрены;
a[r-1] — сохранённый опорный.

Если a[j] < pivot, меняем a[i] и a[j] и увеличиваем i; затем увеличиваем j. В конце меняем a[i] и a[r-1]: опорный встаёт на окончательную позицию p = i.

Разберём полный проход на [4, 1, 6, 3, 2, 5].

In [6]:

def partition_lomuto_trace(a, l, r):
    # Печатает состояние массива после каждой позиции прохода.
    pivot = a[r - 1]
    print("опорный:", pivot, " массив:", a)
    i = l
    for j in range(l, r - 1):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
        print("  j =", j, ":", a, "  i =", i)
    a[i], a[r - 1] = a[r - 1], a[i]
    print("после обмена с опорным:", a, " p =", i)
    return i


b = [4, 1, 6, 3, 2, 5]
p = partition_lomuto_trace(b, 0, len(b))
print("слева:", b[:p], " опорный:", b[p], " справа:", b[p + 1:])

опорный: 5  массив: [4, 1, 6, 3, 2, 5]
  j = 0 : [4, 1, 6, 3, 2, 5]   i = 1
  j = 1 : [4, 1, 6, 3, 2, 5]   i = 2
  j = 2 : [4, 1, 6, 3, 2, 5]   i = 2
  j = 3 : [4, 1, 3, 6, 2, 5]   i = 3
  j = 4 : [4, 1, 3, 2, 6, 5]   i = 4
после обмена с опорным: [4, 1, 3, 2, 5, 6]  p = 4
слева: [4, 1, 3, 2]  опорный: 5  справа: [6]

Получили [4, 1, 3, 2, 5, 6] и p = 4. Опорный 5 стоит там, где и должен, но обе части ещё не отсортированы — их предстоит отсортировать рекурсивно.

Разбиение стоит $\Theta(r-l)$ времени и $O(1)$ дополнительной памяти. Опорный исключается из обоих рекурсивных вызовов, поэтому диапазоны строго уменьшаются даже при крайнем p.

In [7]:

def partition_lomuto(a, l, r):
    # Разбиение [l, r) вокруг a[r-1]; возвращает индекс опорного.
    pivot = a[r - 1]
    i = l
    for j in range(l, r - 1):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[r - 1] = a[r - 1], a[i]
    return i


def quick_sort(a, l, r):
    if r - l <= 1:
        return
    p = partition_lomuto(a, l, r)
    quick_sort(a, l, p)                 # опорный не входит ни в одну часть
    quick_sort(a, p + 1, r)

In [8]:

c = [4, 1, 6, 3, 2, 5]
quick_sort(c, 0, len(c))
print(c)

[1, 2, 3, 4, 5, 6]

6. Разбиение Хоара

Для непустого диапазона длины хотя бы 2 сохраняем значение pivot = a[(l+r-1)//2]. Начинаем с i = l-1, j = r: указатели сначала делают шаг внутрь, а затем ищут

слева — первый элемент >= pivot;
справа — первый элемент <= pivot.

Если i < j, меняем элементы и продолжаем. Иначе возвращаем границу b = j + 1.

При каждом повторе каждый указатель делает хотя бы один шаг, поэтому равные опорному элементы не могут остановить продвижение и зациклить проход.

In [10]:

def partition_hoare_trace(a, l, r):
    # Печатает, где останавливаются указатели и что меняется местами.
    pivot = a[(l + r - 1) // 2]
    print("pivot =", pivot, " массив:", a)
    i, j = l - 1, r
    while True:
        i += 1
        while a[i] < pivot:
            i += 1
        j -= 1
        while a[j] > pivot:
            j -= 1
        print("  i =", i, "a[i] =", a[i], "  j =", j, "a[j] =", a[j])
        if i >= j:
            print("  указатели сошлись: возвращаем", j + 1)
            return j + 1
        a[i], a[j] = a[j], a[i]
        print("  обмен:", a)


for arr in ([4, 1, 6, 3, 2, 5], [2, 2, 2, 2]):
    data = arr[:]
    b = partition_hoare_trace(data, 0, len(data))
    print("части:", data[:b], "|", data[b:])
    print()

pivot = 6  массив: [4, 1, 6, 3, 2, 5]
  i = 2 a[i] = 6   j = 5 a[j] = 5
  обмен: [4, 1, 5, 3, 2, 6]
  i = 5 a[i] = 6   j = 4 a[j] = 2
  указатели сошлись: возвращаем 5
части: [4, 1, 5, 3, 2] | [6]

pivot = 2  массив: [2, 2, 2, 2]
  i = 0 a[i] = 2   j = 3 a[j] = 2
  обмен: [2, 2, 2, 2]
  i = 1 a[i] = 2   j = 2 a[j] = 2
  обмен: [2, 2, 2, 2]
  i = 2 a[i] = 2   j = 1 a[j] = 2
  указатели сошлись: возвращаем 2
части: [2, 2] | [2, 2]

Контракт отличается от Ломуто. Получаем две непустые части [l, b) и [b, r): в левой элементы <= pivot, в правой >= pivot. Сам опорный элемент не обязан стоять на окончательном месте.

Рекурсивно сортируем именно эти две части, без пропуска позиции b. Для этой схемы выбор нижней середины и продвижение обоих указателей обеспечивают l < b < r. Не смешивайте код одной схемы с границами рекурсии другой.

In [11]:

def partition_hoare(a, l, r):
    # Разбиение [l, r), r - l >= 2; возвращает границу b, l < b < r.
    pivot = a[(l + r - 1) // 2]         # значение, не индекс
    i, j = l - 1, r
    while True:
        i += 1
        while a[i] < pivot:
            i += 1
        j -= 1
        while a[j] > pivot:
            j -= 1
        if i >= j:
            return j + 1
        a[i], a[j] = a[j], a[i]


def quick_sort_hoare(a, l, r):
    if r - l <= 1:
        return
    b = partition_hoare(a, l, r)
    quick_sort_hoare(a, l, b)           # без пропуска позиции b
    quick_sort_hoare(a, b, r)

In [12]:

d = [4, 1, 6, 3, 2, 5, 2, 2, 0, 9]
quick_sort_hoare(d, 0, len(d))
print(d)

[0, 1, 2, 2, 2, 3, 4, 5, 6, 9]

На массиве из одинаковых значений Хоар ведёт себя иначе, чем Ломуто: обмены и продвижение обоих указателей делят массив примерно пополам, а не отделяют по одному элементу за вызов.

Если времени мало — разбираем схему стрелками и контракт; самостоятельная реализация на семинаре обязательна только для Ломуто.

7. Быстрая сортировка: время, опорный, память

Хорошее деление. Части сопоставимы по размеру: $\Theta(n)$ работы на уровень, $\Theta(\log n)$ уровней, итого $\Theta(n\log n)$.

Плохое деление. Каждый раз отделяется 0 и $n-1$ элементов. Суммарная работа $n + (n-1) + \dots + 1 = \Theta(n^2)$, глубина рекурсии $\Theta(n)$. Для разбиения Ломуто с последним опорным такой вход — уже отсортированный массив различных чисел.

Случайный опорный. Перед разбиением выбираем случайный индекс и переносим выбранный элемент в конец. Для различных ключей ожидаемое время $\Theta(n\log n)$ на любом фиксированном входе; ожидание берётся по случайным выборам алгоритма. Худшее время при этом остаётся $\Theta(n^2)$: рандомизация не отменяет плохой случай, а делает его маловероятным.

Посчитаем сравнения ключей при $n = 64$:

In [13]:

import random

random.seed(42)
cmp_count = 0


def partition_lomuto_counted(a, l, r):
    global cmp_count
    pivot = a[r - 1]
    i = l
    for j in range(l, r - 1):
        cmp_count += 1
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[r - 1] = a[r - 1], a[i]
    return i


def quick_sort_lomuto_counted(a, l, r):
    if r - l <= 1:
        return
    p = partition_lomuto_counted(a, l, r)
    quick_sort_lomuto_counted(a, l, p)
    quick_sort_lomuto_counted(a, p + 1, r)


def quick_sort_random_counted(a, l, r):
    # Та же схема, но опорный выбирается случайно.
    global cmp_count
    if r - l <= 1:
        return
    k = random.randrange(l, r)
    a[k], a[r - 1] = a[r - 1], a[k]
    p = partition_lomuto_counted(a, l, r)
    quick_sort_random_counted(a, l, p)
    quick_sort_random_counted(a, p + 1, r)

In [14]:

n = 64
print("n =", n, " n(n-1)/2 =", n * (n - 1) // 2, " n*log2(n) =", n * 6)
for name, data in [("возрастающий", list(range(n))),
                   ("убывающий", list(range(n, 0, -1))),
                   ("случайный", random.sample(range(n), n))]:
    cmp_count = 0
    quick_sort_lomuto_counted(data[:], 0, n)
    last_pivot = cmp_count
    cmp_count = 0
    quick_sort_random_counted(data[:], 0, n)
    random_pivot = cmp_count
    print(name + ":", "последний опорный", last_pivot, " случайный опорный", random_pivot)

n = 64  n(n-1)/2 = 2016  n*log2(n) = 384
возрастающий: последний опорный 2016  случайный опорный 369
убывающий: последний опорный 2016  случайный опорный 332
случайный: последний опорный 324  случайный опорный 406

Числа совпадают с теорией: на упорядоченном входе Ломуто с последним опорным делает $\frac{n(n-1)}{2} = 2016$ сравнений — это $\Theta(n^2)$. Случайный опорный на том же входе даёт порядок $n\log n$. Меняется только выбор опорного, сам вход остаётся фиксированным. На случайном входе оба варианта уже близки к $n\log n$.

Повторяющиеся ключи. На массиве из одинаковых значений выбранный вариант Ломуто всё равно отделяет лишь один элемент, и случайный опорный здесь не спасает. Решение — трёхчастное разбиение на <, =, >; реализацию не разбираем. Хоар на равных элементах ведёт себя иначе благодаря обменам и продвижению обоих указателей.

Память. Разбиение на месте — это $O(1)$ на один вызов, но не $O(1)$ на всю сортировку: остаётся стек вызовов. В обычной версии стек $\Theta(\log n)$ при хорошем делении и $\Theta(n)$ при вырождении; для рандомизированной версии на различных ключах ожидаемый размер стека $O(\log n)$. Большой вырожденный вход в Python упирается в RecursionError раньше, чем закончится замер:

In [15]:

big = list(range(2000))
try:
    quick_sort_lomuto_counted(big, 0, len(big))
    print("отсортировано без ошибки")
except RecursionError:
    print("RecursionError: вырожденное дерево глубины 2000 не помещается в стек вызовов Python")

RecursionError: вырожденное дерево глубины 2000 не помещается в стек вызовов Python

Устойчивость. Обычные разбиения неустойчивы. Контрпример для Ломуто: [2a, 2b, 1] после разбиения превращается в [1, 2b, 2a].

In [16]:

pair = [Item(2, "2a"), Item(2, "2b"), Item(1, "1")]
print("вход:           ", pair)
p = partition_lomuto(pair, 0, len(pair))
print("после разбиения:", pair, " p =", p)

вход:            [2a, 2b, 1]
после разбиения: [1, 2b, 2a]  p = 0

8. Закрепление базовых вопросов по асимптотике

Последняя лекция перед коллоквиумом. Сначала задаём вопрос группе и даём 20–30 секунд на ответ, затем фиксируем точную формулировку. Новую теорию здесь не вводим.

8.1. Что именно оцениваем?

Вопрос. «Время алгоритма — $O(n^2)$». Чего не хватает в таком ответе?

Ожидаем. Не указано, что такое $n$ (размер входа), какая модель стоимости операций и какой случай рассматривается — например, время в худшем случае для массива из $n$ элементов в модели RAM. Для примеров ниже считаем сравнение и обмен элементов за $O(1)$.

Вопрос. $O$ — это худший случай, $\Omega$ — лучший, $\Theta$ — средний?

Ответ. Нет. Сначала выбираем функцию стоимости — например, максимум времени по входам размера $n$, — а потом оцениваем её сверху, снизу или с двух сторон.

Для неотрицательных функций при достаточно больших $n$:

$f(n)=O(g(n))$: существуют $C>0$ и $n_0$, при всех $n\ge n_0$ выполнено $f(n)\le C\cdot g(n)$;
$f(n)=\Omega(g(n))$: существуют $c>0$ и $n_0$, при всех $n\ge n_0$ выполнено $f(n)\ge c\cdot g(n)$;
$f(n)=\Theta(g(n))$: обе оценки одновременно.

Проверка. $3n+7$ — это $O(n^2)$? Да, но неточно: точная по порядку оценка — $\Theta(n)$. Константы и порог $n_0$ от $n$ не зависят.

8.2. Как складывать стоимость действий?

На доске короткие схемы, без запуска таймера:

Вопрос	Ожидаемый ответ
Два последовательных прохода длины $n$	$\Theta(n)+\Theta(n)=\Theta(n)$, не $\Theta(n^2)$
Для каждого $i$ от $0$ до $n-1$ выполнить $i$ действий	$0+1+\dots+(n-1)=\Theta(n^2)$
В цикле целое $k=n$ заменяется на $k//2$, пока $k>0$	$\Theta(\log n)$ итераций при $n\ge 2$
Бинпоиск делает $\Theta(\log M)$ проверок, каждая стоит $\Theta(n)$	$\Theta(n\log M)$: размер массива и размер шкалы ответа — разные параметры

Число вложенных циклов само по себе асимптотику не определяет: считаем реально выполненные действия. Если про проверку известно только $O(n)$, то и для результата гарантируем только верхнюю оценку $O(n\log M)$.

8.3. Рекурсия, случаи и нижняя оценка

Вопрос. Почему две рекурсивные сортировки могут иметь разную сложность?

Ответ. Важны размеры подзадач и работа в каждом вызове. У merge sort суммарно $\Theta(n)$ работы на уровне и $\Theta(\log n)$ уровней. У вырожденного quick sort работы $n+(n-1)+\dots+1$.

Вопрос. Бинарный поиск по $\Theta(\log n)$ уровням и merge sort по $\Theta(\log n)$ уровням — это одно время?

Ответ. Нет. В бинарном поиске один активный диапазон и $O(1)$ работы на шаг; merge sort обрабатывает обе половины, на целом уровне $\Theta(n)$ работы. Высота дерева не равна общему времени.

Вопрос. Рандомизация quick sort даёт гарантию $O(n\log n)$ в худшем случае?

Ответ. Нет. При различных ключах получаем ожидаемую оценку по случайным выборам опорного для фиксированного входа; худшее время остаётся $\Theta(n^2)$.

Вопрос. Сортировка подсчётом нарушает нижнюю оценку $\Omega(n\log n)$?

Ответ. Нет. Нижняя оценка относится к худшему случаю сортировки произвольных различных ключей в модели сравнений. Подсчёт использует значения как индексы и стоит $\Theta(n+U)$, где $U$ — размер диапазона ключей.

Вопрос. Почему мастер-теорема не даёт оценку вырожденного quick sort?

Ответ. Она применима к рекурренте вида $aT(n/b)+\Theta(n^c)$ с $b>1$. При вырождении получается $T(n)=T(n-1)+\Theta(n)$, то есть $b=1$: остаётся сумма $n+(n-1)+\dots+1=\Theta(n^2)$.

8.4. Время и память — отдельные оценки

Вопрос. За всё выполнение выделено много списков. Нужно сложить их размеры, чтобы оценить дополнительную память?

Ответ. Считаем максимум одновременно занятой дополнительной памяти, а не суммарный объём выделений за всё время. У merge sort со срезами пиковая память $\Theta(n)$, хотя суммарно копируется $\Theta(n\log n)$ элементов.

Вопрос. Quick sort переставляет элементы внутри массива. Значит, дополнительная память $O(1)$?

Ответ. $O(1)$ у самого разбиения, но есть стек вызовов: $\Theta(\log n)$ при хорошем делении и $\Theta(n)$ при вырождении обычной рекурсивной реализации.

Вопрос. Можно ли доказать $\Theta(n\log n)$, измерив несколько времён запуска?

Ответ. Замеры помогают проверить гипотезу, но не заменяют подсчёт операций и обоснование оценки.

Формула ответа на коллоквиуме: «Что считаю → какой случай и модель → откуда число операций → оценка времени → отдельно дополнительная память».

9. Сравнение, семинар и коллоквиум

Свойство	Merge sort	Quick sort с Ломуто
Время в худшем случае	$\Theta(n\log n)$	$\Theta(n^2)$
Ожидаемое время при случайном опорном и различных ключах	$\Theta(n\log n)$, рандомизация не нужна	$\Theta(n\log n)$
Дополнительная память	$\Theta(n)$	$O(\log n)$ в ожидании при тех же условиях; $\Theta(n)$ в худшем случае
Устойчивость	да, если при равенстве берём слева	нет
Основная работа	слияние после рекурсивных вызовов	разбиение до рекурсивных вызовов

Не обещаем, что quick sort всегда быстрее по фактическому времени: результат зависит от реализации, данных и среды.

Семинар 5: слияние, merge sort, разбиение Ломуто, quick sort, проверка устойчивости, случайные и специально плохие входы. Малые размеры для демонстрации вырождения; ограничение глубины рекурсии учитываем при измерениях.

К коллоквиуму 1

формулировать $O$, $\Omega$, $\Theta$ и отделять вид оценки от выбора случая; считать стоимость последовательных действий, циклов и рекурсивных вызовов;
показать базу и уменьшение задачи в обеих сортировках;
выполнить слияние и один проход Ломуто на маленьком массиве;
объяснить отличие контрактов Ломуто и Хоара;
обосновать корректность через меньшие задачи и контракт вспомогательной операции;
получить $n\log n$ по уровням и $n^2$ по вырожденному дереву;
различать память буфера, глубину стека и общее число вызовов;
объяснить устойчивость и условия ожидаемой оценки quick sort.

Мастер-теорема — инструмент этой лекции; в обязательную программу коллоквиума 1 она не входит: там достаточно дерева уровней.

Код Хоара наизусть и доказательство математического ожидания не требуются. Блок ADT «стек, очередь, дек» — лекция 7.

Материалы

Сценарий пары — plans/lec05.md. Опираемся на лекцию 3 (sem1/03/lecture.ipynb) и лекцию 4 (sem1/04/lecture.ipynb); слияние двух упорядоченных массивов разбиралось на семинаре 2 (sem1/02/seminar.ipynb).

Программа коллоквиума 1 — plans/colloquium01.md.