{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Содержание\n", "\n", "1. [Оценка скорости алгоритмов](#measure)\n", " 1. [Как оценить скорость работы алгоритма](#how_to_measure)\n", " 2. [Какие есть интрументы для измерения](#measurement_frameworks)\n", "2. [Разделяй и властвуй](#divide_and_conquer)\n", " 1. [Идея](#dnq_idea)\n", "3. [Mergesort](#mergesort)\n", " 1. [Краткое описание](#mergesort_description)\n", " 2. [Merge](#merge)\n", " 3. [Сложность, плюсы, минусы, стабильность](#mergesort_properties)\n", " 4. [Варианты](#mergesort_variants)\n", "4. [Quicksort](#quicksort)\n", " 1. [Идея](#quciksort_idea)\n", " 2. [Особенности алгоритма](#quicksort_features)\n", " 3. [Псевдокод](#quicksort_code)\n", " 4. [Errata](#errata)\n", "5. [Timsort](#timsort)\n", " 1. [История](#history)\n", " 2. [Алгоритм](#timsort_algorithm)\n", "6. [Домашняя работа](#homework)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Оценка скорости алгоритмов\n", "\n", "\n", "## Как оценить скорость работы алгоритма\n", "\n", "\n", "- Если необходимо сделать оценку скорости, то нужно делать замеры для большого количества значений (размера входных данных). Чем больше точек - тем точнее данные\n", " - можно брать значения по линейно\n", " - можно брать по логарифмической шкале\n", " - иногда итмеет смысл брать значения чуть ли не непрерывно, потому что в таком случае можно посмотреть на динамику, когда происходит выделение памяти etc\n", "- Также стоит делать $ n $ замеров, чтобы получать усреденные значения\n", "- Просто замерять время между выполнением команд может быть недостаточно точно - т.к. в процесс мог влезть другой процесс и так далее. Нужно мерять cpu time\n", "\n", "\n", "## Какие есть интрументы для измерения\n", "\n", "\n", "- Python\n", " - если вы используете ipython, есть magic %%time и %%timeit\n", " - есть библиотека [profile](https://docs.python.org/3/library/profile.html)\n", "\n", "- C++\n", " - функции из chrono :)\n", " - vallgrind's [callgrind](http://valgrind.org/docs/manual/cl-manual.html)\n", " - [gperftools](https://github.com/gperftools/gperftools) \n", "\n", "- Java\n", " - [ссылка](http://java-source.net/open-source/profilers) - список профайлеров\n", " \n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Разделяй и властвуй\n", "\n", "\n", "## Идея\n", "\n", "\n", "\n", " \n", "- Разбить большую задачу на такие же, но меньшие по размеру, и так далее\n", "- Решить задачу, когда размер станет мал\n", "- Объединить результаты\n", "\n", "\n", "Работа mergesort\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Mergesort\n", "\n", "\n", "\n", "## Краткое описание\n", "\n", "- Нужен механизм разделения\n", "- Алгоритм для сортировки минимальной подзадачи\n", "- Алгоритм объединения (merge)\n", "\n", "\n", "Будем делить массивы ~пополам, учитывая, что один их размер может быть нечетным\n", "\n", "> Сколько всего будет разбиений?\n", "\n", "Сам алгоритм:\n", "\n", "
\n",
    "1  MergeSort(Array, end):\n",
    "2      Copy = CopyArray(Array)\n",
    "3      SplitMerge(Copy, 0, n, Array)\n",
    "4  \n",
    "5 \n",
    "6  SplitMerge(Copy, begin, end, Array):\n",
    "7      if end - begin < 2\n",
    "8         return\n",
    "9      middle = (end + begin) // 2\n",
    "10     SplitMerge(Array, begin, middle, Copy)\n",
    "11     SplitMerge(Array, middle, end, Copy)\n",
    "12     Merge(Copy, begin, middle, end, Array)\n",
    "
\n", "\n", "\\- постоянно меняются местами `Array` и `Copy` - данные копируются из одного в другой\n", "\n", "Функция `Merge` - время работы $ O(n) $ \n", "\n", "\n", "\n", "[в начало](#index)\n", "\n", "### Достаем двойные листочки!\n", "Давайте напишем `Merge` (и весь алгоритм), определение `MergeSort` выглядит довольно простым.\n", "\n", "- Идея: есть два массива одинакового рамера, второй разбит на две части\n", "- Переносим элементы в первый массив из второго либо из первой, либо из второй части\n", "\n", "\n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "[[1, 1, 1, 1], [2, 3, 4, 5]]\n", "[1, 1, 1, 1, 2, 3, 4, 5]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "[[\"2\",3,4,5], [1,1,1,\"1\"]]\n", "[1,1,1,1,2,3,4,5]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Merge\n", "\n", "\n", "
\n",
    "1  Merge(Array, begin, middle, end, Copy):\n",
    "2      fst, snd = begin, middle\n",
    "3      for ptr in range(begin, end)\n",
    "4          if fst < middle and (snd >= end or Array[fst] <= Array[snd])\n",
    "5              Copy[ptr] = Array[fst]\n",
    "6              fst += 1\n",
    "7          else\n",
    "8              Copy[ptr] = Array[snd]\n",
    "9              snd += 1\n",
    "\n",
    "
\n", "\n", "## Сложность, плюсы, минусы, стабильность\n", "\n", "\n", "Если посмотреть еще раз на это изображение:\n", "
\n", "\n", " \n", "\\- становится интуитивно понятно, какая у алгоритма сложноcть. \n", "- $ O(n) $ - на `Merge` на каждом \"уровне\"\n", "- $ O(log(n)) $ уровней \n", "\n", "\\- получается $ O(n \\cdot log(n)) $ сортировка\n", "\n", "\n", "### Плюсы сортировки\n", "\n", "\n", "- Гарантированная скорость $ O(n \\cdot log(n)) $ \n", "- Стабильность\n", "- Возможность параллелизации\n", "- Модификации используются для внешней сортировки\n", "- Подходит хорошо для списков (см. далее)\n", "\n", " \n", "### Минусы\n", "\n", "\n", "\n", "- $ O(n) $ памяти - без оптимизаций\n", "- Немного медленнее Quicksort\n", "\n", "\n", "\n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Варианты\n", "\n", "\n", "\n", "Как можно усовершенствовать Mergesort (много как, на самом деле)\n", "\n", "#### Сделать параллельным\n", "\n", "
\n",
    "1  SplitMerge(Copy, begin, end, Array):\n",
    "2      if end - begin < 2\n",
    "3         return\n",
    "4      middle = (end + begin) // 2\n",
    "5      fork SplitMerge(Array, begin, middle, Copy)\n",
    "6      join\n",
    "7      SplitMerge(Array, middle, end, Copy)\n",
    "8      Merge(Copy, begin, middle, end, Array)\n",
    "
\n", "\n", "#### Fork-join model\n", "\n", "Это [стандартный подход](https://en.wikipedia.org/wiki/Fork%E2%80%93join_model), исользующийся для алгоритмов \"Divide-and-Conquer\". На этот каркас можно \"натянуть\" и другие алгоритмы\n", "\n", "
\n",
    "1  Solve(problem):\n",
    "2      if problem is small enough:\n",
    "3          solve problem directly (sequential algorithm)\n",
    "4      else:\n",
    "5          for part in Subdivide(problem)\n",
    "6              fork subtask to Solve(part)\n",
    "7          join all subtasks spawned in previous loop\n",
    "8          return combined results\n",
    "
\n", "\n", "\n", "### Другие идеи\n", "\n", "
\n", "\n", "- Использовать имеющиеся в данных убывающие / возрастающие посоледовательности (и не сортировать их)\n", "- Можно превратить в блочную сортировку\n", "- В модификации хорошо работает со списками - когда доступ по индексу закрыт. При этом можно обойтись без доп. памяти/\n", "\n", "\n", "[в начало](#index)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Quicksort \n", "\n", "\n", "\n", "## Идея\n", "\n", "\n", "\n", "- Выбрать стержневой элемент\n", "- Разбить массивы так, чтобы \"слева\" от стержневого были элементы $ \\leq $, \"справа\" - большие\n", "- Повторять для \"правой\" и \"левой\" половин, пока длина массива > 1\n", "\n", "\n", "## Особенности алгоритма\n", "\n", "\n", "\n", "\n", "### Фичи и плюсы\n", "- Алгоритм придумал [Хоар](https://ru.wikipedia.org/wiki/%D0%A5%D0%BE%D0%B0%D1%80,_%D0%A7%D0%B0%D1%80%D0%BB%D1%8C%D0%B7_%D0%AD%D0%BD%D1%82%D0%BE%D0%BD%D0%B8_%D0%A0%D0%B8%D1%87%D0%B0%D1%80%D0%B4) для быстрой сортировки словарей (1959)\n", "- Алгоритм обладает средним временем работы $ O(n \\cdot log(n)) $, но _наихудшим_ $ O(n^2) $ \n", "- При этом у него хорошие константы\n", "- Не нужно дополнительно выделять память\n", "- Можно распараллелить\n", "\n", "### Недостатки\n", "- нестабилен\n", "- не гарантированно быстр (может \"тормозить\")\n", "- нестабилен\n", "\n", "\n", "## Псевдокод\n", "\n", "\n", "\n", "
\n",
    "1  Quicksort(Array, begin, end):\n",
    "2      if begin < end:\n",
    "3          pivot = Partition(Array, begin, end)\n",
    "4          Quicksort(Array, begin, pivot)\n",
    "5          Quicksort(Array, pivot+1, end)\n",
    "\n",
    "
\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Процедура Partition\n", "\n", "
\n", "\n", "Итак, есть сигнатура: `Partition(Array, begin, end) -> pivot`\n", " \n", "> Что эта функция должна делать? \n", "> И как ее реализовать (как минимум один способ)?\n", "\n", "\n", "\n", " \n", " На семинаре демонстрировалось неправильное изображение! Здесь приведен исправленный вариант.\n", "
\n", "
\n", "\n", "\n", "\n", " \n", "\n", " \n", "- Использовалось 1-индексирование, сказано про это не было - теперь псевдокод исправлен на 0-индексирование\n", "- Была показана работа `Partition` для создания убывающих массивов (вместо возрастающих, как в коде)\n", "- Если $j$-й элемент меньше либо равен стержневого, то меняются местами $i$+1 и $j$-й элементы, а $ i += 1 $\n", "- Менябщиеся элементы выделены градиентом\n", "- Теперь изображение соответствует коду, приведенному ниже\n", " \n", "\n", " \n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Псевдокод Partition\n", "
\n", "Это один из вариантов. Мы можем реализовать рандомизированный вариант или схему Хоара.\n", "\n", "- Процесс происходит _inplace_\n", "- Процесс _не_ гарантирует стабильности\n", "\n", "\n", "Код:\n", "
\n",
    "1  Partition(Array, begin, end):\n",
    "2      pivot = Array[end-1]  // например, мы можем взять элемент из конца\n",
    "3      i = begin - 1  // да, он может быть < 0, это ОК\n",
    "4      for j = begin to end-2  // имеется в виду \"по элемент end-2 включительно\"\n",
    "5          if Array[j] ≤ pivot\n",
    "6              i += 1\n",
    "7              swap(Array, j, i)\n",
    "8      swap(Array, i+1, end-1)  // ставим стержневой элемент на место\n",
    "9      return i + 1\n",
    "
\n", "\n", "\n", "\n", " Список исправлений в псевдокоде:\n", "\n", "- Используется `Array[end-1]` вместо `Array[end]`\n", "- Используется `swap(Array, i+1, end-1)` вместо `swap(Array, i+1, end)`\n", "- Используется `for j = begin to end-2` вместо `for j = begin to end-1`\n", "- Используется `Quicksort(Array, begin, pivot)` вместо `Quicksort(Array, begin, pivot-1)`\n", "- Последнее верно для `Quicksort` и `TailQuicksort` (см. ниже)\n", "\n", "\n", "\n", "[В начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Здесь приведен код, который соответсвует иллюстрации с вебинара, и сама иллюстрация.

\n", "\n", "\n", "Оператор `≤` заменен на `≥`, располагающий меньший и больший массивы соответсвенно справа и слева и \"сортирующий\" в обратном порядке. \n", "\n", "\n", "\n", "
\n",
    "1  Partition(Array, begin, end):\n",
    "2      pivot = Array[end-1]  // например, мы можем взять элемент из конца\n",
    "3      i = begin - 1  // да, он может быть < 0, это ОК\n",
    "4      for j = begin to end-2  // имеется в виду \"по элемент end-2 включительно\"\n",
    "5          if Array[j] ≥ pivot\n",
    "6              i += 1 \n",
    "7              swap(Array, j, i)\n",
    "8      swap(Array, i+1, end-1)  // ставим стержневой элемент на место\n",
    "9      return i + 1\n",
    "
\n", "\n", "\n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Код на python (с минимальными отличиями от псевдокода)\n", "\n", "Код показывет разницу между decreasing и increasing partition" ] }, { "cell_type": "code", "execution_count": 241, "metadata": {}, "outputs": [], "source": [ "def quicksrot(array, begin, end, partition):\n", " if begin < end:\n", " pivot = partition(array, begin, end)\n", " quicksrot(array, begin, pivot, partition)\n", " quicksrot(array, pivot+1, end, partition)\n", " \n", "\n", "def partition_increasing(array, begin, end):\n", " pivot = array[end-1]\n", " i = begin - 1\n", " for j in range(begin, end-1):\n", " if array[j] <= pivot:\n", " i += 1\n", " swap(array, i, j)\n", " swap(array, i+1, end-1)\n", " return i + 1\n", "\n", "\n", "def partition_decreasing(array, begin, end):\n", " pivot = array[end-1]\n", " i = begin - 1\n", " for j in range(begin, end-1):\n", " if array[j] >= pivot:\n", " i += 1\n", " swap(array, i, j)\n", " swap(array, i+1, end-1)\n", " return i + 1\n", "\n", "\n", "def swap(array, i, j):\n", " buff = array[i]\n", " array[i] = array[j]\n", " array[j] = buff" ] }, { "cell_type": "code", "execution_count": 227, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]" ] }, "execution_count": 227, "metadata": {}, "output_type": "execute_result" } ], "source": [ "arr = list(range(10))\n", "partition_increasing(arr, 0, 10)\n", "arr" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Сортировка в убывающем порядке" ] }, { "cell_type": "code", "execution_count": 228, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]" ] }, "execution_count": 228, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quicksrot(arr, 0, 10, partition_decreasing)\n", "arr" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Сортировка в возрастающем порядке" ] }, { "cell_type": "code", "execution_count": 229, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]" ] }, "execution_count": 229, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quicksrot(arr, 0, 10, partition_increasing)\n", "arr" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Несколько примеров" ] }, { "cell_type": "code", "execution_count": 230, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "unsorted: [10, 18, 2, 17, 0, 1, 19, 13, 15, 5, 12, 16, 14, 3, 9, 7, 11, 6, 4, 8]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [12, 2, 17, 8, 19, 10, 0, 1, 6, 9, 3, 4, 16, 13, 11, 14, 5, 15, 7, 18]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [19, 7, 13, 8, 12, 0, 14, 1, 10, 16, 11, 4, 3, 6, 2, 17, 15, 18, 5, 9]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [4, 8, 0, 12, 1, 10, 7, 2, 11, 17, 3, 5, 19, 9, 14, 13, 16, 6, 15, 18]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [19, 5, 18, 4, 3, 12, 10, 17, 13, 14, 11, 2, 1, 6, 0, 9, 7, 15, 16, 8]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [19, 2, 0, 12, 4, 11, 10, 8, 6, 14, 7, 9, 1, 3, 15, 16, 17, 13, 18, 5]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [7, 13, 17, 18, 16, 10, 0, 8, 19, 3, 14, 15, 12, 6, 4, 9, 11, 5, 1, 2]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [6, 2, 0, 13, 17, 12, 19, 4, 3, 8, 7, 1, 11, 15, 14, 18, 10, 9, 5, 16]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [15, 9, 2, 13, 12, 16, 10, 1, 8, 11, 4, 7, 19, 18, 6, 5, 17, 14, 3, 0]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n", "unsorted: [7, 1, 13, 15, 11, 6, 3, 18, 19, 8, 17, 5, 0, 9, 14, 4, 12, 10, 2, 16]\n", "decreasing: [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n", "increasing: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]\n", "--------------------------\n" ] } ], "source": [ "def test(array, partition):\n", " quicksrot(array, 0, len(arr), partition)\n", " assert len(array) > 2\n", " for i, j in zip(array[:-1], array[1:]):\n", " assert i <= j if partition is partition_increasing else i >= j\n", "\n", " \n", "for i in range(10):\n", " arr = list(range(20))\n", " np.random.shuffle(arr)\n", " cpy = [i for i in arr]\n", " print(\"unsorted: {}\".format(arr))\n", " test(arr, partition_decreasing)\n", " test(cpy, partition_increasing)\n", " print(\"decreasing: {}\".format(arr))\n", " print(\"increasing: {}\".format(cpy))\n", " print(\"--------------------------\")" ] }, { "cell_type": "code", "execution_count": 248, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[-4, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 56]" ] }, "execution_count": 248, "metadata": {}, "output_type": "execute_result" } ], "source": [ "arr = [1, 1, 1, 1, -4, 5, 5, 5, 5, 56, 5, 5, 5, 5]\n", "cpy = [i for i in arr]\n", "quicksrot(arr, 0, len(arr), partition_increasing)\n", "arr" ] }, { "cell_type": "code", "execution_count": 249, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[56, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, -4]" ] }, "execution_count": 249, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quicksrot(cpy, 0, len(arr), partition_decreasing)\n", "cpy" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Варианты\n", "\n", "\n", "### Randomized\n", "
\n", "Если массив организован так, что pivot всегда неудачный - можно обойтись при помощи внесеня рандомизации\n", "\n", "Немного вопросов:\n", "\n", "> Как сделать рандомизацию? \n", "> Сколько раз будет генерироваться случайное число? \n", "> Какова примерная оценка вероятности того, что _всегда_ будет выбираться наихудший случай?\n", "\n", "\n", "\n", "### Hoare Partition\n", "
\n", "Оригинальная схема упорядочения значений, предложенная Хоаром. \n", "Без псевдокода - но его легко найти
\n", " \n", "\n", "\n", "wiki/Quicksort - Hoare partition scheme\n", "\n", "\n", "\n", "### Хвостовая рекурсия\n", "
\n", " \n", "
\n",
    "1  TailQuicksort(Array, begin, end):\n",
    "2      while begin < end:\n",
    "3          pivot = Partition(Array, begin, end)\n",
    "4          TailQuicksort(Array, begin, pivot)\n",
    "5          begin = pivot + 1\n",
    "\n",
    "
\n", "\n", "> Какова будет глубина стека при использовании такого алгоритма?\n", "\n", "\n", "\n", "[В начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Timsort\n", "\n", "## История\n", "\n", "\n", "
\n", "\n", "- Алгоритм изобрел Тим Питерс в 2002 г. для использования в языке Python\n", "- Алгоритм является улучшением merge sort\n", "- [ссылка](https://hg.python.org/cpython/file/f2353e74b335/Objects/listobject.c#l980)\n", "\n", "
\n",
    "/* Lots of code for an adaptive, stable, natural mergesort.  There are many\n",
    " * pieces to this algorithm; read listsort.txt for overviews and details.\n",
    " */\n",
    "
\n", "\\- здесь его даже Timsort не зовут\n", "\n", "\n", "\n", "## Особенности алгоритма\n", "\n", "
\n", "\n", "- Это merge sort на стероидах\n", "- Алгоритм использует неубывающие и невозрастающие последовательности в данных (последние он разворачивает), которые называются run. Ссылки на run'ы отправляются в стек\n", "- Для сортировки маленьких подпоследовательностей < _minrun_ используется insertion sort\n", "- _minrun_ выбирается от 32 до 64 - из соображений, что лучше всего разбивать на части, близкие к степеням двойки \n", "- алгоритм адаптивный, стабильный\n", "- _run'ы_ сливаются по очереди и по ссылкам, что позволяет не выделять большое количество памяти - \n", "\n", "\n", "\n", "\n", "$$\n", "|Z| > |Y| + |X|\n", "$$\n", "$$\n", "|Y| > |X|\n", "$$\n", "$$\n", "\\rightarrow X, Y \\ merged\n", "$$\n", "$$\n", "else\\ \n", "Y,\\ smallest(Z, X) merged\n", "$$\n", "\n", "\n", "### Ссылки\n", "\n", "Ссылки на статьи про Timsort на [hackernoon](https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399) и [dev.to](https://dev.to/s_awdesh/timsort-fastest-sorting-algorithm-for-real-world-problems--2jhd) \n", "\n", "\n", "[в начало](#index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Домашняя работа\n", "\n", " \n", "\n", " \n", "Реализовать:\n", "\n", "MergeSort или QuickSort (рандомизированный и обычный)\n", "- алгоритм работает корректно, используется insertion sort: 3 балла\n", "- алгоритм работает корректно, но выполняет много лишних действий / отклоняется от реализации не в лучшую сторону - 2 балл\n", "\n", "Дополнительно:\n", "- quicksort - сравнить рандомизированный и обычный варианты - 1 балл\n", "- mergsesort - добавить обработку run'ов - 1 балл\n", "\n", "- распараллелить алгоритм - 1 балл (если считаете, что этот материал надо разобрать отдельно - напишите в слак) - 1 балл\n", "\n", "- делать оба алгоритма не обязательно, но при желании можно, баллы ставятся за лучший :\n", " \n", "\n", "\n", "[в начало](#index)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "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.6.7" } }, "nbformat": 4, "nbformat_minor": 2 }