sorting

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Майнор \"Интеллектуальный анализ данных\" \n",
    "# Курс \"Введение в программирование\"\n",
    "<img src=\"../img/faculty_logo.jpg\" height=\"240\" width=\"240\">\n",
    "## Автор материала: преподаватель ФКН НИУ ВШЭ Кашницкий Юрий\n",
    "Материал распространяется на условиях лицензии <a href=\"http://creativecommons.org/licenses/by-sa/4.0/\">Creative Commons Attribution-Share Alike 4.0</a>. Можно использовать в любых целях, но с обязательным упоминанием автора курса и аффилиации."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Семинар 9. Методы сортировки\n",
    "#### Цель - уметь объяснить и реализовать сортировки пузырьком, слиянием, вставками, быструю сортировку и сортировку Шелла.\n",
    "\n",
    "Чтобы было интерактивно и наглядно:\n",
    "http://www.sorting-algorithms.com/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Пузырек\n",
    "**Пузырьковая сортировка** делает по списку несколько проходов. Она сравнивает стоящие рядом элементы и меняет местами те из них, что находятся в неправильном порядке. Каждый проход по списку помещает следующее наибольшее значение на его правильную позицию. В сущности, каждый элемент “пузырьком” всплывает на своё место.\n",
    "\n",
    "Рассмотрим на примере:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='../img/bubblepass.png'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На рисунке показан первый проход пузырьковой сортировки. Затенёные элементы будут сравниваться для определения в правильном ли порядке они стоят.\n",
    "\n",
    "Операция перестановки, иногда называемая **“обменом”**, в Python несколько проще, чем в большинстве других языков программирования. Обычно перестановка местами двух элементов списка требует временного сохранения их местоположения (дополнительный объём памяти). Следующий фрагмент кода:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "alist = [1,2,3,4,5]\n",
    "i = 0\n",
    "temp = 0\n",
    "j = 1\n",
    "temp = alist[i]\n",
    "alist[i] = alist[j]\n",
    "alist[j] = temp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В Python возможно одновременное присваивание:\n",
    "\n",
    "<img src='../img/swap.png'>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def bubbleSort(alist):\n",
    "    for passnum in range(len(alist)-1, 0, -1):\n",
    "        for i in range(passnum):\n",
    "            if alist[i] > alist[i + 1]:\n",
    "                temp = alist[i]\n",
    "                alist[i] = alist[i + 1]\n",
    "                alist[i + 1] = temp\n",
    "\n",
    "alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "bubbleSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Однако**, поскольку пузырьковая сортировка делает проход по всей несортированной части списка, она умеет то, что не могут большинство сортировочных алгоритмов. В частности, если во время прохода не было сделано ни одной перестановки, то мы знаем, что список уже отсортирован. Таким образом, алгоритм может быть модифицирован, чтобы останавливаться раньше, если обнаруживает, что задача выполнена. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[20, 30, 40, 50, 60, 70, 80, 90, 100, 110]\n"
     ]
    }
   ],
   "source": [
    "def shortBubbleSort(alist):\n",
    "    exchanges = True\n",
    "    passnum = len(alist) - 1\n",
    "    while passnum > 0 and exchanges:\n",
    "       exchanges = False\n",
    "       for i in range(passnum):\n",
    "           if alist[i] > alist[i + 1]:\n",
    "               exchanges = True\n",
    "               temp = alist[i]\n",
    "               alist[i] = alist[i + 1]\n",
    "               alist[i + 1] = temp\n",
    "       passnum = passnum - 1\n",
    "\n",
    "alist=[20, 30, 40, 90, 50, 60, 70, 80, 100, 110]\n",
    "shortBubbleSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Сортировка вставками\n",
    "\n",
    "Сортировка вставками, имея по-прежнему сложность **$O(n^2)$**, работает несколько иначе. Она всегда поддерживает в сортированном виде подсписок на нижних индексах списка. Каждый новый элемент “вставляется” в упорядоченный на прошлой итерации подсписок так, чтобы тот остался сортированным и стал на один элемент больше. Рисунок ниже демонстрирует процесс сортировки вставками. Затенённые элементы представляют собой упорядоченные подсписки, которые алгоритм создаёт на каждом проходе.\n",
    "\n",
    "<img src='../img/insertionsort.png'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Максимальное количество сравнений для сортировки вставками равно сумме первых **n−1** целых. Т.е. снова **$O(n^2)$**. Однако, в наилучшем случае на каждом проходе потребуется всего одно сравнение. Это произойдёт, когда список уже отсортирован.\n",
    "\n",
    "Важное замечание о противопоставлении сдвига и обмена: в общем случае операция сдвига требует приблизительно трети от вычислительной работы обмена, поскольку делается всего одно присваивание. В контрольных исследованиях сортировка вставками имеет очень хорошую производительность."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def insertionSort(alist):\n",
    "   for index in range(1, len(alist)):\n",
    "\n",
    "     currentvalue = alist[index]\n",
    "     position = index\n",
    "\n",
    "     while position > 0 and alist[position - 1] > currentvalue:\n",
    "         alist[position] = alist[position - 1]\n",
    "         position -= 1\n",
    "\n",
    "     alist[position] = currentvalue\n",
    "\n",
    "alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "insertionSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Сортировака Шелла\n",
    "\n",
    "Сортировку Шелла иногда называют **“сортировкой с уменьшением инкремента”**. Она улучшает сортировку вставками, разбивая первоначальный список на несколько подсписков, каждый из которых сортируется по отдельности. Оригинальный способ выбора таких подсписков - ключевая идея сортировки Шелла. Вместо того, чтобы выделять подсписки из стоящих рядом элементов, сортировка Шелла использует инкремент **i (приращение)**, чтобы создавать подсписки из значений, отстоящих на расстоянии **i** друг от друга.\n",
    "\n",
    "Рассмотрим пример на рисунке ниже. \n",
    "\n",
    "Если мы используем тройку в качестве инкремента, то получим три подсписка, каждый из которых можно отсортировать вставками.\n",
    "\n",
    "<img src='../img/shellsortA.png'>\n",
    "\n",
    "После завершения этих сортировок мы получим список:\n",
    "\n",
    "<img src='../img/shellsortB.png'>\n",
    "\n",
    "Реализация:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]\n",
      "After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]\n",
      "After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]\n",
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def shellSort(alist):\n",
    "    sublistcount = len(alist) // 2\n",
    "    while sublistcount > 0:\n",
    "\n",
    "      for startposition in range(sublistcount):\n",
    "        gapInsertionSort(alist, startposition, sublistcount)\n",
    "\n",
    "      print(\"After increments of size\", sublistcount,\n",
    "                                   \"The list is\", alist)\n",
    "\n",
    "      sublistcount = sublistcount // 2\n",
    "\n",
    "def gapInsertionSort(alist, start, gap):\n",
    "    for i in range(start + gap, len(alist), gap):\n",
    "\n",
    "        currentvalue = alist[i]\n",
    "        position = i\n",
    "\n",
    "        while position >= gap and alist[position - gap] > currentvalue:\n",
    "            alist[position]=alist[position - gap]\n",
    "            position = position-gap\n",
    "\n",
    "        alist[position] = currentvalue\n",
    "\n",
    "alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "shellSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Сортировка слиянием\n",
    "\n",
    "Это рекурсивный алгоритм, который постоянно разбивает список пополам. Если список пуст или состоит из одного элемента, то он отсортирован по определению (базовый случай). Если в списке больше, чем один элемент, мы разбиваем его и рекурсивно вызываем сортировку слиянием для каждой из половин. После того, как обе они уже отсортированы, выполняется основная операция, называемая слиянием.\n",
    "\n",
    "**Слияние** - это процесс комбинирования двух меньших сортированных списков в один новый, но тоже отсортированный\n",
    "\n",
    "**Разбиение:**\n",
    "<img src='../img/msortA.png'>\n",
    "\n",
    "**Слияние:**\n",
    "<img src = '../img/mergesortB.png'>\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Начинаем с проверки базового условия. Если длина списка меньше или равна единице, то он уже отсортирован, и в дальшейшей обработке нет необходимости. С другой стороны, если длина больше единицы, то мы используем операцию Python *slice*, чтобы извлечь правую и левую части. Важно отметить, что список может иметь нечётное количество элементов. Для алгоритма это не принципиально, поскольку длины будут различаться максимум на единицу."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Splitting  [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
      "Splitting  [54, 26, 93, 17]\n",
      "Splitting  [54, 26]\n",
      "Splitting  [54]\n",
      "Merging  [54]\n",
      "Splitting  [26]\n",
      "Merging  [26]\n",
      "Merging  [26, 54]\n",
      "Splitting  [93, 17]\n",
      "Splitting  [93]\n",
      "Merging  [93]\n",
      "Splitting  [17]\n",
      "Merging  [17]\n",
      "Merging  [17, 93]\n",
      "Merging  [17, 26, 54, 93]\n",
      "Splitting  [77, 31, 44, 55, 20]\n",
      "Splitting  [77, 31]\n",
      "Splitting  [77]\n",
      "Merging  [77]\n",
      "Splitting  [31]\n",
      "Merging  [31]\n",
      "Merging  [31, 77]\n",
      "Splitting  [44, 55, 20]\n",
      "Splitting  [44]\n",
      "Merging  [44]\n",
      "Splitting  [55, 20]\n",
      "Splitting  [55]\n",
      "Merging  [55]\n",
      "Splitting  [20]\n",
      "Merging  [20]\n",
      "Merging  [20, 55]\n",
      "Merging  [20, 44, 55]\n",
      "Merging  [20, 31, 44, 55, 77]\n",
      "Merging  [17, 20, 26, 31, 44, 54, 55, 77, 93]\n",
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def mergeSort(alist):\n",
    "    print(\"Splitting \",alist)\n",
    "    if len(alist) > 1:\n",
    "        mid = len(alist) // 2\n",
    "        lefthalf = alist[:mid]\n",
    "        righthalf = alist[mid:]\n",
    "\n",
    "        mergeSort(lefthalf)\n",
    "        mergeSort(righthalf)\n",
    "\n",
    "        i, j, k = 0, 0, 0\n",
    "        while i < len(lefthalf) and j < len(righthalf):\n",
    "            if lefthalf[i] < righthalf[j]:\n",
    "                alist[k] = lefthalf[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                alist[k] = righthalf[j]\n",
    "                j += 1\n",
    "            k += 1\n",
    "\n",
    "        while i < len(lefthalf):\n",
    "            alist[k]=lefthalf[i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "\n",
    "        while j < len(righthalf):\n",
    "            alist[k] = righthalf[j]\n",
    "            j += 1\n",
    "            k += 1\n",
    "    print(\"Merging \",alist)\n",
    "\n",
    "alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "mergeSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Быстрая сортировка\n",
    "\n",
    "Быстрая сортировка использует технику *“разделяй и властвуй”*, чтобы получить те же преимущества, что и сортировка слиянием, но при этом не использовать дополнительное место. Однако, ценой за это станет то, что список может не поделиться пополам, что приводит к уменьшению производительности.\n",
    "\n",
    "Сначала быстрая сортировка выбирает значение, которое называется **опорным элементом**. Несмотря на то, что есть много способов выбрать его, мы будем просто использовать первое значение в списке. Роль опорного элемента заключается в помощи при разбиении списка. Позиция, на которой он окажется в итоговом сортированном списке, обычно называемая **точкой разбиения**, будет использоваться для разделения списка при последующих вызовах быстрой сортировки.\n",
    "\n",
    "**Пример:**\n",
    "\n",
    "<img src='../img/firstsplit.png'>\n",
    "\n",
    "54 выступает в роли первого опорного значения. Поскольку мы уже рассматривали этот пример несколько раз, то знаем, что 54 в итоге окажется на позиции, занятой сейчас 31. Далее происходит процесс разделения. Он находит точку разделения и одновременно перемещает элементы по соответствующим сторонам списка, в зависимости от того, больше они или меньше опорной величины.\n",
    "\n",
    "Разбиение начинается с определения двух маркеров положения - назовём их **leftmark** и **rightmark** - в начале и в конце оставшихся элементов списка.\n",
    "\n",
    "В процессе разбиения элементы, лежащие по неправильным сторонам от опорного, должны перемещаться пока маркеры не сойдутся в точке разделения:\n",
    "\n",
    "<img src='../img/partitionA.png'>\n",
    "\n",
    "Мы начинаем с увеличения на единицу **leftmark**, пока не находим значение, большее опорного. Тогда мы уменьшаем на единицу **rightmark**, пока не находим значение, меньшее опорного. В этот момент мы имеем два элемента, находящихся не на своих местах относительно итоговой точки разбиения. В нашем примере таковыми являются 93 и 20. Теперь можно поменять их местами и повторить процесс заново.\n",
    "\n",
    "Когда **rightmark** становится меньше **leftmark**, мы останавливаемся. Позиция **rightmark** в данный момент - точка разбиения. Опорное значение следует поменять местами с её содержимым, и тогда оно будет стоять на своём месте.\n",
    "\n",
    "<img src='../img/partitionB.png'>\n",
    "\n",
    "*В дополнение, все элементы слева от точки разбиения теперь меньше опорного значения, а справа - больше. Список поделен на две части, и быстрая сортировка может быть рекурсивно применена к каждой из них.*\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Функция **quickSort**, показанная в реализации ниже, вызывает другую рекурсивную функцию - **quickSortHelper**. Она начинает работать с базового случая, аналогичного сортировке слиянием. Если длина списка меньше или равна единице, то он уже отсортирован. Если больше, то он может быть разделен и рекурсивно отсортирован. Функция **partition** воплощает описанный ранее процесс."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "def quickSort(alist):\n",
    "   quickSortHelper(alist, 0, len(alist) - 1)\n",
    "\n",
    "def quickSortHelper(alist, first, last):\n",
    "   if first<last:\n",
    "\n",
    "       splitpoint = partition(alist, first, last)\n",
    "\n",
    "       quickSortHelper(alist, first, splitpoint-1)\n",
    "       quickSortHelper(alist, splitpoint + 1, last)\n",
    "\n",
    "def partition(alist, first, last):\n",
    "   pivotvalue = alist[first]\n",
    "\n",
    "   leftmark = first+1\n",
    "   rightmark = last\n",
    "\n",
    "   done = False\n",
    "   while not done:\n",
    "\n",
    "       while leftmark <= rightmark and \\\n",
    "               alist[leftmark] <= pivotvalue:\n",
    "           leftmark = leftmark + 1\n",
    "\n",
    "       while alist[rightmark] >= pivotvalue and \\\n",
    "               rightmark >= leftmark:\n",
    "           rightmark = rightmark -1\n",
    "\n",
    "       if rightmark < leftmark:\n",
    "           done = True\n",
    "       else:\n",
    "           temp = alist[leftmark]\n",
    "           alist[leftmark] = alist[rightmark]\n",
    "           alist[rightmark] = temp\n",
    "\n",
    "   temp = alist[first]\n",
    "   alist[first] = alist[rightmark]\n",
    "   alist[rightmark] = temp\n",
    "\n",
    "\n",
    "   return rightmark\n",
    "\n",
    "alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "quickSort(alist)\n",
    "print(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Timsort\n",
    "\n",
    "Timsort — это не полностью самостоятельный алгоритм, а гибрид, эффективная комбинация нескольких других алгоритмов, приправленная собственными идеями. Очень коротко суть алгоритма можно объяснить так:\n",
    "\n",
    "1. По специальному алгоритму разделяем входной массив на подмассивы.\n",
    "2. Сортируем каждый подмассив обычной сортировкой вставками.\n",
    "3. Собираем отсортированные подмассивы в единый массив с помощью модифицированной сортировки слиянием.\n",
    "\n",
    "Дьявол, как всегда, скрывается в деталях, а именно в алгоритме из пункта 1 и модификации сортировки слиянием из пункта 3.\n",
    "\n",
    "**ПОЧЕМУ ?**\n",
    "\n",
    "<img src='../img/timsort_wiki.png'>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}