{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Алгоритмы сортировки"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Материалы для изучения\n",
    "[Алгоритмы сортировки на Python](https://pythonist.ru/algoritmy-sortirovki-na-python)  \n",
    "[Объяснение алгоритмов сортировки с примерами на Python](https://tproger.ru/translations/sorting-algorithms-in-python/)  \n",
    "[Топ-5 алгоритмов сортировки на Python](https://pythonru.com/osnovy/top-5-algoritmov-sortirovki-na-python)  \n",
    "Иллюстрации к алгоритмам взяты из статьи [Сортировки в гифках: 8 самых популярных алгоритмов](https://proglib.io/p/sort-gif/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Подготовительная работа\n",
    "Создадим несколько списков, на которых будем проверять работоспособность алгоритмов и время их работы\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7, 4, 10, 7, 0, 3, 7, 6, 5, 20, 20, 7, 13, 1, 15]\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "import random\n",
    "import math\n",
    "\n",
    "n1 = 15\n",
    "n2 = 5*10**3\n",
    "a1 = [random.randint(0, 20) for i in range(n1)]\n",
    "a2 = [random.randint(-1000, 1000) for i in range(n2)]\n",
    "# a2 = [0.00001*i+math.sin(i) for i in range(n2)]\n",
    "print(a1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Метод пузырька (Bubble sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "При проходе по списку попарно сравниваются два соседних элемента. Если они находятся в верном порядке, то ничего не происходит, в противном случае они меняются местами. В результате первого прохода максимальный элемент окажется в конце, то есть всплывет словно пузырек.   \n",
    "Затем все повторяется до того момента пока весь массив не будет отсортирован."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://media.proglib.io/wp-uploads/-000//1/596b722779f8b_Yb6G53y.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n"
     ]
    }
   ],
   "source": [
    "# базовый вариант\n",
    "def bubble_sort1(a):\n",
    "    n = len(a)\n",
    "    for i in range(n-1, 0, -1):\n",
    "        for j in range(i):\n",
    "            if a[j]>a[j+1]:\n",
    "                a[j], a[j+1] = a[j+1], a[j]\n",
    "# тестирование\n",
    "b = a1.copy()\n",
    "bubble_sort1(b)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n"
     ]
    }
   ],
   "source": [
    "# улучшенный вариант\n",
    "def bubble_sort2(a):\n",
    "    n = len(a)\n",
    "    for i in range(n-1, 0, -1):\n",
    "        finish = True\n",
    "        for j in range(i):\n",
    "            if a[j]>a[j+1]:\n",
    "                a[j], a[j+1] = a[j+1], a[j]\n",
    "                finish = False\n",
    "        if finish:\n",
    "            return\n",
    "\n",
    "\n",
    "# тестирование\n",
    "b = a1.copy()\n",
    "bubble_sort1(b)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "время сортировки - 5.7500 сек.\n",
      "время сортировки - 3.5200 сек.\n"
     ]
    }
   ],
   "source": [
    "# сравнение времени работы\n",
    "b = a2.copy()\n",
    "c = a2.copy()\n",
    "\n",
    "t = time.time()\n",
    "bubble_sort1(b)\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')\n",
    "\n",
    "t = time.time()\n",
    "bubble_sort2(c)\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')\n",
    "\n",
    "# а как увидеть преимущества улучшенного варианта?\n",
    "# закомментировать первые две строчки"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Сортировка выбором (Selection sort)\n",
    "\n",
    "Идея метода: в списке находим минимальный элемент и помещаем его на первое место (меняем местами первый и минимальный). Затем находим минимальный элемент из оставшихся и ставим его на второе место. Процесс повторяется, пока список не станет упорядоченным."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://media.proglib.io/wp-uploads/-000//1/596b722fd2a7d_djIHfUK.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n",
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n"
     ]
    }
   ],
   "source": [
    "# базовый вариант\n",
    "def selection_sort1(a):\n",
    "    n = len(a)\n",
    "    for i in range(n-1):\n",
    "        min1 = a[i]\n",
    "        k = i\n",
    "        for j in range(i+1, n):\n",
    "            if a[j]<min1:\n",
    "                min1 = a[j]\n",
    "                k = j\n",
    "        a[i], a[k] = a[k], a[i]        \n",
    "\n",
    "# улучшенный? вариант\n",
    "# без внутреннего цикла\n",
    "def selection_sort2(a):\n",
    "    n = len(a)\n",
    "    for i in range(n-1):\n",
    "        min1 = min(a[i:])\n",
    "        k = a.index(min1, i)\n",
    "        a[i], a[k] = a[k], a[i]\n",
    "        \n",
    "# тестирование\n",
    "b = a1.copy()\n",
    "selection_sort1(b)\n",
    "print(b)\n",
    "\n",
    "b = a1.copy()\n",
    "selection_sort2(b)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "help(list.insert)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "время сортировки - 2.0200 сек.\n",
      "время сортировки - 0.9000 сек.\n"
     ]
    }
   ],
   "source": [
    "# сравнение времени работы\n",
    "b = a2.copy()\n",
    "c = a2.copy()\n",
    "\n",
    "t = time.time()\n",
    "selection_sort1(b)\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')\n",
    "\n",
    "t = time.time()\n",
    "selection_sort2(c)\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Сортировка вставками"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Предполагаем, что список состоит из двух частей: отсортированной и неотсортированной. Перебираем по очереди элементы из неотсортированной части и **вставляем** их в нужную позцию отсортированной части. В результате, на каждом шаге размер отсортированной части увеличивается и в конце концов весь список становится отсортированным."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://media.proglib.io/wp-uploads/-000//1/596b723189cb1_Zmjm3wv.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n",
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n"
     ]
    }
   ],
   "source": [
    "# базовый вариант (почти на любом языке)\n",
    "def insertion_sort1(a):\n",
    "    n = len(a)\n",
    "    for i in range(1, n):\n",
    "        el = a[i] # выбираем очередной элемент\n",
    "        j = i-1\n",
    "        while j>=0 and a[j]>el: # двигаем\n",
    "            a[j+1] = a[j]   \n",
    "            j -= 1\n",
    "        a[j+1] = el\n",
    "\n",
    "# добавим немного питона\n",
    "def insertion_sort2(a):\n",
    "    n = len(a)\n",
    "    for i in range(1, n):\n",
    "        el = a[i] # выбираем очередной элемент\n",
    "        if el<a[i-1]:\n",
    "            for j in range(i):\n",
    "                if a[j]>=el:\n",
    "                    a.insert(j, el)\n",
    "                    a.pop(i+1)\n",
    "                    break\n",
    "\n",
    "\n",
    "# тестирование\n",
    "b = a1.copy()\n",
    "insertion_sort1(b)\n",
    "print(b)\n",
    "\n",
    "b = a1.copy()\n",
    "insertion_sort2(b)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "время сортировки - 3.1100 сек.\n",
      "время сортировки - 0.6400 сек.\n"
     ]
    }
   ],
   "source": [
    "# сравнение времени работы\n",
    "b = a2.copy()\n",
    "c = a2.copy()\n",
    "\n",
    "t = time.time()\n",
    "insertion_sort1(b)\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')\n",
    "\n",
    "t = time.time()\n",
    "insertion_sort2(c)\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Вставки + бинарный поиск"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Существенное ускорение сортировки вставками можно достичь, если учесть, что искать место вставки нужно в отсортированном списке. А значит можно заменить процесс полного перебора на поиск на основе деления списка пополам."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n"
     ]
    }
   ],
   "source": [
    "# вспомогательная функция\n",
    "def find_pos(a, x):\n",
    "    '''\n",
    "    функция находит номер позиции\n",
    "    в упорядоченном списке a,\n",
    "    на которую можно поставить элемент x,\n",
    "    так что упорядоченность списка \n",
    "    сохранится\n",
    "    '''\n",
    "    n = len(a)\n",
    "    if x<=a[0]:\n",
    "        return 0\n",
    "    if x>=a[n-1]:\n",
    "        return n\n",
    "    n1 = 0\n",
    "    n2 = n-1\n",
    "    while n2-n1>1:\n",
    "        k = (n1+n2)//2\n",
    "        if a[k]==x:\n",
    "            return k\n",
    "        elif x<a[k]:\n",
    "            n2 = k\n",
    "        else:\n",
    "            n1 = k\n",
    "    return n2         \n",
    "\n",
    "# прежде, чем использовать, нужно проверить\n",
    "b = a1.copy()\n",
    "b.sort()\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_pos(b, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n"
     ]
    }
   ],
   "source": [
    "def insertion_sort3(a):\n",
    "    n = len(a)\n",
    "    for i in range(1, n):\n",
    "        el = a[i] # выбираем очередной элемент\n",
    "        if el<a[i-1]:\n",
    "            j = find_pos(a[:i], el)\n",
    "            a.insert(j, el)\n",
    "            a.pop(i+1)\n",
    "\n",
    "# тестирование\n",
    "b = a1.copy()\n",
    "insertion_sort3(b)\n",
    "print(b)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "время сортировки - 0.2500 сек.\n"
     ]
    }
   ],
   "source": [
    "# сравнение времени работы\n",
    "b = a2.copy()\n",
    "\n",
    "t = time.time()\n",
    "insertion_sort3(b)\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Алгоритм быстрой сортировки (Quick sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Данный алгоритм относится к алгоритмам типа «разделяй и властвуй». \n",
    "Он начинается с выбора одного из элементов в качестве опорного. Далее все элементы меньше него перемещаются влево, а равные и большие элементы перемещаются вправо. При этом к каждой из двух частей можно (рекурсивно) применить этот же подход.\n",
    "В качестве опорного можно выбирать случайный элемент в списке. В реализации ниже будем использовать первый элемент."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 4, 5, 6, 7, 7, 7, 7, 10, 13, 15, 20, 20]\n"
     ]
    }
   ],
   "source": [
    "def qsort(a):\n",
    "    '''\n",
    "    Это функция. \n",
    "    Она не сортирует список \"на месте\",\n",
    "    а возвращает новый, отсортированный\n",
    "    '''\n",
    "    if a:\n",
    "        x = a[0]\n",
    "        a1 = qsort([el for el in a if el<x])\n",
    "        a2 = [el for el in a if el==x]\n",
    "        a3 = qsort([el for el in a if el>x])\n",
    "        return a1+a2+a3\n",
    "    else:\n",
    "        return []\n",
    "\n",
    "# тестирование\n",
    "b = a1.copy()\n",
    "print(qsort(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "время сортировки - 0.0400 сек.\n"
     ]
    }
   ],
   "source": [
    "# сравнение времени работы\n",
    "b = a2.copy()\n",
    "\n",
    "t = time.time()\n",
    "qsort(b)\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "время сортировки - 0.0000 сек.\n"
     ]
    }
   ],
   "source": [
    "# сравнение времени работы\n",
    "b = a2.copy()\n",
    "\n",
    "t = time.time()\n",
    "b.sort()\n",
    "dt = time.time() - t\n",
    "print(f'время сортировки - {dt:1.4f} сек.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}