{ "cells": [ { "cell_type": "markdown", "id": "lec05-000", "metadata": {}, "source": [ "# Лекция 5. Разделяй и властвуй: сортировки слиянием и Хоара\n", "\n", "На лекции 3 были квадратичные сортировки и нижняя оценка $\\Omega(n\\log n)$ в модели сравнений. Сегодня строим алгоритмы, которые до этой границы дотягиваются: сортировку слиянием — гарантированно, быструю сортировку — в ожидании при оговорённых условиях.\n", "\n", "Опираемся на лекцию 3 (сортировка, устойчивость, нижняя оценка) и лекцию 4 (рекурсия, база и шаг, стек вызовов). Слияние двух упорядоченных массивов уже встречалось на семинаре 2. Первые пять минут — входной тест по лекциям 2–4: три короткие задачи, чтобы проверить базу перед коллоквиумом.\n", "\n", "## План\n", "\n", "**Разминка: входной тест** по лекциям 2–4 — три задачи, 5 минут.\n", "0. Мастер-теорема: рекуррента $aT(n/b)+\\Theta(n^c)$ и три случая.\n", "1. Зачем ещё две сортировки: «разделяй и властвуй» и контракт сортировки.\n", "2. Слияние двух упорядоченных массивов: два указателя, инвариант, устойчивость.\n", "3. Сортировка слиянием: рекурсивная схема, корректность, дерево, время и память.\n", "4. Идея быстрой сортировки: работа до рекурсивных вызовов.\n", "5. Разбиение Ломуто.\n", "6. Разбиение Хоара: другой контракт и другие границы.\n", "7. Быстрая сортировка: хорошее и плохое дерево, случайный опорный, повторяющиеся ключи, память.\n", "8. Закрепление базовых вопросов по асимптотике перед коллоквиумом.\n", "9. Сравнение двух сортировок, семинар и программа коллоквиума.\n", "\n", "Это лекция: рекурсивную схему смотрим кодом, внутренние циклы слияния и разбиения разбираем через инвариант и ручную трассировку. Полные реализации закрепляем на семинаре 5. Лекция идёт **до** семинара.\n", "\n", "Стек, очередь и дек как абстрактные типы данных — лекция 7; в программу коллоквиума 1 этот материал не входит." ] }, { "cell_type": "markdown", "id": "lec05-001", "metadata": {}, "source": [ "## Входной тест: три задачи по лекциям 2–4\n", "\n", "Разогрев на 5 минут перед новой теорией. Это не оценка, а проверка, что база прошлых лекций на месте: сначала отвечает группа, потом открываем ячейку с проверкой.\n", "\n", "**1. Асимптотика (лекция 2).** Два последовательных прохода по массиву длины $n$ — это $\\Theta(n)$ или $\\Theta(n^2)$?\n", "\n", "**2. Устойчивость (лекция 3).** Отсортируйте устойчиво по ключу: `[(2, \"б\"), (1, \"а\"), (2, \"в\")]`.\n", "\n", "**3. Бинпоиск (лекция 4).** В массиве `[1, 3, 5, 7, 9]` найдите `lower_bound(7)` — первый индекс с `a[i] >= 7`." ] }, { "cell_type": "markdown", "id": "lec05-003", "metadata": {}, "source": [ "## 0. Мастер-теорема\n", "\n", "Перед сортировками — короткий инструмент. Он позволит оценивать «разделяй и властвуй» одной формулой, а не рисовать дерево заново для каждой задачи. Это именно инструмент: в программу коллоквиума 1 он не входит.\n", "\n", "**Рекуррента «разделяй и властвуй».** Задача размера $n$ делится на $a$ подзадач размера $n/b$, а сборка ответа (слияние, разбиение) стоит $\\Theta(n^c)$:\n", "\n", "$$T(n) = a\\,T(n/b) + \\Theta(n^c), \\qquad T(n) = \\Theta(1) \\text{ при } n \\le n_0.$$\n", "\n", "**Мастер-теорема.** Сравним показатель сборки $c$ с $\\log_b a$:\n", "\n", "- **A.** $c > \\log_b a$: $T(n) = \\Theta(n^c)$ — работа в корне перевешивает;\n", "- **B.** $c = \\log_b a$: $T(n) = \\Theta(n^c\\log n)$ — уровни равнозначны, их $\\log_b n$;\n", "- **C.** $c < \\log_b a$: $T(n) = \\Theta(n^{\\log_b a})$ — перевешивают листья.\n", "\n", "**Откуда три случая.** Дерево рекурсии: $\\log_b n$ уровней, на $k$-м уровне $a^k$ вершин, каждая стоит $(n/b^k)^c$. Сумма по уровням — геометрическая прогрессия со знаменателем $a/b^c$:\n", "\n", "$$T(n) = n^c \\sum_{k=0}^{\\log_b n} \\left(\\frac{a}{b^c}\\right)^k.$$\n", "\n", "Её режим зависит от того, больше знаменатель единицы, равен ей или меньше. Это ровно та картинка уровней, которой мы будем объяснять merge sort, только в общем виде. Полное доказательство не выводим.\n", "\n", "Проверка без логарифмов: сравниваем $b^c$ и $a$ — это то же самое, что сравнивать $c$ и $\\log_b a$." ] }, { "cell_type": "code", "execution_count": 2, "id": "lec05-004", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "бинарный поиск: a=1 b=2 c=0 -> B: Theta(log n)\n", "merge sort: a=2 b=2 c=1 -> B: Theta(n log n)\n", "слияние за Theta(n^2): a=2 b=2 c=2 -> A: Theta(n^2)\n", "четыре подзадачи, линейная сборка: a=4 b=2 c=1 -> C: Theta(n^2)\n" ] } ], "source": [ "def master_case(a, b, c):\n", " # Сравниваем b**c с a — это то же, что сравнивать c и log_b(a), но без логарифмов.\n", " if b ** c > a:\n", " return f\"A: Theta(n^{c})\"\n", " if b ** c == a:\n", " if c == 0:\n", " base = \"log n\"\n", " elif c == 1:\n", " base = \"n log n\"\n", " else:\n", " base = f\"n^{c} log n\"\n", " return f\"B: Theta({base})\"\n", " k = 0\n", " while b ** k < a:\n", " k += 1\n", " return f\"C: Theta(n^{k})\"\n", "\n", "\n", "recurrences = [\n", " (\"бинарный поиск\", 1, 2, 0),\n", " (\"merge sort\", 2, 2, 1),\n", " (\"слияние за Theta(n^2)\", 2, 2, 2),\n", " (\"четыре подзадачи, линейная сборка\", 4, 2, 1),\n", "]\n", "for name, a, b, c in recurrences:\n", " print(f\"{name}: a={a} b={b} c={c} -> {master_case(a, b, c)}\")" ] }, { "cell_type": "markdown", "id": "lec05-005", "metadata": {}, "source": [ "**Границы применимости.** Сборка должна быть $\\Theta(n^c)$, то есть полиномиальной: слияние за $\\Theta(n\\log n)$ в теорему не укладывается. И рекуррента обязана иметь вид $aT(n/b)$ с $b > 1$: вырожденный quick sort даёт $T(n)=T(n-1)+\\Theta(n)$ — это $b=1$, и его мы разберём отдельно деревом в разделе 7." ] }, { "cell_type": "markdown", "id": "lec05-006", "metadata": {}, "source": [ "## 1. Зачем ещё две сортировки\n", "\n", "На лекции 3 квадратичные сортировки давали $\\Theta(n^2)$ сравнений. Нижняя оценка говорит, что в модели сравнений быстрее $\\Omega(n\\log n)$ в худшем случае не получится. Осталось построить алгоритмы, которые этого порядка **достигают**.\n", "\n", "**Разделяй и властвуй:** разделить задачу на меньшие, решить их тем же способом, собрать ответ для целого. В бинарном поиске после сравнения оставался один диапазон. Для сортировки так не выйдет: упорядочить нужно обе части, а потом соединить их.\n", "\n", "**Контракт сортировки.** Результат неубывает и содержит те же элементы с теми же кратностями: ничего не потеряно и ничего не добавлено.\n", "\n", "**База рекурсии:** 0 или 1 элемент — сортировать нечего. Чтобы рекурсия завершилась, каждый дочерний диапазон должен быть **строго меньше** родительского.\n", "\n", "Для диапазонов массива используем полуинтервалы $[l, r)$ — тот же договор, что в бинарном поиске. Но условие остановки другое: сортировка заканчивается уже при $r - l \\le 1$, а не при $l = r$." ] }, { "cell_type": "markdown", "id": "lec05-007", "metadata": {}, "source": [ "## 2. Слияние двух упорядоченных массивов\n", "\n", "Пример: `[1, 4a, 7]` и `[2, 4b, 6]`. Буквы — метки элементов; сравниваем **только числовой ключ**. Метка нужна, чтобы увидеть устойчивость: при равных ключах $4a$ и $4b$ порядок входа должен сохраниться.\n", "\n", "Два указателя стоят на первых ещё не взятых элементах. Меньшую голову переносим в результат и сдвигаем её указатель. Когда один массив исчерпан, дописываем остаток другого.\n", "\n", "**Инвариант.** Результат содержит уже взятые элементы в неубывающем порядке; каждый оставшийся элемент не меньше последнего выданного. Значит, минимальный из оставшихся лежит на одной из двух голов: сравнивать достаточно их.\n", "\n", "**Устойчивость.** При равенстве ключей берём из **левого** массива. В сортировке слиянием левая половина стояла раньше правой, поэтому $4a$ останется перед $4b$.\n", "\n", "Время $\\Theta(p+q)$, где $p$ и $q$ — длины массивов: каждый элемент переносится ровно один раз. Буфер под результат — $\\Theta(p+q)$.\n", "\n", "Сравнение элементов сделаем по ключу: опишем элемент с ключом и меткой." ] }, { "cell_type": "code", "execution_count": 1, "id": "lec05-008", "metadata": {}, "outputs": [], "source": [ "class Item:\n", " # Элемент с ключом и полезной нагрузкой; сравнение — только по ключу.\n", " def __init__(self, key, label):\n", " self.key = key\n", " self.label = label\n", "\n", " def __lt__(self, other):\n", " return self.key < other.key\n", "\n", " def __le__(self, other):\n", " return self.key <= other.key\n", "\n", " def __repr__(self):\n", " return self.label\n", "\n", "\n", "def merge(left, right):\n", " # Слить два неубывающих массива в новый неубывающий.\n", " result = []\n", " i = j = 0\n", " while i < len(left) and j < len(right):\n", " if left[i] <= right[j]: # при равенстве ключей берём из левого\n", " result.append(left[i])\n", " i += 1\n", " else:\n", " result.append(right[j])\n", " j += 1\n", " result.extend(left[i:]) # остаток одного из массивов\n", " result.extend(right[j:])\n", " return result" ] }, { "cell_type": "code", "execution_count": 2, "id": "lec05-009", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "слева: [1, 4a, 7]\n", "справа: [2, 4b, 6]\n", "слияние: [1, 2, 4a, 4b, 6, 7]\n" ] } ], "source": [ "left = [Item(1, \"1\"), Item(4, \"4a\"), Item(7, \"7\")]\n", "right = [Item(2, \"2\"), Item(4, \"4b\"), Item(6, \"6\")]\n", "print(\"слева: \", left)\n", "print(\"справа: \", right)\n", "print(\"слияние:\", merge(left, right))" ] }, { "cell_type": "markdown", "id": "lec05-010", "metadata": {}, "source": [ "Разберём шаги на этом примере:\n", "\n", "| Шаг | Сравниваем | Берём | Результат |\n", "| --- | --- | --- | --- |\n", "| 1 | $1$ и $2$ | $1$ | `[1]` |\n", "| 2 | $4a$ и $2$ | $2$ | `[1, 2]` |\n", "| 3 | $4a$ и $4b$ | $4a$ — берём слева | `[1, 2, 4a]` |\n", "| 4 | $7$ и $4b$ | $4b$ | `[1, 2, 4a, 4b]` |\n", "| 5 | $7$ и $6$ | $6$ | `[1, 2, 4a, 4b, 6]` |\n", "| 6 | левый исчерпан | хвост `[7]` | `[1, 2, 4a, 4b, 6, 7]` |\n", "\n", "Полный цикл слияния соберёте на семинаре 5. Здесь важно, почему один проход даёт линейное время и откуда берётся устойчивость." ] }, { "cell_type": "markdown", "id": "lec05-011", "metadata": {}, "source": [ "## 3. Сортировка слиянием\n", "\n", "**Схема.** Делим массив пополам, сортируем обе половины тем же алгоритмом, соединяем слиянием. Сначала **целиком** завершается левый вызов, затем правый, и только потом выполняется слияние.\n", "\n", "Перед запуском стоит спросить: когда выполнится первый вызов `merge`? Только после того, как обе половины вернутся отсортированными." ] }, { "cell_type": "code", "execution_count": 3, "id": "lec05-012", "metadata": {}, "outputs": [], "source": [ "def merge_sort(a):\n", " # Вернуть новый отсортированный список; исходный не меняется.\n", " if len(a) <= 1: # база: 0 или 1 элемент\n", " return a[:]\n", " m = len(a) // 2\n", " left = merge_sort(a[:m])\n", " right = merge_sort(a[m:])\n", " return merge(left, right)" ] }, { "cell_type": "code", "execution_count": 4, "id": "lec05-013", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "вход: [5, 1, 4, 2, 8, 3, 7, 6]\n", "выход: [1, 2, 3, 4, 5, 6, 7, 8]\n", "исходный не изменился: [5, 1, 4, 2, 8, 3, 7, 6]\n" ] } ], "source": [ "a = [5, 1, 4, 2, 8, 3, 7, 6]\n", "print(\"вход: \", a)\n", "print(\"выход: \", merge_sort(a))\n", "print(\"исходный не изменился:\", a)" ] }, { "cell_type": "markdown", "id": "lec05-014", "metadata": {}, "source": [ "На доске то же самое: вниз — деление до единичных массивов, вверх — слияние. Дерево всех вызовов и текущая цепочка активных вызовов — разные объекты: одновременно занята память только одной ветви.\n", "\n", "Посмотрим на порядок работы явно:" ] }, { "cell_type": "code", "execution_count": 5, "id": "lec05-015", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "делим [5, 1, 4, 2, 8, 3, 7, 6]\n", " делим [5, 1, 4, 2]\n", " делим [5, 1]\n", " делим [5]\n", " делим [1]\n", " слили [1, 5]\n", " делим [4, 2]\n", " делим [4]\n", " делим [2]\n", " слили [2, 4]\n", " слили [1, 2, 4, 5]\n", " делим [8, 3, 7, 6]\n", " делим [8, 3]\n", " делим [8]\n", " делим [3]\n", " слили [3, 8]\n", " делим [7, 6]\n", " делим [7]\n", " делим [6]\n", " слили [6, 7]\n", " слили [3, 6, 7, 8]\n", "слили [1, 2, 3, 4, 5, 6, 7, 8]\n" ] }, { "data": { "text/plain": [ "[1, 2, 3, 4, 5, 6, 7, 8]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def merge_sort_trace(a, depth=0):\n", " # Печатает деление и слияние, возвращает отсортированный список.\n", " print(\" \" * depth + \"делим\", a)\n", " if len(a) <= 1:\n", " return a[:]\n", " m = len(a) // 2\n", " left = merge_sort_trace(a[:m], depth + 1)\n", " right = merge_sort_trace(a[m:], depth + 1)\n", " result = merge(left, right)\n", " print(\" \" * depth + \"слили\", result)\n", " return result\n", "\n", "\n", "merge_sort_trace([5, 1, 4, 2, 8, 3, 7, 6])" ] }, { "cell_type": "markdown", "id": "lec05-016", "metadata": {}, "source": [ "**Корректность.** База: массив длины 0 или 1 уже упорядочен. Шаг: по предположению обе половины отсортированы и содержат те же элементы; слияние даёт неубывающий результат и сохраняет все элементы с кратностями. Размеры половин меньше размера целого, поэтому рекурсия завершается.\n", "\n", "**Время.** Пусть $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)$. Ту же оценку полезно увидеть и деревом уровней. На уже отсортированном массиве оценка та же: слияние всегда проходит все элементы.\n", "\n", "**Память.** Дополнительный буфер под слияние — $\\Theta(n)$ в пике, глубина рекурсии — $\\Theta(\\log n)$. В показанной версии срезы `a[:m]` и `a[m:]` тоже копируют данные: они не бесплатны, и суммарно за всё выполнение копируется $\\Theta(n\\log n)$ элементов. Но **пиковая одновременно занятая** дополнительная память — $\\Theta(n)$. В реализации по индексам можно переиспользовать один буфер.\n", "\n", "**Устойчивость** следует из устойчивого слияния.\n", "\n", "> На коллоквиуме достаточно нарисовать дерево уровней и объяснить пиковый расход памяти: складывать все копирования за время работы не нужно." ] }, { "cell_type": "markdown", "id": "lec05-017", "metadata": {}, "source": [ "## 4. Быстрая сортировка: работа до рекурсивных вызовов\n", "\n", "**Быстрая сортировка** — сортировка Хоара. Важно не путать название алгоритма и конкретную схему разбиения: quick sort можно реализовать и с разбиением Ломуто, и с разбиением Хоара.\n", "\n", "Выбираем опорное значение и переставляем элементы так, чтобы части можно было сортировать **независимо**. Главная работа идёт до рекурсивных вызовов; отдельного слияния результатов нет.\n", "\n", "| | Merge sort | Quick sort |\n", "| --- | --- | --- |\n", "| Размеры частей | всегда примерно равны | зависят от опорного |\n", "| Как разделены | по позициям, значения перемешаны | по значениям |\n", "| Основная работа | слияние после вызовов | разбиение до вызовов |\n", "\n", "Именно из-за неравных частей у quick sort появляется худший случай." ] }, { "cell_type": "markdown", "id": "lec05-018", "metadata": {}, "source": [ "## 5. Разбиение Ломуто\n", "\n", "**Договор.** Обрабатываем полуинтервал `[l, r)`, опорный — **последний** элемент: `pivot = a[r-1]`. В проходе сравнение **строгое**: `a[j] < pivot`.\n", "\n", "Перед обработкой позиции `j` выполнено:\n", "\n", "- `[l, i)` — элементы `< pivot`;\n", "- `[i, j)` — элементы `>= pivot`;\n", "- `[j, r-1)` — ещё не просмотрены;\n", "- `a[r-1]` — сохранённый опорный.\n", "\n", "Если `a[j] < pivot`, меняем `a[i]` и `a[j]` и увеличиваем `i`; затем увеличиваем `j`. В конце меняем `a[i]` и `a[r-1]`: опорный встаёт на **окончательную** позицию `p = i`.\n", "\n", "Разберём полный проход на `[4, 1, 6, 3, 2, 5]`." ] }, { "cell_type": "code", "execution_count": 6, "id": "lec05-019", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "опорный: 5 массив: [4, 1, 6, 3, 2, 5]\n", " j = 0 : [4, 1, 6, 3, 2, 5] i = 1\n", " j = 1 : [4, 1, 6, 3, 2, 5] i = 2\n", " j = 2 : [4, 1, 6, 3, 2, 5] i = 2\n", " j = 3 : [4, 1, 3, 6, 2, 5] i = 3\n", " j = 4 : [4, 1, 3, 2, 6, 5] i = 4\n", "после обмена с опорным: [4, 1, 3, 2, 5, 6] p = 4\n", "слева: [4, 1, 3, 2] опорный: 5 справа: [6]\n" ] } ], "source": [ "def partition_lomuto_trace(a, l, r):\n", " # Печатает состояние массива после каждой позиции прохода.\n", " pivot = a[r - 1]\n", " print(\"опорный:\", pivot, \" массив:\", a)\n", " i = l\n", " for j in range(l, r - 1):\n", " if a[j] < pivot:\n", " a[i], a[j] = a[j], a[i]\n", " i += 1\n", " print(\" j =\", j, \":\", a, \" i =\", i)\n", " a[i], a[r - 1] = a[r - 1], a[i]\n", " print(\"после обмена с опорным:\", a, \" p =\", i)\n", " return i\n", "\n", "\n", "b = [4, 1, 6, 3, 2, 5]\n", "p = partition_lomuto_trace(b, 0, len(b))\n", "print(\"слева:\", b[:p], \" опорный:\", b[p], \" справа:\", b[p + 1:])" ] }, { "cell_type": "markdown", "id": "lec05-020", "metadata": {}, "source": [ "Получили `[4, 1, 3, 2, 5, 6]` и `p = 4`. Опорный `5` стоит там, где и должен, но обе части **ещё не отсортированы** — их предстоит отсортировать рекурсивно.\n", "\n", "Разбиение стоит $\\Theta(r-l)$ времени и $O(1)$ дополнительной памяти. Опорный исключается из обоих рекурсивных вызовов, поэтому диапазоны строго уменьшаются даже при крайнем `p`." ] }, { "cell_type": "code", "execution_count": 7, "id": "lec05-021", "metadata": {}, "outputs": [], "source": [ "def partition_lomuto(a, l, r):\n", " # Разбиение [l, r) вокруг a[r-1]; возвращает индекс опорного.\n", " pivot = a[r - 1]\n", " i = l\n", " for j in range(l, r - 1):\n", " if a[j] < pivot:\n", " a[i], a[j] = a[j], a[i]\n", " i += 1\n", " a[i], a[r - 1] = a[r - 1], a[i]\n", " return i\n", "\n", "\n", "def quick_sort(a, l, r):\n", " if r - l <= 1:\n", " return\n", " p = partition_lomuto(a, l, r)\n", " quick_sort(a, l, p) # опорный не входит ни в одну часть\n", " quick_sort(a, p + 1, r)" ] }, { "cell_type": "code", "execution_count": 8, "id": "lec05-022", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 3, 4, 5, 6]\n" ] } ], "source": [ "c = [4, 1, 6, 3, 2, 5]\n", "quick_sort(c, 0, len(c))\n", "print(c)" ] }, { "cell_type": "markdown", "id": "lec05-023", "metadata": {}, "source": [ "## 6. Разбиение Хоара\n", "\n", "Для непустого диапазона длины хотя бы 2 сохраняем **значение** `pivot = a[(l+r-1)//2]`. Начинаем с `i = l-1`, `j = r`: указатели сначала делают шаг внутрь, а затем ищут\n", "\n", "- слева — первый элемент `>= pivot`;\n", "- справа — первый элемент `<= pivot`.\n", "\n", "Если `i < j`, меняем элементы и продолжаем. Иначе возвращаем границу `b = j + 1`.\n", "\n", "При каждом повторе каждый указатель делает хотя бы один шаг, поэтому равные опорному элементы не могут остановить продвижение и зациклить проход." ] }, { "cell_type": "code", "execution_count": 10, "id": "lec05-024", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "pivot = 6 массив: [4, 1, 6, 3, 2, 5]\n", " i = 2 a[i] = 6 j = 5 a[j] = 5\n", " обмен: [4, 1, 5, 3, 2, 6]\n", " i = 5 a[i] = 6 j = 4 a[j] = 2\n", " указатели сошлись: возвращаем 5\n", "части: [4, 1, 5, 3, 2] | [6]\n", "\n", "pivot = 2 массив: [2, 2, 2, 2]\n", " i = 0 a[i] = 2 j = 3 a[j] = 2\n", " обмен: [2, 2, 2, 2]\n", " i = 1 a[i] = 2 j = 2 a[j] = 2\n", " обмен: [2, 2, 2, 2]\n", " i = 2 a[i] = 2 j = 1 a[j] = 2\n", " указатели сошлись: возвращаем 2\n", "части: [2, 2] | [2, 2]\n", "\n" ] } ], "source": [ "def partition_hoare_trace(a, l, r):\n", " # Печатает, где останавливаются указатели и что меняется местами.\n", " pivot = a[(l + r - 1) // 2]\n", " print(\"pivot =\", pivot, \" массив:\", a)\n", " i, j = l - 1, r\n", " while True:\n", " i += 1\n", " while a[i] < pivot:\n", " i += 1\n", " j -= 1\n", " while a[j] > pivot:\n", " j -= 1\n", " print(\" i =\", i, \"a[i] =\", a[i], \" j =\", j, \"a[j] =\", a[j])\n", " if i >= j:\n", " print(\" указатели сошлись: возвращаем\", j + 1)\n", " return j + 1\n", " a[i], a[j] = a[j], a[i]\n", " print(\" обмен:\", a)\n", "\n", "\n", "for arr in ([4, 1, 6, 3, 2, 5], [2, 2, 2, 2]):\n", " data = arr[:]\n", " b = partition_hoare_trace(data, 0, len(data))\n", " print(\"части:\", data[:b], \"|\", data[b:])\n", " print()" ] }, { "cell_type": "markdown", "id": "lec05-025", "metadata": {}, "source": [ "**Контракт отличается от Ломуто.** Получаем две **непустые** части `[l, b)` и `[b, r)`: в левой элементы `<= pivot`, в правой `>= pivot`. Сам опорный элемент не обязан стоять на окончательном месте.\n", "\n", "Рекурсивно сортируем именно эти две части, **без пропуска позиции `b`**. Для этой схемы выбор нижней середины и продвижение обоих указателей обеспечивают `l < b < r`. Не смешивайте код одной схемы с границами рекурсии другой." ] }, { "cell_type": "code", "execution_count": 11, "id": "lec05-026", "metadata": {}, "outputs": [], "source": [ "def partition_hoare(a, l, r):\n", " # Разбиение [l, r), r - l >= 2; возвращает границу b, l < b < r.\n", " pivot = a[(l + r - 1) // 2] # значение, не индекс\n", " i, j = l - 1, r\n", " while True:\n", " i += 1\n", " while a[i] < pivot:\n", " i += 1\n", " j -= 1\n", " while a[j] > pivot:\n", " j -= 1\n", " if i >= j:\n", " return j + 1\n", " a[i], a[j] = a[j], a[i]\n", "\n", "\n", "def quick_sort_hoare(a, l, r):\n", " if r - l <= 1:\n", " return\n", " b = partition_hoare(a, l, r)\n", " quick_sort_hoare(a, l, b) # без пропуска позиции b\n", " quick_sort_hoare(a, b, r)" ] }, { "cell_type": "code", "execution_count": 12, "id": "lec05-027", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 2, 2, 2, 3, 4, 5, 6, 9]\n" ] } ], "source": [ "d = [4, 1, 6, 3, 2, 5, 2, 2, 0, 9]\n", "quick_sort_hoare(d, 0, len(d))\n", "print(d)" ] }, { "cell_type": "markdown", "id": "lec05-028", "metadata": {}, "source": [ "На массиве из одинаковых значений Хоар ведёт себя иначе, чем Ломуто: обмены и продвижение обоих указателей делят массив примерно пополам, а не отделяют по одному элементу за вызов.\n", "\n", "Если времени мало — разбираем схему стрелками и контракт; самостоятельная реализация на семинаре обязательна только для Ломуто." ] }, { "cell_type": "markdown", "id": "lec05-029", "metadata": {}, "source": [ "## 7. Быстрая сортировка: время, опорный, память\n", "\n", "**Хорошее деление.** Части сопоставимы по размеру: $\\Theta(n)$ работы на уровень, $\\Theta(\\log n)$ уровней, итого $\\Theta(n\\log n)$.\n", "\n", "**Плохое деление.** Каждый раз отделяется 0 и $n-1$ элементов. Суммарная работа $n + (n-1) + \\dots + 1 = \\Theta(n^2)$, глубина рекурсии $\\Theta(n)$. Для разбиения Ломуто с последним опорным такой вход — уже **отсортированный массив различных чисел**.\n", "\n", "**Случайный опорный.** Перед разбиением выбираем случайный индекс и переносим выбранный элемент в конец. Для различных ключей ожидаемое время $\\Theta(n\\log n)$ **на любом фиксированном входе**; ожидание берётся по случайным выборам алгоритма. Худшее время при этом остаётся $\\Theta(n^2)$: рандомизация не отменяет плохой случай, а делает его маловероятным.\n", "\n", "Посчитаем сравнения ключей при $n = 64$:" ] }, { "cell_type": "code", "execution_count": 13, "id": "lec05-030", "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "random.seed(42)\n", "cmp_count = 0\n", "\n", "\n", "def partition_lomuto_counted(a, l, r):\n", " global cmp_count\n", " pivot = a[r - 1]\n", " i = l\n", " for j in range(l, r - 1):\n", " cmp_count += 1\n", " if a[j] < pivot:\n", " a[i], a[j] = a[j], a[i]\n", " i += 1\n", " a[i], a[r - 1] = a[r - 1], a[i]\n", " return i\n", "\n", "\n", "def quick_sort_lomuto_counted(a, l, r):\n", " if r - l <= 1:\n", " return\n", " p = partition_lomuto_counted(a, l, r)\n", " quick_sort_lomuto_counted(a, l, p)\n", " quick_sort_lomuto_counted(a, p + 1, r)\n", "\n", "\n", "def quick_sort_random_counted(a, l, r):\n", " # Та же схема, но опорный выбирается случайно.\n", " global cmp_count\n", " if r - l <= 1:\n", " return\n", " k = random.randrange(l, r)\n", " a[k], a[r - 1] = a[r - 1], a[k]\n", " p = partition_lomuto_counted(a, l, r)\n", " quick_sort_random_counted(a, l, p)\n", " quick_sort_random_counted(a, p + 1, r)" ] }, { "cell_type": "code", "execution_count": 14, "id": "lec05-031", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n = 64 n(n-1)/2 = 2016 n*log2(n) = 384\n", "возрастающий: последний опорный 2016 случайный опорный 369\n", "убывающий: последний опорный 2016 случайный опорный 332\n", "случайный: последний опорный 324 случайный опорный 406\n" ] } ], "source": [ "n = 64\n", "print(\"n =\", n, \" n(n-1)/2 =\", n * (n - 1) // 2, \" n*log2(n) =\", n * 6)\n", "for name, data in [(\"возрастающий\", list(range(n))),\n", " (\"убывающий\", list(range(n, 0, -1))),\n", " (\"случайный\", random.sample(range(n), n))]:\n", " cmp_count = 0\n", " quick_sort_lomuto_counted(data[:], 0, n)\n", " last_pivot = cmp_count\n", " cmp_count = 0\n", " quick_sort_random_counted(data[:], 0, n)\n", " random_pivot = cmp_count\n", " print(name + \":\", \"последний опорный\", last_pivot, \" случайный опорный\", random_pivot)" ] }, { "cell_type": "markdown", "id": "lec05-032", "metadata": {}, "source": [ "Числа совпадают с теорией: на упорядоченном входе Ломуто с последним опорным делает $\\frac{n(n-1)}{2} = 2016$ сравнений — это $\\Theta(n^2)$. Случайный опорный на том же входе даёт порядок $n\\log n$. Меняется только **выбор опорного**, сам вход остаётся фиксированным. На случайном входе оба варианта уже близки к $n\\log n$.\n", "\n", "**Повторяющиеся ключи.** На массиве из одинаковых значений выбранный вариант Ломуто всё равно отделяет лишь один элемент, и случайный опорный здесь не спасает. Решение — трёхчастное разбиение на `<`, `=`, `>`; реализацию не разбираем. Хоар на равных элементах ведёт себя иначе благодаря обменам и продвижению обоих указателей.\n", "\n", "**Память.** Разбиение на месте — это $O(1)$ **на один вызов**, но не $O(1)$ на всю сортировку: остаётся стек вызовов. В обычной версии стек $\\Theta(\\log n)$ при хорошем делении и $\\Theta(n)$ при вырождении; для рандомизированной версии на различных ключах ожидаемый размер стека $O(\\log n)$. Большой вырожденный вход в Python упирается в `RecursionError` раньше, чем закончится замер:" ] }, { "cell_type": "code", "execution_count": 15, "id": "lec05-033", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "RecursionError: вырожденное дерево глубины 2000 не помещается в стек вызовов Python\n" ] } ], "source": [ "big = list(range(2000))\n", "try:\n", " quick_sort_lomuto_counted(big, 0, len(big))\n", " print(\"отсортировано без ошибки\")\n", "except RecursionError:\n", " print(\"RecursionError: вырожденное дерево глубины 2000 не помещается в стек вызовов Python\")" ] }, { "cell_type": "markdown", "id": "lec05-034", "metadata": {}, "source": [ "**Устойчивость.** Обычные разбиения неустойчивы. Контрпример для Ломуто: `[2a, 2b, 1]` после разбиения превращается в `[1, 2b, 2a]`." ] }, { "cell_type": "code", "execution_count": 16, "id": "lec05-035", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "вход: [2a, 2b, 1]\n", "после разбиения: [1, 2b, 2a] p = 0\n" ] } ], "source": [ "pair = [Item(2, \"2a\"), Item(2, \"2b\"), Item(1, \"1\")]\n", "print(\"вход: \", pair)\n", "p = partition_lomuto(pair, 0, len(pair))\n", "print(\"после разбиения:\", pair, \" p =\", p)" ] }, { "cell_type": "markdown", "id": "lec05-036", "metadata": {}, "source": [ "## 8. Закрепление базовых вопросов по асимптотике\n", "\n", "Последняя лекция перед коллоквиумом. Сначала задаём вопрос группе и даём 20–30 секунд на ответ, затем фиксируем точную формулировку. Новую теорию здесь не вводим.\n", "\n", "### 8.1. Что именно оцениваем?\n", "\n", "**Вопрос.** «Время алгоритма — $O(n^2)$». Чего не хватает в таком ответе?\n", "\n", "**Ожидаем.** Не указано, что такое $n$ (размер входа), какая модель стоимости операций и **какой случай** рассматривается — например, время в худшем случае для массива из $n$ элементов в модели RAM. Для примеров ниже считаем сравнение и обмен элементов за $O(1)$.\n", "\n", "**Вопрос.** $O$ — это худший случай, $\\Omega$ — лучший, $\\Theta$ — средний?\n", "\n", "**Ответ.** Нет. Сначала выбираем функцию стоимости — например, максимум времени по входам размера $n$, — а потом оцениваем её сверху, снизу или с двух сторон.\n", "\n", "Для неотрицательных функций при достаточно больших $n$:\n", "\n", "- $f(n)=O(g(n))$: существуют $C>0$ и $n_0$, при всех $n\\ge n_0$ выполнено $f(n)\\le C\\cdot g(n)$;\n", "- $f(n)=\\Omega(g(n))$: существуют $c>0$ и $n_0$, при всех $n\\ge n_0$ выполнено $f(n)\\ge c\\cdot g(n)$;\n", "- $f(n)=\\Theta(g(n))$: обе оценки одновременно.\n", "\n", "**Проверка.** $3n+7$ — это $O(n^2)$? Да, но неточно: точная по порядку оценка — $\\Theta(n)$. Константы и порог $n_0$ от $n$ не зависят.\n", "\n", "### 8.2. Как складывать стоимость действий?\n", "\n", "На доске короткие схемы, без запуска таймера:\n", "\n", "| Вопрос | Ожидаемый ответ |\n", "| --- | --- |\n", "| Два последовательных прохода длины $n$ | $\\Theta(n)+\\Theta(n)=\\Theta(n)$, не $\\Theta(n^2)$ |\n", "| Для каждого $i$ от $0$ до $n-1$ выполнить $i$ действий | $0+1+\\dots+(n-1)=\\Theta(n^2)$ |\n", "| В цикле целое $k=n$ заменяется на $k//2$, пока $k>0$ | $\\Theta(\\log n)$ итераций при $n\\ge 2$ |\n", "| Бинпоиск делает $\\Theta(\\log M)$ проверок, каждая стоит $\\Theta(n)$ | $\\Theta(n\\log M)$: размер массива и размер шкалы ответа — разные параметры |\n", "\n", "Число вложенных циклов само по себе асимптотику не определяет: считаем реально выполненные действия. Если про проверку известно только $O(n)$, то и для результата гарантируем только верхнюю оценку $O(n\\log M)$.\n", "\n", "### 8.3. Рекурсия, случаи и нижняя оценка\n", "\n", "**Вопрос.** Почему две рекурсивные сортировки могут иметь разную сложность?\n", "\n", "**Ответ.** Важны размеры подзадач и работа в каждом вызове. У merge sort суммарно $\\Theta(n)$ работы на уровне и $\\Theta(\\log n)$ уровней. У вырожденного quick sort работы $n+(n-1)+\\dots+1$.\n", "\n", "**Вопрос.** Бинарный поиск по $\\Theta(\\log n)$ уровням и merge sort по $\\Theta(\\log n)$ уровням — это одно время?\n", "\n", "**Ответ.** Нет. В бинарном поиске один активный диапазон и $O(1)$ работы на шаг; merge sort обрабатывает обе половины, на целом уровне $\\Theta(n)$ работы. Высота дерева не равна общему времени.\n", "\n", "**Вопрос.** Рандомизация quick sort даёт гарантию $O(n\\log n)$ в худшем случае?\n", "\n", "**Ответ.** Нет. При различных ключах получаем ожидаемую оценку по случайным выборам опорного для фиксированного входа; худшее время остаётся $\\Theta(n^2)$.\n", "\n", "**Вопрос.** Сортировка подсчётом нарушает нижнюю оценку $\\Omega(n\\log n)$?\n", "\n", "**Ответ.** Нет. Нижняя оценка относится к худшему случаю сортировки произвольных различных ключей **в модели сравнений**. Подсчёт использует значения как индексы и стоит $\\Theta(n+U)$, где $U$ — размер диапазона ключей.\n", "\n", "**Вопрос.** Почему мастер-теорема не даёт оценку вырожденного quick sort?\n", "\n", "**Ответ.** Она применима к рекурренте вида $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)$.\n", "\n", "### 8.4. Время и память — отдельные оценки\n", "\n", "**Вопрос.** За всё выполнение выделено много списков. Нужно сложить их размеры, чтобы оценить дополнительную память?\n", "\n", "**Ответ.** Считаем максимум **одновременно занятой** дополнительной памяти, а не суммарный объём выделений за всё время. У merge sort со срезами пиковая память $\\Theta(n)$, хотя суммарно копируется $\\Theta(n\\log n)$ элементов.\n", "\n", "**Вопрос.** Quick sort переставляет элементы внутри массива. Значит, дополнительная память $O(1)$?\n", "\n", "**Ответ.** $O(1)$ у самого разбиения, но есть стек вызовов: $\\Theta(\\log n)$ при хорошем делении и $\\Theta(n)$ при вырождении обычной рекурсивной реализации.\n", "\n", "**Вопрос.** Можно ли доказать $\\Theta(n\\log n)$, измерив несколько времён запуска?\n", "\n", "**Ответ.** Замеры помогают проверить гипотезу, но не заменяют подсчёт операций и обоснование оценки.\n", "\n", "**Формула ответа на коллоквиуме:** «Что считаю → какой случай и модель → откуда число операций → оценка времени → **отдельно** дополнительная память»." ] }, { "cell_type": "markdown", "id": "lec05-037", "metadata": {}, "source": [ "## 9. Сравнение, семинар и коллоквиум\n", "\n", "| Свойство | Merge sort | Quick sort с Ломуто |\n", "| --- | --- | --- |\n", "| Время в худшем случае | $\\Theta(n\\log n)$ | $\\Theta(n^2)$ |\n", "| Ожидаемое время при случайном опорном и различных ключах | $\\Theta(n\\log n)$, рандомизация не нужна | $\\Theta(n\\log n)$ |\n", "| Дополнительная память | $\\Theta(n)$ | $O(\\log n)$ в ожидании при тех же условиях; $\\Theta(n)$ в худшем случае |\n", "| Устойчивость | да, если при равенстве берём слева | нет |\n", "| Основная работа | слияние после рекурсивных вызовов | разбиение до рекурсивных вызовов |\n", "\n", "Не обещаем, что quick sort всегда быстрее по фактическому времени: результат зависит от реализации, данных и среды.\n", "\n", "**Семинар 5:** слияние, merge sort, разбиение Ломуто, quick sort, проверка устойчивости, случайные и специально плохие входы. Малые размеры для демонстрации вырождения; ограничение глубины рекурсии учитываем при измерениях.\n", "\n", "### К коллоквиуму 1\n", "\n", "- формулировать $O$, $\\Omega$, $\\Theta$ и отделять вид оценки от выбора случая; считать стоимость последовательных действий, циклов и рекурсивных вызовов;\n", "- показать базу и уменьшение задачи в обеих сортировках;\n", "- выполнить слияние и один проход Ломуто на маленьком массиве;\n", "- объяснить отличие контрактов Ломуто и Хоара;\n", "- обосновать корректность через меньшие задачи и контракт вспомогательной операции;\n", "- получить $n\\log n$ по уровням и $n^2$ по вырожденному дереву;\n", "- различать память буфера, глубину стека и общее число вызовов;\n", "- объяснить устойчивость и условия ожидаемой оценки quick sort.\n", "\n", "Мастер-теорема — инструмент этой лекции; в обязательную программу коллоквиума 1 она не входит: там достаточно дерева уровней.\n", "\n", "Код Хоара наизусть и доказательство математического ожидания не требуются. Блок ADT «стек, очередь, дек» — лекция 7." ] }, { "cell_type": "markdown", "id": "lec05-038", "metadata": {}, "source": [ "## Материалы\n", "\n", "Сценарий пары — `plans/lec05.md`. Опираемся на лекцию 3 (`sem1/03/lecture.ipynb`) и лекцию 4 (`sem1/04/lecture.ipynb`); слияние двух упорядоченных массивов разбиралось на семинаре 2 (`sem1/02/seminar.ipynb`).\n", "\n", "Программа коллоквиума 1 — `plans/colloquium01.md`." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }