{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "intro",
   "metadata": {},
   "source": [
    "# Семинар 5. Разделяй и властвуй: merge sort и quick sort\n",
    "\n",
    "Лекция 5 дала слияние, сортировку слиянием, разбиения Ломуто и Хоара, худший случай и случайный опорный. Здесь вы пишете это руками: сначала слияние, потом сортировку слиянием, потом разбиение и быструю сортировку.\n",
    "\n",
    "**Встроенную сортировку сегодня не используем как решение.** `sorted()` и `a.sort()` допустимы только как **эталон проверки**: с ними сравниваем свой результат. Это условие пары, а не ограничение тестера.\n",
    "\n",
    "Ноутбук — тетрадь пары. **Его семинаристу не отправляйте.** Зачёт пары — прорешанность задач контеста на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n",
    "\n",
    "Заглушки ничего не сортируют и возвращают неверный ответ — так и задумано, их надо переписать."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "jupyter",
   "metadata": {},
   "source": [
    "## Как устроен ноутбук\n",
    "\n",
    "Как на семинарах 1–4: ячейки **Markdown** и **Code**; командный режим — `Esc`, правка — `Enter`; `Shift+Enter` выполняет ячейку.\n",
    "\n",
    "Скачайте с сайта курса [этот файл `.ipynb`](https://learn.ai.msu.ru/algo/1/05/seminar.ipynb). Отдельного файла тестов на этой неделе нет: проверки встроены в ноутбук, зачёт — контест на платформе.\n",
    "\n",
    "Ячейки с комментарием «Ваш эксперимент» никто автоматически не проверяет."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "roadmap",
   "metadata": {},
   "source": [
    "## Порядок работы\n",
    "\n",
    "Номера в заголовках разделов соответствуют этому списку:\n",
    "\n",
    "- инструменты проверки: `is_sorted`, `check_sort`, `check_pairs_sort`, `check_partition`;\n",
    "- **1.** слияние двух упорядоченных массивов;\n",
    "- **2.** сортировка слиянием и устойчивость по ключу;\n",
    "- **3.** разбиение Ломуто и проверка его контракта;\n",
    "- **4.** быстрая сортировка: границы рекурсии, глубина на плохом входе, случайный опорный;\n",
    "- **5.** почему quick sort неустойчив — и чем контракт Хоара отличается от Ломуто;\n",
    "- **6.** трёхчастное разбиение (нужно для задачи № 6); `quickselect` и подсчёт инверсий — по желанию;\n",
    "- контест на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n",
    "\n",
    "Разделы 1–5 — основная часть пары. В разделе 6 трёхчастное разбиение нужно для обязательной задачи № 6, остальное — по желанию."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "tools_md",
   "metadata": {},
   "source": [
    "## Инструменты проверки\n",
    "\n",
    "Эти функции уже написаны, их менять не нужно. `check_sort` прогоняет вашу сортировку на случайных массивах и печатает первый вход, на котором она ошиблась.\n",
    "\n",
    "Здесь `sorted()` стоит **внутри проверки**, а не внутри решения: сравнивать свой ответ с эталоном — нормальная практика, сдавать эталон вместо решения — нет."
   ]
  },
  {
   "cell_type": "code",
   "id": "tools_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "\n",
    "def is_sorted(a):\n",
    "    \"\"\"Массив неубывает?\"\"\"\n",
    "    return all(a[i] <= a[i + 1] for i in range(len(a) - 1))\n",
    "\n",
    "\n",
    "def check_sort(sort_fn, in_place=False, trials=200, seed=0):\n",
    "    \"\"\"Проверяет сортировку на случайных массивах; sorted() — только эталон.\n",
    "\n",
    "    seed фиксирован, поэтому неудача воспроизводится: набор входов один и тот же.\n",
    "    \"\"\"\n",
    "    rng = random.Random(seed)\n",
    "    for _ in range(trials):\n",
    "        a = [rng.randint(-5, 5) for _ in range(rng.randint(0, 12))]\n",
    "        expected = sorted(a)\n",
    "        if in_place:\n",
    "            got = a[:]\n",
    "            sort_fn(got)\n",
    "        else:\n",
    "            got = sort_fn(a[:])\n",
    "        if got != expected:\n",
    "            print(\"не сходится на\", a)\n",
    "            print(\"  получено: \", got)\n",
    "            print(\"  ожидается:\", expected)\n",
    "            return False\n",
    "    print(f\"ok: {trials} случайных массивов отсортированы верно\")\n",
    "    return True\n",
    "\n",
    "\n",
    "def check_pairs_sort(sort_pairs_fn, trials=200, seed=0):\n",
    "    \"\"\"Сортировка пар по ключу и её устойчивость.\n",
    "\n",
    "    Эталон — sorted с ключом x[0]: встроенная сортировка устойчива, поэтому\n",
    "    пары с равными ключами обязаны остаться в порядке входа.\n",
    "    \"\"\"\n",
    "    rng = random.Random(seed)\n",
    "    for _ in range(trials):\n",
    "        keys = [rng.randint(0, 3) for _ in range(rng.randint(0, 10))]\n",
    "        payload = list(range(len(keys)))\n",
    "        rng.shuffle(payload)\n",
    "        pairs = list(zip(keys, payload))\n",
    "        expected = sorted(pairs, key=lambda x: x[0])\n",
    "        got = sort_pairs_fn(pairs[:])\n",
    "        if got != expected:\n",
    "            print(\"не сходится на\", pairs)\n",
    "            print(\"  получено: \", got)\n",
    "            print(\"  ожидается:\", expected)\n",
    "            print(\"  подсказка: сравнивайте ключ x[0], а не пару целиком\")\n",
    "            return False\n",
    "    print(f\"ok: {trials} наборов пар отсортированы устойчиво по ключу\")\n",
    "    return True\n",
    "\n",
    "\n",
    "print(\"инструменты готовы\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "merge_md",
   "metadata": {},
   "source": [
    "## 1. Слияние двух упорядоченных массивов\n",
    "\n",
    "Два уже неубывающих массива `left` и `right`. Держим два указателя на первые ещё не взятые элементы. Меньшую **голову** переносим в результат и сдвигаем её указатель. Когда один массив кончился, дописываем остаток другого.\n",
    "\n",
    "**Инвариант.** Результат неубывает, и каждый ещё не взятый элемент не меньше последнего выданного. Минимум из оставшихся всегда лежит на одной из двух голов — поэтому смотреть дальше голов не нужно.\n",
    "\n",
    "**Равные ключи.** При равенстве берите из **левого** массива: `left[i] <= right[j]`. На этом стоит устойчивость сортировки слиянием.\n",
    "\n",
    "Время — линейное от суммы длин. Обратите внимание на пустые массивы: отдельной ветки для них быть не должно, цикл просто не сделает ни шага."
   ]
  },
  {
   "cell_type": "code",
   "id": "merge_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def merge(left, right):\n",
    "    \"\"\"Слияние двух неубывающих массивов в новый неубывающий массив.\"\"\"\n",
    "    return []\n",
    "\n",
    "\n",
    "print(merge([1, 4, 7], [2, 4, 8]))  # ожидается [1, 2, 4, 4, 7, 8]\n",
    "print(merge([], [1, 2]))            # ожидается [1, 2]\n",
    "print(merge([3], []))               # ожидается [3]\n",
    "print(merge([1, 2, 3], [4, 5]))     # ожидается [1, 2, 3, 4, 5]"
   ]
  },
  {
   "cell_type": "code",
   "id": "merge_exp",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Ваш эксперимент: сколько сравнений делает слияние в лучшем и худшем случае?\n",
    "# Добавьте счётчик и проверьте на [1, 2, 3] + [4, 5, 6] и на [1, 3, 5] + [2, 4, 6]."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ms_md",
   "metadata": {},
   "source": [
    "## 2. Сортировка слиянием\n",
    "\n",
    "Рекурсивная схема ровно с лекции:\n",
    "\n",
    "- **база** — ноль или один элемент, такой массив уже упорядочен;\n",
    "- **шаг** — разрезать пополам, отсортировать половины **тем же способом**, слить.\n",
    "\n",
    "```\n",
    "        [5 1 4 2 | 8 3 7 6]\n",
    "       /                   \\\n",
    "   [5 1 4 2]             [8 3 7 6]\n",
    "    /     \\               /     \\\n",
    " [5 1]   [4 2]        [8 3]   [7 6]\n",
    "```\n",
    "\n",
    "Сначала полностью завершается левый вызов, затем правый, и только потом слияние. На каждом уровне суммарно линейная работа, уровней $\\Theta(\\log n)$, итого $\\Theta(n\\log n)$ — **всегда**, в том числе на уже отсортированном входе.\n",
    "\n",
    "Версия ниже возвращает **новый** список и не портит вход. Срезы `a[:m]` и `a[m:]` копируют данные: это те самые $\\Theta(n)$ дополнительной памяти."
   ]
  },
  {
   "cell_type": "code",
   "id": "ms_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def merge_sort(a):\n",
    "    \"\"\"Новый неубывающий список из элементов a; вход не меняется.\"\"\"\n",
    "    return []\n",
    "\n",
    "\n",
    "print(merge_sort([5, 1, 4, 2, 8, 3, 7, 6]))  # ожидается [1, 2, 3, 4, 5, 6, 7, 8]\n",
    "print(merge_sort([]), merge_sort([7]))        # ожидается [] [7]\n",
    "\n",
    "original = [3, 1, 2]\n",
    "merge_sort(original)\n",
    "print(original)  # ожидается [3, 1, 2] — вход не испорчен\n",
    "\n",
    "check_sort(merge_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "stable_md",
   "metadata": {},
   "source": [
    "### Устойчивость по ключу\n",
    "\n",
    "Теперь сортируем пары `(ключ, нагрузка)` **только по ключу**. Устойчивость означает: пары с равными ключами остались в том же относительном порядке, что во входе.\n",
    "\n",
    "Сравнивайте именно ключ, `x[0]`, а не пару целиком. Если сравнить пары целиком, порядок равных ключей задаст нагрузка — это уже другая задача."
   ]
  },
  {
   "cell_type": "code",
   "id": "stable_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def merge_sort_pairs(pairs):\n",
    "    \"\"\"Сортировка пар (ключ, нагрузка) по ключу; при равных ключах порядок как во входе.\"\"\"\n",
    "    return []\n",
    "\n",
    "\n",
    "print(merge_sort_pairs([(2, \"a\"), (1, \"c\"), (2, \"b\")]))\n",
    "# ожидается [(1, 'c'), (2, 'a'), (2, 'b')] — 'a' раньше 'b', как во входе\n",
    "\n",
    "print(merge_sort_pairs([(5, \"x\"), (5, \"y\"), (5, \"z\")]))\n",
    "# ожидается [(5, 'x'), (5, 'y'), (5, 'z')] — порядок не меняется\n",
    "\n",
    "print(merge_sort_pairs([(2, \"b\"), (1, \"c\"), (2, \"a\")]))\n",
    "# ожидается [(1, 'c'), (2, 'b'), (2, 'a')]\n",
    "# если вышло [(1, 'c'), (2, 'a'), (2, 'b')] — пары сравниваются целиком, а не по ключу\n",
    "\n",
    "check_pairs_sort(merge_sort_pairs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lomuto_md",
   "metadata": {},
   "source": [
    "## 3. Разбиение Ломуто\n",
    "\n",
    "Работаем с полуинтервалом `[l, r)` внутри массива, **на месте**. Опорный элемент — последний в диапазоне: `pivot = a[r-1]`.\n",
    "\n",
    "Перед обработкой позиции `j` держим четыре зоны:\n",
    "\n",
    "| Зона | Что там |\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`. В конце меняем `a[i]` и `a[r-1]` — опорный встаёт на **окончательную** позицию `p = i`, которую возвращаем.\n",
    "\n",
    "Сравнение строгое `<`. Разбиение — это ещё не сортировка: обе части могут остаться неупорядоченными.\n",
    "\n",
    "Пример с лекции: `[4, 1, 6, 3, 2, 5]` превращается в `[4, 1, 3, 2, 5, 6]`, `p = 4`."
   ]
  },
  {
   "cell_type": "code",
   "id": "lomuto_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def partition_lomuto(a, l, r):\n",
    "    \"\"\"Разбивает a[l:r] по опорному a[r-1]; возвращает окончательную позицию опорного.\"\"\"\n",
    "    return -1\n",
    "\n",
    "\n",
    "a = [4, 1, 6, 3, 2, 5]\n",
    "p = partition_lomuto(a, 0, len(a))\n",
    "print(a, \"p =\", p)  # ожидается [4, 1, 3, 2, 5, 6] p = 4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "contract_md",
   "metadata": {},
   "source": [
    "### Проверка контракта\n",
    "\n",
    "Своими глазами один пример — мало. Эта проверка написана за вас: она берёт случайные массивы, вызывает ваше разбиение и убеждается, что слева от опорного все элементы строго меньше, справа — не меньше, а сам набор элементов не изменился."
   ]
  },
  {
   "cell_type": "code",
   "id": "contract_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def check_partition(partition_fn, trials=200, seed=0):\n",
    "    \"\"\"Проверяет контракт разбиения на случайных массивах.\n",
    "\n",
    "    seed фиксирован, поэтому неудача воспроизводится.\n",
    "    \"\"\"\n",
    "    rng = random.Random(seed)\n",
    "    for _ in range(trials):\n",
    "        a = [rng.randint(-5, 5) for _ in range(rng.randint(1, 12))]\n",
    "        b = a[:]\n",
    "        p = partition_fn(b, 0, len(b))\n",
    "        if not isinstance(p, int) or not 0 <= p < len(b):\n",
    "            print(\"позиция вне диапазона:\", a, \"->\", b, \"p =\", p)\n",
    "            return False\n",
    "        pivot = b[p]\n",
    "        if sorted(b) != sorted(a):\n",
    "            print(\"элементы потеряны:\", a, \"->\", b)\n",
    "            return False\n",
    "        if any(x >= pivot for x in b[:p]) or any(x < pivot for x in b[p + 1:]):\n",
    "            print(\"контракт нарушен:\", a, \"->\", b, \"p =\", p)\n",
    "            return False\n",
    "    print(f\"ok: контракт держится на {trials} массивах\")\n",
    "    return True\n",
    "\n",
    "\n",
    "check_partition(partition_lomuto)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "qs_md",
   "metadata": {},
   "source": [
    "## 4. Быстрая сортировка\n",
    "\n",
    "Опорный уже стоит на своём месте, поэтому его позиция в рекурсивные вызовы **не входит**:\n",
    "\n",
    "```python\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)\n",
    "```\n",
    "\n",
    "Диапазоны `[l, p)` и `[p+1, r)` строго короче родительского даже при крайнем `p` — поэтому рекурсия заканчивается.\n",
    "\n",
    "Параметр `depth` и переменная `max_depth` нужны только для замера: дальше мы посмотрим, как глубина зависит от входа. Сортировка идёт **на месте**, функция ничего не возвращает."
   ]
  },
  {
   "cell_type": "code",
   "id": "qs_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "max_depth = 0\n",
    "\n",
    "\n",
    "def quick_sort(a, l, r, depth=0):\n",
    "    \"\"\"Сортирует a[l:r] на месте разбиением Ломуто; depth — только для замера глубины.\"\"\"\n",
    "    global max_depth\n",
    "    max_depth = max(max_depth, depth)\n",
    "    return None\n",
    "\n",
    "\n",
    "b = [4, 1, 6, 3, 2, 5]\n",
    "quick_sort(b, 0, len(b))\n",
    "print(b)  # ожидается [1, 2, 3, 4, 5, 6]\n",
    "\n",
    "check_sort(lambda x: quick_sort(x, 0, len(x)), in_place=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "worst_md",
   "metadata": {},
   "source": [
    "### Плохой вход и глубина рекурсии\n",
    "\n",
    "У Ломуто с последним опорным элементом уже **отсортированный** массив различных чисел даёт вырожденное дерево: каждое разбиение отделяет один элемент, глубина растёт как $n$, а работа — как $n^2$.\n",
    "\n",
    "Ячейка ниже сравнивает случайный вход и отсортированный на $n = 500$. Ожидаемый порядок величин: у случайного глубина — десятки, у отсортированного — около 500.\n",
    "\n",
    "Отсюда практическое следствие: на $n$ в несколько тысяч такой вход упрётся в лимит глубины рекурсии Python и вы получите `RecursionError` вместо результата."
   ]
  },
  {
   "cell_type": "code",
   "id": "worst_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "n = 500\n",
    "inputs = {\n",
    "    \"случайный\": [random.randint(0, 10 ** 6) for _ in range(n)],\n",
    "    \"уже отсортированный\": list(range(n)),\n",
    "}\n",
    "\n",
    "for name, data in inputs.items():\n",
    "    max_depth = 0\n",
    "    b = data[:]\n",
    "    quick_sort(b, 0, len(b))\n",
    "    print(f\"{name}: глубина {max_depth}, отсортирован: {is_sorted(b)}\")\n",
    "\n",
    "# Ваш эксперимент: добавьте вход list(range(n, 0, -1)) — массив, упорядоченный по убыванию.\n",
    "# Предскажите глубину до запуска."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "rand_md",
   "metadata": {},
   "source": [
    "### Случайный опорный элемент\n",
    "\n",
    "Лечится не сам худший случай, а его привязка к конкретному входу: перед разбиением выбираем **случайный** индекс в `[l, r)` и меняем этот элемент с последним. Дальше — то же разбиение Ломуто.\n",
    "\n",
    "Для различных ключей ожидаемое время становится $\\Theta(n\\log n)$ на любом фиксированном входе, но худший случай остаётся квадратичным: он просто перестаёт достигаться отсортированным массивом.\n",
    "\n",
    "На массиве из **одинаковых** значений это не помогает: выбранный вариант Ломуто всё равно отделяет по одному элементу. Проверьте сами."
   ]
  },
  {
   "cell_type": "code",
   "id": "rand_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "n = 500          # тот же размер, что выше, но задан локально: ячейку можно запускать отдельно\n",
    "\n",
    "\n",
    "def quick_sort_random(a, l, r, depth=0):\n",
    "    \"\"\"То же, но опорный выбирается случайно и переносится в конец перед разбиением.\"\"\"\n",
    "    global max_depth\n",
    "    max_depth = max(max_depth, depth)\n",
    "    return None\n",
    "\n",
    "\n",
    "check_sort(lambda x: quick_sort_random(x, 0, len(x)), in_place=True)\n",
    "\n",
    "for name, data in ((\"уже отсортированный\", list(range(n))),\n",
    "                   (\"все элементы равны\", [7] * n)):\n",
    "    max_depth = 0\n",
    "    b = data[:]\n",
    "    quick_sort_random(b, 0, len(b))\n",
    "    print(f\"{name}: глубина {max_depth}, отсортирован: {is_sorted(b)}\")\n",
    "\n",
    "# Ожидание: на отсортированном глубина падает до десятков,\n",
    "# на массиве из равных значений остаётся около n."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unstable_md",
   "metadata": {},
   "source": [
    "## 5. Почему quick sort неустойчив\n",
    "\n",
    "Слияние можно заставить брать при равенстве левый элемент — и сортировка слиянием становится устойчивой. У разбиения такого рычага нет: оно переставляет элементы обменами через весь диапазон.\n",
    "\n",
    "Контрпример с лекции: пары `(2, 'a')`, `(2, 'b')`, `(1, 'c')`. Одно разбиение Ломуто уже переставляет `'a'` и `'b'` местами."
   ]
  },
  {
   "cell_type": "code",
   "id": "unstable_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# partition_lomuto сравнивает элементы целиком. Здесь все сравнения идут между\n",
    "# разными ключами (2 и 1), поэтому результат тот же, что при сравнении только ключа.\n",
    "pairs = [(2, \"a\"), (2, \"b\"), (1, \"c\")]\n",
    "p = partition_lomuto(pairs, 0, len(pairs))\n",
    "print(pairs, \"p =\", p)\n",
    "# ожидается [(1, 'c'), (2, 'b'), (2, 'a')] p = 0\n",
    "# ключи упорядочены верно, но 'b' оказалась раньше 'a' — устойчивость сломана"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "extra_md",
   "metadata": {},
   "source": [
    "## 6. По желанию и для контеста\n",
    "\n",
    "Три упражнения. **Трёхчастное разбиение нужно для обязательной задачи № 6 (75. Sort Colors)** — идею разберём у доски, код пишете сами. `quickselect` (№ 7) и подсчёт инверсий (№ 9) — по желанию, для зачёта не требуются."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "three_md",
   "metadata": {},
   "source": [
    "### Трёхчастное разбиение — нужно для № 6\n",
    "\n",
    "Лекция упоминала проблему одинаковых ключей: Ломуто на массиве равных значений вырождается. Лечение — разбить сразу на **три** части: `< pivot`, `= pivot`, `> pivot`. Тогда все равные опорному уходят из рекурсии за один проход.\n",
    "\n",
    "Держим три границы и идём по массиву один раз: `lt` — конец зоны меньших, `i` — текущая позиция, `gt` — начало зоны больших. Функция возвращает пару `(lt, gt)`: равные опорному занимают полуинтервал `[lt, gt)`."
   ]
  },
  {
   "cell_type": "code",
   "id": "three_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def partition_three(a, pivot):\n",
    "    \"\"\"Переставляет a на месте: сначала < pivot, потом = pivot, потом > pivot.\n",
    "\n",
    "    Возвращает (lt, gt): равные опорному лежат в полуинтервале [lt, gt).\n",
    "    \"\"\"\n",
    "    return (-1, -1)\n",
    "\n",
    "\n",
    "b = [2, 0, 2, 1, 1, 0]\n",
    "print(partition_three(b, 1), b)  # ожидается (2, 4) [0, 0, 1, 1, 2, 2]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "select_md",
   "metadata": {},
   "source": [
    "### ★ Порядковая статистика без полной сортировки\n",
    "\n",
    "Разбиение даёт больше, чем сортировку. После него опорный стоит на окончательной позиции `p`. Если нужен элемент, который в упорядоченном массиве стоял бы на позиции `k`, то:\n",
    "\n",
    "- `p == k` — это и есть ответ;\n",
    "- `p > k` — ответ слева, продолжаем в `[l, p)`;\n",
    "- `p < k` — ответ справа, продолжаем в `[p+1, r)`.\n",
    "\n",
    "Рекурсивный вызов нужен только **один** — как в бинарном поиске. Поэтому в среднем работа линейная, а не $n\\log n$: полностью сортировать массив не требуется."
   ]
  },
  {
   "cell_type": "code",
   "id": "select_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def kth_smallest(a, k):\n",
    "    \"\"\"Элемент, который стоял бы на позиции k (от нуля) в упорядоченном a; вход не менять.\"\"\"\n",
    "    return -1\n",
    "\n",
    "\n",
    "data = [3, 2, 1, 5, 6, 4]\n",
    "print([kth_smallest(data, k) for k in range(len(data))])  # ожидается [1, 2, 3, 4, 5, 6]\n",
    "print(data)  # ожидается [3, 2, 1, 5, 6, 4] — вход не испорчен\n",
    "\n",
    "# В задаче № 7 (215) просят k-й наибольший, и k там с единицы:\n",
    "# ответ — kth_smallest(a, len(a) - k)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "inv_md",
   "metadata": {},
   "source": [
    "### ★ Слияние считает больше, чем сортирует\n",
    "\n",
    "**Инверсия** — пара индексов $i < j$, для которой $a[i] > a[j]$. Число инверсий показывает, насколько массив далёк от упорядоченного: у отсортированного их ноль, у развёрнутого — максимум.\n",
    "\n",
    "Двойным циклом это $\\Theta(n^2)$. Но слияние уже знает ответ: когда вы берёте элемент из **правой** половины, он меньше всех оставшихся в левой — а значит, образует инверсию с каждым из них сразу. Добавьте к счётчику число оставшихся в левой половине.\n",
    "\n",
    "Инверсии внутри половин считают рекурсивные вызовы, а слияние добавляет только те пары, у которых один элемент слева, другой справа."
   ]
  },
  {
   "cell_type": "code",
   "id": "inv_code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def count_inversions(a):\n",
    "    \"\"\"Число пар i < j с a[i] > a[j]; вход не менять.\"\"\"\n",
    "    return -1\n",
    "\n",
    "\n",
    "print(count_inversions([2, 4, 1, 3, 5]))  # ожидается 3\n",
    "print(count_inversions([1, 2, 3]))        # ожидается 0\n",
    "print(count_inversions([3, 2, 1]))        # ожидается 3\n",
    "print(count_inversions([]))               # ожидается 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "contest",
   "metadata": {},
   "source": [
    "## Контест\n",
    "\n",
    "Задачи сдавайте в контест недели 5 на [algo.ai.msu.ru](https://algo.ai.msu.ru). Номера LeetCode помогают найти условие.\n",
    "\n",
    "**Для зачёта семинара обязательны № 5 (912. Sort an Array) и № 6 (75. Sort Colors).** Разминка и задачи по желанию их не заменяют.\n",
    "\n",
    "| № | Задача | Статус на семинаре | Что из ноутбука |\n",
    "| --- | --- | --- | --- |\n",
    "| 1 | 88. Merge Sorted Array | Разминка | `merge`; здесь его просят сделать на месте, с конца |\n",
    "| 2 | 977. Squares of a Sorted Array | Разминка | то же слияние, только две монотонные части нужно сначала увидеть |\n",
    "| 3 | 283. Move Zeroes | Разминка | цикл Ломуто: указатель записи и указатель просмотра |\n",
    "| 4 | 905. Sort Array By Parity | Разминка | разбиение по предикату; сравните схему Ломуто и встречные указатели |\n",
    "| 5 | 912. Sort an Array | **Обязательная** | `merge_sort` — рабочий вариант; `quick_sort` годится на различных ключах |\n",
    "| 6 | 75. Sort Colors | **Обязательная** | `partition_three` за один проход |\n",
    "| 7 | 215. Kth Largest Element in an Array | По желанию | `kth_smallest`; сортировка проходит тесты, но на паре нужен `quickselect` |\n",
    "| 8 | 56. Merge Intervals | По желанию | сортировка как подготовка к линейному проходу |\n",
    "| 9 | 493. Reverse Pairs ★ | По желанию | `count_inversions`; условие считает пары с $a[i] > 2\\cdot a[j]$ |\n",
    "\n",
    "**Порядок работы.** Разминку № 1–4 закрывайте быстро, они на один приём каждая. Главная задача пары — № 5: в ней встроенную сортировку использовать нельзя по условию, и именно там пригодится случайный опорный. Дальше № 6. Остальное — по желанию и дома.\n",
    "\n",
    "Типичный **WA**: при равенстве в слиянии берут из правой половины и теряют устойчивость; в Ломуто сравнивают нестрого; опорный оставляют в одном из рекурсивных диапазонов; в трёхчастном разбиении сдвигают `i` после обмена с зоной больших.\n",
    "\n",
    "Типичный **TLE** и `RecursionError`: quick sort с последним опорным на отсортированном входе; полная сортировка там, где нужна одна порядковая статистика; пересборка списков срезами внутри цикла.\n",
    "\n",
    "**Про встроенную сортировку.** В № 5 (912) она запрещена условием самой задачи. В № 8 (56) сортировка — только подготовительный шаг: там `sorted()` допустим и решением не считается. В проверках ноутбука `sorted()` — эталон.\n",
    "\n",
    "**Про № 5 и глубину рекурсии.** В 912 длина массива до 5·10⁴. Уже отсортированный вход с последним опорным даёт вырожденное дерево и `RecursionError` (лимит Python около 1000). Рабочий рецепт — merge sort: $\\Theta(n\\log n)$ на любом входе и глубина $\\Theta(\\log n)$. Поднимать `sys.setrecursionlimit` под Ломуто не стоит: на различных ключах случайный опорный и так даёт глубину порядка логарифма, а на одинаковых ключах Ломуто по-прежнему отделяет один элемент — глубина около $n$ и время $\\Theta(n^2)$, так что вместо `RecursionError` будет превышение по времени."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cheatsheet",
   "metadata": {},
   "source": [
    "## Шпаргалка\n",
    "\n",
    "Слияние и merge sort:\n",
    "\n",
    "- смотрим только две головы; при равенстве берём **слева** — это устойчивость;\n",
    "- база рекурсии — ноль или один элемент;\n",
    "- $\\Theta(n\\log n)$ всегда, в том числе на отсортированном входе;\n",
    "- пиковая дополнительная память $\\Theta(n)$, глубина $\\Theta(\\log n)$.\n",
    "\n",
    "Разбиение и quick sort:\n",
    "\n",
    "- Ломуто: опорный `a[r-1]`, зоны `[l, i)` и `[i, j)`, строгое `<`, в конце опорный на позиции `p`;\n",
    "- позиция `p` в рекурсивные вызовы не входит: `[l, p)` и `[p+1, r)`;\n",
    "- отсортированный вход + последний опорный = вырожденное дерево, $\\Theta(n^2)$ и глубина $n$;\n",
    "- случайный опорный даёт ожидаемое $\\Theta(n\\log n)$ при различных ключах, но не гарантию в худшем случае;\n",
    "- одинаковые ключи лечит трёхчастное разбиение, а не рандомизация;\n",
    "- разбиение на месте — это $O(1)$ памяти у разбиения, но не у всей сортировки: остаётся стек вызовов;\n",
    "- обычные разбиения неустойчивы.\n",
    "\n",
    "Контракт Хоара (спросят на коллоквиуме):\n",
    "\n",
    "- Ломуто возвращает окончательную позицию опорного `p`: рекурсия на `[l, p)` и `[p+1, r)`, опорный в вызовы не входит;\n",
    "- Хоар возвращает границу `b`, причём `l < b < r`: опорный не обязан стоять на месте, рекурсия на `[l, b)` и `[b, r)`, обе части непусты.\n",
    "\n",
    "Контест: № 5 (912) — до 5·10⁴ элементов. Рабочий рецепт — merge sort: $\\Theta(n\\log n)$ и глубина $\\Theta(\\log n)$; поднимать лимит рекурсии под Ломуто бессмысленно — на одинаковых ключах он даёт глубину около $n$ и время $\\Theta(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "submit",
   "metadata": {},
   "source": [
    "## Сдача\n",
    "\n",
    "- **Этот** `.ipynb` семинаристу отправлять не нужно.\n",
    "- Для зачёта выполните **№ 5 — 912. Sort an Array** и **№ 6 — 75. Sort Colors** в контесте на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n",
    "- Разминка № 1–4 и задачи № 7–9 выполняются по желанию, для зачёта не требуются.\n",
    "- Если обязательные задачи не закончены на паре, дорешайте их в том же контесте после занятия.\n",
    "- На неделе 6 — коллоквиум по лекциям 1–5. Слияние, merge sort, разбиение Ломуто и Хоара, худший случай и память входят в программу; спросят и трассировку на маленьком массиве."
   ]
  }
 ],
 "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}