{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Семинар 3. Квадратичные и линейные сортировки\n",
        "\n",
        "На этой паре вы **напишете** проверку упорядоченности и несколько сортировок, снимете время и увидите, когда линейный метод обгоняет `sorted`. Лекция дала инварианты и картинки, а не готовые циклы: циклы собираете вы.\n",
        "\n",
        "Часть работы — **упражнения** в ячейках: график, замер, `all`/`any`, NaN, Fool, пузырёк, вставки, выбор, LSD. Их тестер не проверяет — смотрите на вывод сами. Четыре **задачи** с `input`/`print` — основа сдачи; пятая — запас, если закрыли первые четыре; шестая со звёздочкой — в самом конце, на паре её не разбираем.\n",
        "\n",
        "Сдаёте **этот** файл семинаристу. ДЗ к лекции 3 — отдельная страница (LaTeX, монетка выбирает вставки или выбор): https://learn.ai.msu.ru/algo/1/03/hw-lecture/ — сдаёте **лектору**, не семинаристу; код туда не писать.\n",
        "\n",
        "На больших тестах квадрат не успеет: тестер даёт **TLE** (лимит 2 секунды на тест), а не только «не тот ответ».\n",
        "\n",
        "Можно спрашивать соседа и семинариста. Готовое решение копировать не стоит: тесты это не заменят, а на зачёте рядом никого не будет.\n",
        "\n",
        ""
      ],
      "id": "intro"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Как устроен ноутбук\n",
        "\n",
        "Как на семинарах 1–2: ячейки **Markdown** и **Code**; командный режим — `Esc`, правка — `Enter`; `Shift+Enter` выполняет ячейку.\n",
        "\n",
        "Скачайте с сайта курса [этот файл `.ipynb`](https://learn.ai.msu.ru/algo/1/03/seminar.ipynb) и файл [`lab03_tests.py`](https://learn.ai.msu.ru/algo/1/03/lab03_tests.py) **в одну папку**. Без файла тестов проверка не запустится. Откройте ноутбук из этой папки.\n"
      ],
      "id": "jupyter"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Ввод, вывод и тесты\n",
        "\n",
        "Решение — **функция без аргументов**: внутри `input` и `print`, как в контесте. Тест подставляет входы сам. **Не заполняйте поле ввода Jupyter.**\n",
        "\n",
        "В каждой задаче стоит заглушка: она что-то читает и печатает неверный ответ. Сначала запустите ячейку: увидите «не OK» или TLE, вход, «ожидалось» и «получено». Потом замените тело функции.\n",
        "\n",
        "Импорт тестов стоит **в каждой** ячейке с решением. Если перезапустите ядро, достаточно снова выполнить эту ячейку — отдельно «подключать библиотеку в начале» не обязательно, хотя общая ячейка ниже тоже есть.\n"
      ],
      "id": "how_tests"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "\n",
        "from lab03_tests import (\n",
        "    test_task1,\n",
        "    test_task2,\n",
        "    test_task3,\n",
        "    test_task4,\n",
        "    test_task5,\n",
        "    test_task6,\n",
        ")\n",
        "\n",
        "print('Тесты подключены')\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "import_tests"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Порядок работы\n",
        "\n",
        "1. Замеры и графики: `%timeit`, `time.perf_counter`, Matplotlib.\n",
        "2. `all`/`any`, проверка неубывания — **задача 1**.\n",
        "3. Функции как объекты, `sort(key=…)`, устойчивость.\n",
        "4. NaN и сломанное сравнение.\n",
        "5. Квадратичные сортировки: Fool, пузырёк, вставки, выбор — **задача 2**, **задача 3**.\n",
        "6. Линейные: подсчёт — **задача 4**, LSD — **задача 5** (запас).\n",
        "7. Сравнение с `sorted` и **задача 6\\***.\n",
        "\n",
        "Ячейки с комментарием «Ваш эксперимент» тестер не проверяет: это место, чтобы потрогать руками и посмотреть на вывод.\n",
        "\n"
      ],
      "id": "roadmap"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Среда: график и замер\n",
        "\n",
        "При работе с алгоритмами полезно **видеть**, как время растёт с $n$, а не только верить формуле. Библиотека Matplotlib рисует графики; документация — на [matplotlib.org](https://matplotlib.org/).\n",
        "\n",
        "Подключаем так:\n",
        "\n",
        "```python\n",
        "import matplotlib.pyplot as plt\n",
        "```\n",
        "\n",
        "Если множество точек $(x, y)$ изображает зависимость $y$ от $x$, точки соединяют линией: `plt.plot(x, y)`. Чтобы Jupyter не печатал служебный объект, в конце вызывают `plt.show()`. Оформление статьи не нужно: нарисовали и пошли.\n"
      ],
      "id": "plot_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import matplotlib.pyplot as plt\n",
        "\n",
        "x = [1, 2, 3, 4, 5]\n",
        "y = [1, 4, 9, 16, 25]\n",
        "plt.plot(x, y)\n",
        "plt.show()\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "plot_demo"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Один замер — это ещё не $\\Theta$. Магия Jupyter `%timeit` много раз запускает маленькую функцию и сообщает типичное время. Для набора точек «время от $n$» удобнее `time.perf_counter`: засекли до и после, записали разность, повторили для нескольких $n$, нарисовали.\n"
      ],
      "id": "timeit_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def square_pass(n):\n",
        "    s = 0\n",
        "    for i in range(n):\n",
        "        for j in range(n):\n",
        "            s += 1\n",
        "    return s\n",
        "\n",
        "\n",
        "%timeit square_pass(200)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "timeit_demo"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import time\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "\n",
        "def square_pass(n):\n",
        "    s = 0\n",
        "    for i in range(n):\n",
        "        for j in range(n):\n",
        "            s += 1\n",
        "    return s\n",
        "\n",
        "\n",
        "ns = [50, 100, 150, 200, 250, 300]\n",
        "times = []\n",
        "for n in ns:\n",
        "    t0 = time.perf_counter()\n",
        "    square_pass(n)\n",
        "    times.append(time.perf_counter() - t0)\n",
        "\n",
        "plt.plot(ns, times)\n",
        "plt.show()\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "perf_plot"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Точки ложатся на параболу: при удвоении $n$ время растёт примерно вчетверо. По одному замеру вывод не делают — нужна **серия** точек. Смотрите на **отношение** времён, а не на «0.01 с — это быстро»: слишком маленькое $n$ тонет в шуме, печать и ввод в замер лучше не включать.\n",
        "\n"
      ],
      "id": "plot_after"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "# Ваш эксперимент: линейная функция и её график рядом с square_pass.\n",
        "# Сравните время при n = 300 и n = 600 — во сколько раз выросло?\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "plot_exp"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## `all`, `any` и итерируемые объекты\n",
        "\n",
        "`all` — это «логическое *и* по всей последовательности»: истинно, только если истинны все элементы. `any` — «логическое *или*»: достаточно одного истинного.\n",
        "\n",
        "Пустой вход у `all` принято считать истинным (ложных элементов нет), у `any` — ложным.\n",
        "\n",
        "Напишите **одну** редукцию своими руками — `my_all`. Вторую (`any`) возьмите стандартную.\n",
        "\n"
      ],
      "id": "all_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def my_all(iterable):\n",
        "    \"\"\"Верните True, если все элементы истинны. Пустой вход — True.\"\"\"\n",
        "    ...\n",
        "\n",
        "\n",
        "print(my_all([True, True, True]))\n",
        "print(my_all([True, False, True]))\n",
        "print(my_all([]))\n",
        "print(my_all(x % 2 == 0 for x in [2, 4, 8]))\n",
        "print(my_all(x % 2 == 0 for x in [2, 3, 8]))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "my_all"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "В Python довольно много объектов, по которым можно пройтись циклом `for`. Строка перебирается по символам — «как монах перебирает чётки». Список — по элементам, `range` — по числам. Такие объекты называются **итерируемыми**.\n",
        "\n",
        "Генератор `x % 2 == 0 for x in a` тоже итерируемый: значения появляются по одному, отдельный список из них собирать не обязательно. Стандартные `all` и `any` как раз принимают любой итерируемый объект.\n"
      ],
      "id": "iter_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "for char in \"ABC\":\n",
        "    print(char)\n",
        "\n",
        "print(any(x < 0 for x in [1, 2, 3]))\n",
        "print(any(x < 0 for x in [1, -2, 3]))\n",
        "print(any([]))\n",
        "print(all([]))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "iter_demo"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Проверку «массив не убывает» удобно записать редукцией по соседним парам:\n",
        "\n",
        "```python\n",
        "all(a[i] <= a[i + 1] for i in range(len(a) - 1))\n",
        "```\n",
        "\n",
        "Пустой массив и массив из одного элемента соседних пар не дают — генератор пуст, `all` возвращает `True`. Не путайте «не убывает» ($a_i \\le a_{i+1}$) со «строго возрастает» ($a_i < a_{i+1}$): знаки `>` и `>=` отвечают на разные вопросы.\n",
        "\n"
      ],
      "id": "issorted_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def is_nondecreasing(a):\n",
        "    return all(a[i] <= a[i + 1] for i in range(len(a) - 1))\n",
        "\n",
        "\n",
        "print(is_nondecreasing([]))\n",
        "print(is_nondecreasing([7]))\n",
        "print(is_nondecreasing([1, 2, 2, 4]))\n",
        "print(is_nondecreasing([1, 3, 2]))\n",
        "print(is_nondecreasing([-5, -1, -1, 3]))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "issorted_ex"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "# Ваш эксперимент: какой знак отвечает на вопрос «не убывает»?\n",
        "# Проверьте [1, 2, 2], [], [7] для <= , < , > , >= и выберите верный.\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "issorted_exp"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Задача 1. Проверка неубывания\n",
        "\n",
        "Дан массив целых чисел. Выведите `YES`, если массив упорядочен по неубыванию, то есть $a_1 \\le a_2 \\le \\ldots \\le a_n$, и `NO` иначе.\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 2\\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \\le 10^9$).\n",
        "\n",
        "**Выход.** Одно слово: `YES` или `NO`.\n",
        "\n",
        "```\n",
        "-> 5\n",
        "-> 1 2 2 4 9\n",
        "--\n",
        "<- YES\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4\n",
        "-> 1 3 2 4\n",
        "--\n",
        "<- NO\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 7 7 7\n",
        "--\n",
        "<- YES\n",
        "```\n",
        "\n",
        "```\n",
        "-> 1\n",
        "-> 0\n",
        "--\n",
        "<- YES\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4\n",
        "-> -5 -1 -1 3\n",
        "--\n",
        "<- YES\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> -1 -3 0\n",
        "--\n",
        "<- NO\n",
        "```\n"
      ],
      "id": "t1_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_tests import test_task1\n",
        "\n",
        "\n",
        "def task1():\n",
        "    n = int(input())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(\"NO\")\n",
        "\n",
        "\n",
        "test_task1(task1)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "t1_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Функция как объект и ключ сортировки\n",
        "\n",
        "В Python **функции — объекты первого класса**. Наравне с числами и строками их можно:\n",
        "\n",
        "1. присваивать переменным,\n",
        "2. класть в списки,\n",
        "3. передавать в другую функцию как параметр,\n",
        "4. возвращать из функции как значение.\n",
        "\n",
        "Имя функции связывается с *объектом функции* так же, как имя переменной — с её значением.\n"
      ],
      "id": "fn_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def foo(x):\n",
        "    return 10 * x\n",
        "\n",
        "\n",
        "bar = foo\n",
        "print(bar(5))\n",
        "\n",
        "\n",
        "def apply_twice(function, x):\n",
        "    return function(function(x))\n",
        "\n",
        "\n",
        "print(apply_twice(foo, 3))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "fn_demo"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Часто имя не нужно: нужен временный объект функции «здесь и сейчас». Тогда пишут `lambda`:\n",
        "\n",
        "```python\n",
        "lambda список_переменных: выражение\n",
        "```\n",
        "\n",
        "И у метода `list.sort`, и у функции `sorted` есть параметр `key`. Это **функция**, которую вызывают для каждого элемента *перед* сравнением. Сортируются сами элементы, а порядок задают ключевые значения.\n",
        "\n",
        "На одинаковых ключах стандартная сортировка CPython **устойчива**: относительный порядок таких элементов не меняется. Это видно на словах одинаковой длины.\n"
      ],
      "id": "lambda_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "s = \"Клара у Карла украла кораллы, Карл у Клары украл кларнет.\"\n",
        "words = s.replace(\",\", \"\").replace(\".\", \"\").split()\n",
        "print(words)\n",
        "words.sort(key=len)\n",
        "print(words)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "key_demo"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Если сортировать пары `(ключ, нагрузка)` как есть, Python сравнивает оба поля: при равном ключе решит нагрузка. Нагрузка сама по себе ключом не является. Чтобы сравнивать **только** ключ, в `key` должна попасть функция, которая из пары достаёт ключ.\n",
        "\n",
        "Безымянная `lambda` как раз удобна как такое «достать поле». Посмотрите, чем отличается сортировка пар целиком от сортировки по одному полю.\n"
      ],
      "id": "pairs_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "pairs = [(1, 9), (2, 0), (1, 3), (2, 1)]\n",
        "print(sorted(pairs))            # сравниваются оба поля\n",
        "print(sorted(pairs, key=len))   # у всех пар длина 2 — порядок не задан ключом\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "pairs_ex"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "# Ваш эксперимент: упорядочите пары только по первому полю.\n",
        "pairs = [(1, 9), (2, 0), (1, 3), (2, 1)]\n",
        "# Допишите вызов sorted(pairs, key=...) и сравните с sorted(pairs).\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "pairs_exp"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## NaN и сломанное сравнение\n",
        "\n",
        "`float('nan')` — нечисло IEEE, не «очень большое» и не «очень маленькое». Любое сравнение с ним ложно: и `nan < x`, и `x < nan`, и `nan < nan`. Это **не** про камень-ножницы-бумагу с лекции: там цикл в правилах игры, здесь сломанное отношение на `float`.\n",
        "\n",
        "`list.sort` опирается на сравнения. Если в массиве есть `nan`, «порядок» после `a.sort()` смотрите глазами: он не обязан совпасть с тем, что вы ждёте от чисел. Запомните картинку — в конце ноутбука есть задача со звёздочкой, где это всплывёт.\n"
      ],
      "id": "nan_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "nan = float(\"nan\")\n",
        "print(nan < 1, 1 < nan, nan < nan, nan == nan)\n",
        "\n",
        "a = [3.0, nan, 1.0, 2.0]\n",
        "print(a)\n",
        "a.sort()\n",
        "print(a)\n",
        "print(all(a[i] <= a[i + 1] for i in range(len(a) - 1)))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "nan_ex"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "# Ваш эксперимент: поставьте nan в начало, в середину и в конец.\n",
        "# Что делает sorted(a) в каждом случае? Похож ли результат на «числа по порядку»?\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "nan_exp"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Квадратичные сортировки\n",
        "\n",
        "На лекции был **Fool**: повторять прогон соседних обменов, пока проверка не скажет «готово». Вложенного `for` может не быть — время в худшем случае всё равно квадрат: отсутствие вложенных циклов не гарантия линейности.\n",
        "\n",
        "Напишите Fool сами. Затем замерьте его на случайном массиве: график должен напоминать параболу, как у `square_pass`.\n"
      ],
      "id": "quad_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import time\n",
        "import random\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "\n",
        "def is_nondecreasing(a):\n",
        "    return all(a[i] <= a[i + 1] for i in range(len(a) - 1))\n",
        "\n",
        "\n",
        "def fool_sort(a):\n",
        "    # Повторяйте прогон / обмен соседей, пока проверка не скажет «готово».\n",
        "    ...\n",
        "    return a\n",
        "\n",
        "\n",
        "print(fool_sort([2, 3, 1]))  # ожидается [1, 2, 3]\n",
        "\n",
        "random.seed(1)\n",
        "ns = [50, 80, 110, 140]\n",
        "times = []\n",
        "for n in ns:\n",
        "    a = [random.randrange(n) for _ in range(n)]\n",
        "    t0 = time.perf_counter()\n",
        "    fool_sort(a)\n",
        "    times.append(time.perf_counter() - t0)\n",
        "\n",
        "plt.plot(ns, times)\n",
        "plt.show()\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "fool_ex"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Если график похож на параболу, при удвоении $n$ время растёт примерно вчетверо. Кода без вложенного `for` достаточно, чтобы вести себя как квадратичный: прогонов тоже порядка $n$.\n",
        "\n"
      ],
      "id": "fool_after"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "# Ваш эксперимент: замерьте Fool на обратно упорядоченном массиве\n",
        "# (list(range(n, 0, -1))) и на «почти порядке». Где быстрее и почему?\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "fool_exp"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**Пузырёк** — тот же прогон, но заранее известно, сколько раз и какую длину ещё смотреть: после $k$ проходов $k$ наибольших уже на своих местах справа (держите один вариант, как на лекции).\n",
        "\n",
        "На почти упорядоченном входе помогает ранний выход: проход без обменов значит «готово». Замерьте случайный массив и массив «почти порядок, одна инверсия»: у пузырька с ранним выходом второе должно быть заметно быстрее.\n"
      ],
      "id": "bubble_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import time\n",
        "import random\n",
        "\n",
        "\n",
        "def bubble_sort(a):\n",
        "    # Прогоны соседних обменов; можно выйти раньше, если проход ничего не менял.\n",
        "    ...\n",
        "    return a\n",
        "\n",
        "\n",
        "print(bubble_sort([4, 3, 2, 1]))  # ожидается [1, 2, 3, 4]\n",
        "\n",
        "n = 400\n",
        "random_a = [random.randrange(n) for _ in range(n)]\n",
        "almost = list(range(n))\n",
        "almost[0], almost[1] = almost[1], almost[0]\n",
        "\n",
        "t0 = time.perf_counter()\n",
        "bubble_sort(random_a)\n",
        "print(\"случайный:\", time.perf_counter() - t0)\n",
        "\n",
        "t0 = time.perf_counter()\n",
        "bubble_sort(almost)\n",
        "print(\"почти порядок:\", time.perf_counter() - t0)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "bubble_ex"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "На почти упорядоченном входе пузырёк с ранним выходом должен быть заметно быстрее, чем на случайном. Если разницы нет, прогон, скорее всего, всегда доходит до конца.\n",
        "\n"
      ],
      "id": "bubble_after"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**Выбор** и **вставки** — по картинкам лекции, не по готовому коду.\n",
        "\n",
        "- Выбор: префикс длины $k$ — $k$ наименьших; каждый шаг минимум хвоста меняется с границей префикса.\n",
        "- Вставки: префикс длины $k$ уже упорядочен; новый элемент въезжает на своё место сдвигами.\n",
        "\n",
        "Оба в худшем случае $\\Theta(n^2)$ сравнений. Вставки обычно дешевле на почти упорядоченном входе. Выбор адаптивным не бывает: он всегда просматривает весь хвост. Доказывать инвариант на паре не нужно: это текст ДЗ к лекции (монетка, LaTeX), сдаёте лектору.\n",
        "\n",
        "Напишите оба и замерьте случайный и почти упорядоченный входы.\n",
        "\n",
        ""
      ],
      "id": "ins_sel_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import time\n",
        "import random\n",
        "\n",
        "\n",
        "def selection_sort(a):\n",
        "    ...\n",
        "    return a\n",
        "\n",
        "\n",
        "def insertion_sort(a):\n",
        "    ...\n",
        "    return a\n",
        "\n",
        "\n",
        "print(selection_sort([3, 1, 2, 3, 0]))  # ожидается [0, 1, 2, 3, 3]\n",
        "print(insertion_sort([3, 1, 2, 3, 0]))  # ожидается [0, 1, 2, 3, 3]\n",
        "\n",
        "n = 400\n",
        "random_a = [random.randrange(n) for _ in range(n)]\n",
        "almost = list(range(n))\n",
        "almost[-1], almost[-2] = almost[-2], almost[-1]\n",
        "\n",
        "for name, fn in [(\"выбор\", selection_sort), (\"вставки\", insertion_sort)]:\n",
        "    t0 = time.perf_counter()\n",
        "    fn(random_a[:])\n",
        "    t_rand = time.perf_counter() - t0\n",
        "    t0 = time.perf_counter()\n",
        "    fn(almost[:])\n",
        "    t_almost = time.perf_counter() - t0\n",
        "    print(name, \"случайный:\", t_rand, \"почти порядок:\", t_almost)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "ins_sel_ex"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "На случайном входе выбор и вставки одного порядка; на почти упорядоченном вставки обычно резко ускоряются, а выбор — нет.\n",
        "\n"
      ],
      "id": "ins_sel_after"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "# Ваш эксперимент: устойчивы ли ваши вставки и выбор?\n",
        "# Возьмите пары [(2, 9), (1, 5), (2, 3), (1, 7)] и упорядочьте их по первому\n",
        "# полю своей функцией. Сохранился ли порядок нагрузок при равных ключах?\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "ins_sel_exp"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Свой цикл на маленьком $n$ успеет. Стандартный `sorted` тесты тоже примут: цель ячейки — потренировать ввод-вывод и один из алгоритмов пары, а не античит.\n",
        "\n",
        "### Задача 2. Сортировка массива\n",
        "\n",
        "Дан массив целых чисел. Выведите его элементы в порядке неубывания.\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 3\\cdot 10^3$). Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \\le 10^9$).\n",
        "\n",
        "**Выход.** Одна строка из $n$ чисел через пробел.\n",
        "\n",
        "```\n",
        "-> 5\n",
        "-> 3 1 2 3 0\n",
        "--\n",
        "<- 0 1 2 3 3\n",
        "```\n",
        "\n",
        "```\n",
        "-> 1\n",
        "-> -10\n",
        "--\n",
        "<- -10\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4\n",
        "-> 4 3 2 1\n",
        "--\n",
        "<- 1 2 3 4\n",
        "```\n"
      ],
      "id": "t2_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_tests import test_task2\n",
        "\n",
        "\n",
        "def task2():\n",
        "    n = int(input())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(*a)\n",
        "\n",
        "\n",
        "test_task2(task2)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "t2_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Устойчивость нужна, когда у равных ключей есть полезная нагрузка: нагрузка не участвует в сравнении, но порядок таких пар должен остаться как во входе. Если сравнить пары целиком, нагрузка вмешается.\n",
        "\n",
        "### Задача 3. Устойчивая сортировка пар\n",
        "\n",
        "Даны $n$ пар целых чисел $(k_i, p_i)$. Упорядочьте пары по неубыванию **только ключа** $k$. Поле $p$ — полезная нагрузка: само по себе оно ключом не является.\n",
        "\n",
        "Если у нескольких пар одинаковый ключ, их относительный порядок должен остаться таким же, как во входе.\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 10^5$). Далее $n$ строк: по два целых $k$ и $p$ ($|k|, |p| \\le 10^9$).\n",
        "\n",
        "**Выход.** $n$ строк `k p` в требуемом порядке.\n",
        "\n",
        "```\n",
        "-> 4\n",
        "-> 3 10\n",
        "-> 1 20\n",
        "-> 2 30\n",
        "-> 4 40\n",
        "--\n",
        "<- 1 20\n",
        "<- 2 30\n",
        "<- 3 10\n",
        "<- 4 40\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4\n",
        "-> 1 5\n",
        "-> 2 8\n",
        "-> 1 3\n",
        "-> 2 1\n",
        "--\n",
        "<- 1 5\n",
        "<- 1 3\n",
        "<- 2 8\n",
        "<- 2 1\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 1 9\n",
        "-> 1 8\n",
        "-> 1 7\n",
        "--\n",
        "<- 1 9\n",
        "<- 1 8\n",
        "<- 1 7\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 5 1\n",
        "-> 4 2\n",
        "-> 3 3\n",
        "--\n",
        "<- 3 3\n",
        "<- 4 2\n",
        "<- 5 1\n",
        "```\n"
      ],
      "id": "t3_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_tests import test_task3\n",
        "\n",
        "\n",
        "def task3():\n",
        "    n = int(input())\n",
        "    for _ in range(n):\n",
        "        k, p = map(int, input().split())\n",
        "        print(k, p)\n",
        "\n",
        "\n",
        "test_task3(task3)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "t3_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Линейные сортировки\n",
        "\n",
        "Если диапазон ключей мал и известен, индекс массива снова может значить *значение*, как частоты на семинаре 2. Сводка «сколько раз встретился ключ $v$» плюс выписывание ключей по возрастанию даёт время $\\Theta(n + U)$, где $U$ — размер диапазона, а не $n^2$.\n",
        "\n",
        "Не путайте $n$ (длина входа) и $U$ (сколько разных ключей возможно). Квадрат по $n$ на задаче 4 получит TLE. Вызывать `sorted` условие не запрещает: на таком $n$ в Python он, скорее всего, тоже успеет.\n"
      ],
      "id": "count_lesson"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Задача 4. Сортировка подсчётом\n",
        "\n",
        "Дан массив целых чисел из диапазона от $0$ до $1000$ включительно. Выведите массив в порядке неубывания.\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 2\\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \\le a_i \\le 1000$).\n",
        "\n",
        "**Выход.** Одна строка из $n$ чисел через пробел.\n",
        "\n",
        "```\n",
        "-> 6\n",
        "-> 3 1 3 2 1 3\n",
        "--\n",
        "<- 1 1 2 3 3 3\n",
        "```\n",
        "\n",
        "```\n",
        "-> 5\n",
        "-> 7 7 7 7 7\n",
        "--\n",
        "<- 7 7 7 7 7\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4\n",
        "-> 1000 0 1000 0\n",
        "--\n",
        "<- 0 0 1000 1000\n",
        "```\n"
      ],
      "id": "t4_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_tests import test_task4\n",
        "\n",
        "\n",
        "def task4():\n",
        "    n = int(input())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(*a)\n",
        "\n",
        "\n",
        "test_task4(task4)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "t4_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**LSD.** Если числа одной разрядности, их можно сортировать устойчивыми проходами с *младшего* разряда: каждый проход — устойчивый подсчёт по одной цифре. После $k$ проходов порядок правильный по $k$ младшим разрядам.\n",
        "\n",
        "Готовый цикл с лекции (карточки и палочка) сюда не копируйте: напишите короткий проход сами. Двоичный пример на три-четыре бита или десятичные цифры — как удобнее. Если времени мало, оставьте упражнение и не открывайте задачу 5.\n"
      ],
      "id": "lsd_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def digit(x, power10):\n",
        "    \"\"\"Цифра числа x на разряде 10 ** power10 (0 — единицы).\"\"\"\n",
        "    return (x // (10 ** power10)) % 10\n",
        "\n",
        "\n",
        "def lsd_sort(a, d):\n",
        "    # d устойчивых проходов, начиная с младшего разряда.\n",
        "    ...\n",
        "    return a\n",
        "\n",
        "\n",
        "print(lsd_sort([15, 7, 100, 3], 3))     # ожидается [3, 7, 15, 100]\n",
        "print(lsd_sort([10, 10, 1, 0, 99], 2))  # ожидается [0, 1, 10, 10, 99]\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "lsd_ex"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Если осталось время\n",
        "\n",
        "Задача 5 не обязательна. Если 1–4 уже зелёные — можно закрыть и её. Квадрат по $n$ на больших тестах не успеет.\n"
      ],
      "id": "spare"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Задача 5. Сортировка чисел фиксированной разрядности\n",
        "\n",
        "Даны $n$ неотрицательных целых чисел. Каждое из них меньше $10^d$, то есть записывается не более чем $d$ десятичными цифрами (ведущие нули не печатать). Выведите числа в порядке неубывания.\n",
        "\n",
        "**Вход.** Первая строка: $n$ и $d$ ($1 \\le n \\le 10^5$, $1 \\le d \\le 6$). Вторая строка: $n$ целых чисел $a_i$ ($0 \\le a_i < 10^d$).\n",
        "\n",
        "**Выход.** Одна строка из $n$ чисел через пробел.\n",
        "\n",
        "```\n",
        "-> 4 3\n",
        "-> 15 7 100 3\n",
        "--\n",
        "<- 3 7 15 100\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3 1\n",
        "-> 9 0 5\n",
        "--\n",
        "<- 0 5 9\n",
        "```\n",
        "\n",
        "```\n",
        "-> 5 2\n",
        "-> 10 10 1 0 99\n",
        "--\n",
        "<- 0 1 10 10 99\n",
        "```\n"
      ],
      "id": "t5_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_tests import test_task5\n",
        "\n",
        "\n",
        "def task5():\n",
        "    n, d = map(int, input().split())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(*a)\n",
        "\n",
        "\n",
        "test_task5(task5)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "t5_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Когда выигрывает подсчёт\n",
        "\n",
        "`sort` / `sorted` в CPython — Timsort, примерно $n\\log n$ сравнений и очень хорошо написан. Подсчёт выигрывает, когда диапазон $U$ мал, а $n$ велико: нет сравнений ключей, только проходы по входу и по $U$. Плата — дополнительная память $\\Theta(U)$ под массив частот.\n",
        "\n",
        "Если $U$ огромный (ключи до $10^9$), массив частот не построите. Если $n$ маленькое, разница часто не видна за шумом замера. Снимите `sorted` и свой подсчёт на одном и том же большом массиве из диапазона $0..1000$.\n",
        "\n"
      ],
      "id": "compare_lesson"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import time\n",
        "import random\n",
        "\n",
        "\n",
        "def counting_sort(a, u=1000):\n",
        "    ...\n",
        "    return a\n",
        "\n",
        "\n",
        "n = 20000\n",
        "a = [random.randrange(1001) for _ in range(n)]\n",
        "\n",
        "t0 = time.perf_counter()\n",
        "sorted(a)\n",
        "print(\"sorted:\", time.perf_counter() - t0)\n",
        "\n",
        "t0 = time.perf_counter()\n",
        "counting_sort(a[:])\n",
        "print(\"подсчёт:\", time.perf_counter() - t0)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "compare_ex"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "# Ваш эксперимент: прикиньте число операций для n = 200000, U = 1000\n",
        "# и для того же n, но с ключами до 10**9 (массив частот такого размера\n",
        "# не построить). Что выгоднее в каждом случае?\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "compare_exp"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## \\* Задача 6. Гномья сортировка\n",
        "\n",
        "Не требуется для зачёта пары. На паре эталон не разбираем. Кто закрыл 1–4 и хочет звёздочку — в конце ноутбука.\n",
        "\n",
        "Рассмотрим такой процесс над массивом. Стоим в начале (индекс $0$). Пока индекс меньше длины массива:\n",
        "\n",
        "- если индекс равен $0$ или текущий элемент **не строго меньше** предыдущего — шаг вперёд;\n",
        "- иначе меняем текущий элемент с предыдущим местами и делаем шаг назад.\n",
        "\n",
        "Примените этот процесс к данному массиву и выведите массив после него.\n",
        "\n",
        "Во входе могут встречаться значения `nan` (нечисло IEEE). Проверяется **точная** последовательность токенов, а не «любой разумный порядок».\n",
        "\n",
        "Обычные `sorted` и `list.sort`, скорее всего, не совпадут с эталоном на тестах с `nan`. Можно попробовать обхитрить тест: вызвать стандартную сортировку и расставить `nan` так, чтобы ответ совпал с описанным процессом.\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 3\\cdot 10^3$). Вторая строка: $n$ токенов — целые числа или слово `nan` (в нижнем регистре). Модуль каждого конечного числа не превосходит $10^9$.\n",
        "\n",
        "**Выход.** Одна строка из $n$ токенов через пробел: те же целые и `nan`.\n",
        "\n",
        "```\n",
        "-> 5\n",
        "-> 3 1 2 3 0\n",
        "--\n",
        "<- 0 1 2 3 3\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4\n",
        "-> 2 0 nan 1\n",
        "--\n",
        "<- 0 2 nan 1\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 7 7 7\n",
        "--\n",
        "<- 7 7 7\n",
        "```\n",
        "\n",
        "```\n",
        "-> 1\n",
        "-> nan\n",
        "--\n",
        "<- nan\n",
        "```\n"
      ],
      "id": "t6_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_tests import test_task6\n",
        "\n",
        "\n",
        "def task6():\n",
        "    n = int(input())\n",
        "    a = input().split()\n",
        "    print(*a)\n",
        "\n",
        "\n",
        "test_task6(task6)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "t6_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Шпаргалка\n",
        "\n",
        "- **Инвариант** — утверждение, верное на границе итерации. Картинки — на лекции; доказательство вставок или выбора — в LaTeX-ДЗ лектору.\n",
        "- **Устойчивость** — при равных ключах относительный порядок входа сохраняется.\n",
        "- **Ключ** — то, по чему сравнивают; нагрузка в сравнение не входит.\n",
        "- Сложности в худшем случае: Fool, пузырёк, вставки, выбор — $\\Theta(n^2)$; подсчёт — $\\Theta(n + U)$; LSD — $\\Theta(d(n + 10))$; `sorted` — примерно $n\\log n$.\n",
        "- `all([])` истинно, `any([])` ложно.\n",
        "- `nan` ни с кем не меньше и не больше; проверка `<=` с ним ложна.\n",
        "- $n$ — длина входа, $U$ — размер диапазона ключей. Это разные величины.\n",
        "\n",
        "Типичные сбои на паре: знак сравнения; `nan` в проверке порядка; квадрат там, где нужен линейный проход; пары сравнили целиком, и нагрузка вмешалась.\n",
        "\n",
        ""
      ],
      "id": "cheatsheet"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Сдача\n",
        "\n",
        "Перед отправкой проверьте:\n",
        "\n",
        "- сохранили ноутбук: `File → Save`;\n",
        "- рядом с ноутбуком лежит `lab03_tests.py`;\n",
        "- в ячейке решения есть `from lab03_tests import test_taskN` (после перезапуска ядра выполните эту ячейку снова);\n",
        "- отправили **этот** файл `.ipynb` семинаристу в личные сообщения до дедлайна.\n",
        "\n",
        "В LMS заданий семинара 3 ещё нет. ДЗ к лекции — https://learn.ai.msu.ru/algo/1/03/hw-lecture/ — сдаёте **лектору**, не семинаристу: `.tex` и PDF, не этот ноутбук.\n",
        "\n",
        "Недорешенные задачи не мешают отправке: сдайте то, что успели. Красный тест у заглушки — нормально. TLE значит «слишком медленно», обычно квадрат там, где нужен линейный проход. Задача 5 не обязательна. Задача 6\\* для зачёта пары не нужна.\n",
        ""
      ],
      "id": "submit"
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "pygments_lexer": "ipython3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}