Sorting2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 272,
   "id": "8d82dec5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def irange(*args):\n",
    "    \"\"\"\n",
    "    An inclusive version of range.\n",
    "    Can be used with 1, 2, or 3 arguments.\n",
    "    \"\"\"\n",
    "    if len(args) == 0:\n",
    "        raise TypeError(\"inclusive_range expected at least 1 argument, got 0\")\n",
    "    elif len(args) == 1:\n",
    "        start, stop, step = 0, args[0], 1\n",
    "    elif len(args) == 2:\n",
    "        start, stop, step = args[0], args[1], 1\n",
    "    elif len(args) == 3:\n",
    "        start, stop, step = args\n",
    "    else:\n",
    "        raise TypeError(f\"inclusive_range expected at most 3 arguments, got {len(args)}\")\n",
    "    \n",
    "    # Modify stop value to make it inclusive\n",
    "    if step > 0:\n",
    "        stop += 1\n",
    "    else:\n",
    "        stop -= 1\n",
    "\n",
    "    return range(start, stop, step)\n",
    "\n",
    "def swap_elements(lst, index1, index2):\n",
    "    \"\"\"\n",
    "    Swap elements in the list at the given indices.\n",
    "\n",
    "    Args:\n",
    "    - lst (list): The list of elements.\n",
    "    - index1 (int): The index of the first element to swap.\n",
    "    - index2 (int): The index of the second element to swap.\n",
    "\n",
    "    Returns:\n",
    "    - list: The list with swapped elements.\n",
    "    \"\"\"\n",
    "    if index1 < 0 or index1 >= len(lst) or index2 < 0 or index2 >= len(lst):\n",
    "        raise ValueError(\"Index out of range\")\n",
    "\n",
    "    lst[index1], lst[index2] = lst[index2], lst[index1]\n",
    "    return lst\n",
    "\n",
    "def print_part(A, left, right):\n",
    "    \"\"\"\n",
    "    Prints part of the array\n",
    "    \n",
    "    Args:\n",
    "    - A (list): Array of elements\n",
    "    - left: left boundary index\n",
    "    - right: right boundary index\n",
    "    \"\"\"\n",
    "    print(\"[\", end=\"\")\n",
    "    for i in irange(left, right):\n",
    "        print(A[i], end=\"\")\n",
    "        if i != right:\n",
    "            print(\", \", end=\"\")      \n",
    "    print(\"]\")\n",
    "    \n",
    "    \n",
    "# Stack helpers\n",
    "    \n",
    "def Push(s, elem):\n",
    "    s.append(elem)\n",
    "    \n",
    "def Top(s):\n",
    "    return s[len(s)-1]\n",
    "    \n",
    "def Pop(s):\n",
    "    s.pop()\n",
    "    \n",
    "def IsEmpty(s):\n",
    "    return len(s) == 0\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff512296",
   "metadata": {},
   "source": [
    "# Bubble-Insert Sort (Shuttle Sort)\n",
    "\n",
    "MAX je počet prvků, MAX-1 je index nejvyššího prvku\n",
    "\n",
    "Mám levou (seřazenou) a pravou (neseřazenou) část.\n",
    "Začnu první **dvojicí** (indexy j a i), pravý prvek si uložím to **tmp**\n",
    "* Pokud je ve správném pořadí, nechám\n",
    "* pokud není, jdu do while a posunu první prvek na druhou pozici (udělám místo pro **tmp**)\n",
    "\n",
    "Na konci cyklu mi **j+1** udává pozici, kam se má umístit prvek **tmp**.\n",
    "Prvek **tmp** se umístí na správnou pozici (zůstane, kde je, nebo se přesune)\n",
    "\n",
    "První 2 prvky jsou nyní uspořádané.\n",
    "\n",
    "např.:\n",
    "[4, 2, 1, 3] -> [**2**, **4**, 1, 3]\n",
    "\n",
    "Zkusím přidat další prvek (**tmp**, index 2) - porovnám hodnoty prvků na indexech 1 a 2 (**tmp**)\n",
    "* Pokud je další prvek větší, nic se neděje\n",
    "* Pokud je další prvek menší, v cyklu while \"probubláním\" posunu překážející prvky doprava.\n",
    "\n",
    "Nakonec zase umístím **tmp** na správné místo (stejné nebo nové)\n",
    "\n",
    "např.:\n",
    "\n",
    "[**2**, **4**, 1, 3] -> [**1**, **2**, **4**, 3]\n",
    "\n",
    "A takto pokračuji a přidávám další prvky, dokud neumístím poslední prvek.\n",
    "\n",
    "[**1**, **2**, **4**, 3] -> [**1**, **2**, **3**, **4**]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "id": "034e5fe5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 2, 1, 0]\n",
      "===== FOR =====\n",
      "i = 1\n",
      "tmp = A[i] = A[1] = 2\n",
      "j = 1-1 = 0\n",
      "WHILE? 0 >= 0 and 2 < 4 ???\n",
      "\n",
      "--- WHILE ---\n",
      "4 jde doprava:\n",
      "A[1] <- 4\n",
      "j = 0-1 = -1\n",
      "[4, 4, 1, 0]\n",
      "------------\n",
      "A[j+1] = A[-1+1] = A[0] <- 2 (tmp) umistime\n",
      "[2, 4, 1, 0]\n",
      " \n",
      "===== FOR =====\n",
      "i = 2\n",
      "tmp = A[i] = A[2] = 1\n",
      "j = 2-1 = 1\n",
      "WHILE? 1 >= 0 and 1 < 4 ???\n",
      "\n",
      "--- WHILE ---\n",
      "4 jde doprava:\n",
      "A[2] <- 4\n",
      "j = 1-1 = 0\n",
      "[2, 4, 4, 0]\n",
      "------------\n",
      "\n",
      "--- WHILE ---\n",
      "2 jde doprava:\n",
      "A[1] <- 2\n",
      "j = 0-1 = -1\n",
      "[2, 2, 4, 0]\n",
      "------------\n",
      "A[j+1] = A[-1+1] = A[0] <- 1 (tmp) umistime\n",
      "[1, 2, 4, 0]\n",
      " \n",
      "===== FOR =====\n",
      "i = 3\n",
      "tmp = A[i] = A[3] = 0\n",
      "j = 3-1 = 2\n",
      "WHILE? 2 >= 0 and 0 < 4 ???\n",
      "\n",
      "--- WHILE ---\n",
      "4 jde doprava:\n",
      "A[3] <- 4\n",
      "j = 2-1 = 1\n",
      "[1, 2, 4, 4]\n",
      "------------\n",
      "\n",
      "--- WHILE ---\n",
      "2 jde doprava:\n",
      "A[2] <- 2\n",
      "j = 1-1 = 0\n",
      "[1, 2, 2, 4]\n",
      "------------\n",
      "\n",
      "--- WHILE ---\n",
      "1 jde doprava:\n",
      "A[1] <- 1\n",
      "j = 0-1 = -1\n",
      "[1, 1, 2, 4]\n",
      "------------\n",
      "A[j+1] = A[-1+1] = A[0] <- 0 (tmp) umistime\n",
      "[0, 1, 2, 4]\n",
      " \n"
     ]
    }
   ],
   "source": [
    "A = [4, 2, 1, 0]\n",
    "MAX = len(A)\n",
    "print(A)\n",
    "\n",
    "for i in irange(1,MAX-1):                   \n",
    "    tmp = A[i]                         ;print(f\"===== FOR =====\\ni = {i}\"); print(f\"tmp = A[i] = A[{i}] = {A[i]}\");\n",
    "    j = i-1                            ;print(f\"j = {i}-1 = {j}\"); print(f\"WHILE? {j} >= 0 and {tmp} < {A[j]} ???\")\n",
    "    while j >= 0 and tmp < A[j]:\n",
    "        A[j+1] = A[j]                  ;print(f\"\\n--- WHILE ---\"); print(f\"{A[j]} jde doprava:\"); print(f\"A[{j+1}] <- {A[j]}\"); \n",
    "        j = j-1                        ;print(f\"j = {j+1}-1 = {j}\"); print(A); print(\"------------\")\n",
    "    A[j+1] = tmp                       ;print(f\"A[j+1] = A[{j}+1] = A[{j+1}] <- {tmp} (tmp) umistime\"); print(A); print(\" \")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2b4475d",
   "metadata": {},
   "source": [
    " ### Zhodnocení Bubble-insert sort\n",
    " * Často vyžaduje **méně operací** (porovnání, záměn) než klasický Bubble sort.\n",
    " * Bohužel stále **pomalá** - 2 cykly v sobě.\n",
    "   * Může se stát, že prvek potřebujeme vkládat až úplně na začátek\n",
    "   * Nejhorší případ - opačně seřazená posloupnoust - n*n iterací\n",
    "   * Kvadratická časová složitost (n^2)\n",
    " * **Stabilní** - vhodná pro vícenásobné řazení podle více klíčů\n",
    " * Chová se **přirozeně** (jako ostatní obdoby Bubble sortu)\n",
    " * Pracuje **in situ**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "993eba73",
   "metadata": {},
   "source": [
    "# Binary-Insert Sort\n",
    "\n",
    "Místo pro vložení prvku v seřazené posloupnosti hledáme **binárním vyhledáváním**.\n",
    "Protože chceme **stabilní** chování, mohli bychom využít **Dijkstrovu variantu** binárního vyhledávání.\n",
    "* Nekončí, když najdeme prvek s daným klíčem.\n",
    "* Hledá dál, dokud nachází stejné klíče -> chci nejpravější\n",
    "\n",
    "Já ale nepotřebuji nejpravější index, potřebuji index o 1 za - tj. využíváme **lehce upravenou Dijkstrovu variantu**.\n",
    "\n",
    "Princip:\n",
    "\n",
    "1) **Vyhledání pozice, kam budeme vkládat** - hledáme místo, kam vložit **tmp**\n",
    "  * Hledám místo pro **tmp**, které je na pozici **i**.\n",
    "  * Řeší se binárním vyhledáváním v počátečním rozsahu **0** až **i-1**.\n",
    "    * Pokud je **tmp** menší než střed **A[m]**, jdeme doleva.\n",
    "    * Pokud je **tmp** větší/roven středu **A[m]**, jdeme doprava.\n",
    "    * Končím, až se mi index překříží\n",
    "  \n",
    "\n",
    "2) **Posun segmentu** - posouváme doprava překážející segment\n",
    "\n",
    "3) **Vložení prvku** - vložíme prvek **tmp** na příslušné místo.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "id": "2b24cdc5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 2, 1, 0]\n",
      "===== FOR =====\n",
      "i = 1\n",
      "tmp = A[i] = A[1] = 2\n",
      "right = 0\n",
      "WHILE 0 <= 0 ???\n",
      "---WHILE 0 <= 0 ---\n",
      "m = (0 + 0) / 2 = 0\n",
      "(tmp) 2 < 4 (A[0])\n",
      "right = 0-1 = -1\n",
      "\n",
      "FOR j=0: A[0+1] <- 4\n",
      "A[left] = A[0] = 2 (tmp) umistime\n",
      "[2, 4, 1, 0]\n",
      " \n",
      "===== FOR =====\n",
      "i = 2\n",
      "tmp = A[i] = A[2] = 1\n",
      "right = 1\n",
      "WHILE 0 <= 1 ???\n",
      "---WHILE 0 <= 1 ---\n",
      "m = (0 + 1) / 2 = 0\n",
      "(tmp) 1 < 2 (A[0])\n",
      "right = 0-1 = -1\n",
      "\n",
      "FOR j=1: A[1+1] <- 4\n",
      "\n",
      "FOR j=0: A[0+1] <- 2\n",
      "A[left] = A[0] = 1 (tmp) umistime\n",
      "[1, 2, 4, 0]\n",
      " \n",
      "===== FOR =====\n",
      "i = 3\n",
      "tmp = A[i] = A[3] = 0\n",
      "right = 2\n",
      "WHILE 0 <= 2 ???\n",
      "---WHILE 0 <= 2 ---\n",
      "m = (0 + 2) / 2 = 1\n",
      "(tmp) 0 < 2 (A[1])\n",
      "right = 1-1 = 0\n",
      "---WHILE 0 <= 0 ---\n",
      "m = (0 + 0) / 2 = 0\n",
      "(tmp) 0 < 1 (A[0])\n",
      "right = 0-1 = -1\n",
      "\n",
      "FOR j=2: A[2+1] <- 4\n",
      "\n",
      "FOR j=1: A[1+1] <- 2\n",
      "\n",
      "FOR j=0: A[0+1] <- 1\n",
      "A[left] = A[0] = 0 (tmp) umistime\n",
      "[0, 1, 2, 4]\n",
      " \n"
     ]
    }
   ],
   "source": [
    "A = [4, 2, 1, 0]\n",
    "MAX = len(A)\n",
    "print(A)\n",
    "\n",
    "for i in irange(1,MAX-1):                   \n",
    "    tmp = A[i]                         ;print(f\"===== FOR =====\\ni = {i}\"); print(f\"tmp = A[i] = A[{i}] = {A[i]}\");\n",
    "    left = 0\n",
    "    right = i-1                        ;print(f\"right = {right}\"); print(f\"WHILE {left} <= {right} ???\")\n",
    "    \n",
    "    # 1) Vyhledani pozice, kam vkladat\n",
    "    while (left <= right):\n",
    "        m  = int((left+right) / 2)     ;print(f\"---WHILE {left} <= {right} ---\"); print(f\"m = ({left} + {right}) / 2 = {m}\")\n",
    "        if tmp < A[m]:\n",
    "            right = m-1                ;print(f\"(tmp) {tmp} < {A[m]} (A[{m}])\"); print(f\"right = {m}-1 = {right}\")\n",
    "        else:\n",
    "            left = m+1                 ;print(f\"NOT (tmp) {tmp} < {A[m]} (A[{m}])\"); print(f\"left = {m}+1 = {left}\");\n",
    "\n",
    "    # 2) Posun segmentu\n",
    "    for j in irange (i-1, left, -1):\n",
    "        A[j+1] = A[j]                  ;print(f\"\\nFOR j={j}: A[{j}+1] <- {A[j]}\")\n",
    "    \n",
    "    # 3) Vlozeni prvku\n",
    "    A[left] = tmp                      ;print(f\"A[left] = A[{left}] = {tmp} (tmp) umistime\"); print(A); print(\" \")\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97055929",
   "metadata": {},
   "source": [
    " ### Zhodnocení Binary-insert sort\n",
    "* O něco rychlejší než Bubble-insert sort - nemusím při posuvech segmentu dělat neustálá porovnávání (porovnávání se přesunulo do binárního vyhledávání)\n",
    "* Binární vyhledávání celý postup **příliš nezrychlilo**, pořád musím **posouvat segmenty pole**.\n",
    "* Proto je časová složitost je stále **kvadratická** (n^2)\n",
    "* **Stabilní**\n",
    "* Chová se **přirozeně**\n",
    "* Pracuje **in situ** - nepotřebuje externí pole pro ukládání prvků"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f7df830",
   "metadata": {},
   "source": [
    "# Quick Sort\n",
    "\n",
    "* Pro nalezení mediánu potřebuji seřazenou posloupnost -> medián se nepoužije.\n",
    "* I metody pro přibližný odhad trvají dlouho.\n",
    "* Použijeme **pseudomedián (pivot)** - Čím lépe zvolený (bližší reálnému mediánu), tím lépe se bude algoritmus chovat. Teoreticky lze však použít libovolný prvek se souboru. Tato implementace bere pseudomedián jako **prostřední prvek**. Zejména, pokud je posloupnost částečně seřazená, máme velkou šanci, že se mediánu přiblížíme.\n",
    "* Quicksort vrací 2 indexy i a j, na které se bude znovu volat\n",
    "* Využívá funkce **partition**, která rozdělá pole na prvky \n",
    "* Autor: C. A. R. Hoare (Tony Hoare)\n",
    "* Příklad: [7, 4, 13, 1, 6, 9, 2]\n",
    "  * Partiton (PM=1)\n",
    "    * Jdu zleva i=0, 7 > 1, zastavím se\n",
    "    * Jdu zprava j=3, všechno je větší než 1, zastavím se na 1 (PM)\n",
    "    * 7 <--> 1\n",
    "    * [**1**, 4, 13, **7**, 6, 9, 2]\n",
    "    * Jdu zleva i=1, 4 > 1, zastavím se\n",
    "    * Jdu zprava zastavím se až na j=0\n",
    "    * j < i, končím Partition. Vrací i=1, j=0\n",
    "  * left = j -> pro **levou část** už se Quicksort **nevolá**.\n",
    "  * i < right -> **volám Quicksort** pro **pravou část!**\n",
    "  * Partition pro [1 | **4, 13, 7, 6, 9, 2**] (PM=7)\n",
    "    * Jdu zleva, i=2, 13 > 7, zastavím se\n",
    "    * Jdu zprava, j=6, 2 < 7, zastavím se\n",
    "    * 13 <--> 2\n",
    "    * [1 | 4, **2**, 7, 6, 9, **13**]\n",
    "    * Jdu zleva i=3, narazím na 7 (PM), zastavím se\n",
    "    * Jdu zprava j=4, 6 < 7, zastavím se\n",
    "    * 7 <--> 6\n",
    "    * [1 | 4, 2, **6**, **7**, 9, 13]\n",
    "    * i se zvýší, j se sníží -> překříží se. Partition končí.\n",
    "   * Další volání Quicksort by bylo pro:\n",
    "     * Levé pro [4, 2, 6]\n",
    "       * PARTITION, PM=2\n",
    "       * 4 <--> 6\n",
    "     * Pravé pro [7, 9, 13]\n",
    "       * PARTITION, PM=9, **nic se nemusí prohazovat**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 277,
   "id": "54e8b7e4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition (A, left, right):\n",
    "    \"\"\"\n",
    "    A - pole\n",
    "    left, right - indexy, které říkají, kterou částí pole se máme zabývat\n",
    "    \"\"\"\n",
    "    i = left             ;print(f\"---- partition(A, {left}, {right}) ----\"); print_part(A,left,right)\n",
    "    j = right            ;origleft=left; origright=right\n",
    "    \n",
    "    # Ustavím pseudomedián\n",
    "    PM = A[int((i+j) / 2)]\n",
    "    print(f\"PM: {PM}\")\n",
    "    \n",
    "    while True: # do\n",
    "        # Jdu zleva\n",
    "        # Dokud jsou prvky menší než pseudomedián, přeskakuju je\n",
    "        while A[i] < PM:\n",
    "            i = i + 1\n",
    "            \n",
    "        # Jdu zprava\n",
    "        # Dokud jsou prvky větší než pseudomedián, přeskakuju je\n",
    "        while A[j] > PM:\n",
    "            j = j - 1\n",
    "        \n",
    "        # Už nemám, co přeskakovat - stojím\n",
    "        # Pokud se mi indexy nepřekřížily, prohodám prvky a posunu se\n",
    "        if i <= j:\n",
    "            swap_elements(A, i, j)    ;print(f\"SWAP: {A[j]} <--> {A[i]}\")\n",
    "            i = i + 1\n",
    "            j = j - 1\n",
    "\n",
    "        # Pokud se indexy překřížily, končím\n",
    "        if not i <= j: # while(i <= j)\n",
    "            break\n",
    "            \n",
    "    print(\"** PARTITION RESULT **\")\n",
    "    print(f\"{origleft}...{j}: \", end=\"\"); print_part(A,origleft,j);\n",
    "    print(f\"{origright}...{i}: \", end=\"\"); print_part(A,i,origright); \n",
    "    print(f\"i={i}, j={j}\")\n",
    "    print(\"----------------------------\")\n",
    "            \n",
    "    return (i, j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 301,
   "id": "3973223b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "======= QUICKSORT (A, 0, 6) =======\n",
      "---- partition(A, 0, 6) ----\n",
      "[7, 4, 13, 1, 6, 9, 2]\n",
      "PM: 1\n",
      "SWAP: 7 <--> 1\n",
      "** PARTITION RESULT **\n",
      "0...0: [1]\n",
      "6...1: [4, 13, 7, 6, 9, 2]\n",
      "i=1, j=0\n",
      "----------------------------\n",
      "(i) 1 < 6 (right) --> CALLING QUICKSORT ON RIGHT (A, 0, 0)\n",
      "======= QUICKSORT (A, 1, 6) =======\n",
      "---- partition(A, 1, 6) ----\n",
      "[4, 13, 7, 6, 9, 2]\n",
      "PM: 7\n",
      "SWAP: 13 <--> 2\n",
      "SWAP: 7 <--> 6\n",
      "** PARTITION RESULT **\n",
      "1...3: [4, 2, 6]\n",
      "6...4: [7, 9, 13]\n",
      "i=4, j=3\n",
      "----------------------------\n",
      "(left) 1 < 3 (j) --> CALLING QUICKSORT ON LEFT (A, 1, 3)\n",
      "======= QUICKSORT (A, 1, 3) =======\n",
      "---- partition(A, 1, 3) ----\n",
      "[4, 2, 6]\n",
      "PM: 2\n",
      "SWAP: 4 <--> 2\n",
      "** PARTITION RESULT **\n",
      "1...1: [2]\n",
      "3...2: [4, 6]\n",
      "i=2, j=1\n",
      "----------------------------\n",
      "(i) 2 < 3 (right) --> CALLING QUICKSORT ON RIGHT (A, 1, 1)\n",
      "======= QUICKSORT (A, 2, 3) =======\n",
      "---- partition(A, 2, 3) ----\n",
      "[4, 6]\n",
      "PM: 4\n",
      "SWAP: 4 <--> 4\n",
      "** PARTITION RESULT **\n",
      "2...1: []\n",
      "3...3: [6]\n",
      "i=3, j=1\n",
      "----------------------------\n",
      "==== END OF QUICKSORT (A, 2, 3) ====\n",
      "==== END OF QUICKSORT (A, 1, 3) ====\n",
      "(i) 4 < 6 (right) --> CALLING QUICKSORT ON RIGHT (A, 1, 3)\n",
      "======= QUICKSORT (A, 4, 6) =======\n",
      "---- partition(A, 4, 6) ----\n",
      "[7, 9, 13]\n",
      "PM: 9\n",
      "SWAP: 9 <--> 9\n",
      "** PARTITION RESULT **\n",
      "4...4: [7]\n",
      "6...6: [13]\n",
      "i=6, j=4\n",
      "----------------------------\n",
      "==== END OF QUICKSORT (A, 4, 6) ====\n",
      "==== END OF QUICKSORT (A, 1, 6) ====\n",
      "==== END OF QUICKSORT (A, 0, 6) ====\n",
      "[1, 2, 4, 6, 7, 9, 13]\n"
     ]
    }
   ],
   "source": [
    "#A = [4, 7, 5, 1, 8, 15, 0, 5, 6]\n",
    "A = [7, 4, 13, 1, 6, 9, 2]\n",
    "#A = [5, 2, 0, 1, 6]\n",
    "\n",
    "def QuickSort (A, left, right):\n",
    "    print(f\"======= QUICKSORT (A, {left}, {right}) =======\")\n",
    "    \n",
    "    i, j = partition(A, left, right)\n",
    "    \n",
    "    if left < j:\n",
    "        print(f\"(left) {left} < {j} (j) --> CALLING QUICKSORT ON LEFT (A, {left}, {j})\")\n",
    "        QuickSort(A, left, j)\n",
    "    \n",
    "    if i < right:\n",
    "        print(f\"(i) {i} < {right} (right) --> CALLING QUICKSORT ON RIGHT (A, {left}, {j})\")\n",
    "        QuickSort(A, i, right)\n",
    "        \n",
    "    print(f\"==== END OF QUICKSORT (A, {left}, {right}) ====\")\n",
    "    \n",
    "def QS (A):\n",
    "    QuickSort (A, 0, len(A)-1)\n",
    "    \n",
    "QS(A)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38fa74c3",
   "metadata": {},
   "source": [
    "## Quicksort (2. varianta)\n",
    "\n",
    "* Hlavní rozdíl je ve funkci **Partition**.\n",
    "* Jako pseudomedián (pivot) je volen **nejpravější prvek**.\n",
    "* Pole procházíme **pouze zleva doprava**.\n",
    "* Postup:\n",
    "  * Tvoříme [část<PM|část>PM ... PM]\n",
    "  * Index **i** ukazuje na poslední zpracovaný prvek < PM.\n",
    "  * Index **j** ukazuje na 1. dosud nezpracovaný prvek\n",
    "  * Posouvám **j**, pokud narazím na prvek < PM a v části > PM už něco mám, tak ho **prohodím s nejlevějším prvkem > PM**.\n",
    "  * Nakonec PM prohodíme s nejlevějším prvkem > PM.\n",
    "  * Dostaneme [část<PM|PM|část>PM].\n",
    "* Partition vrací **index nové pozice pivota**.\n",
    "* Rekurzivní volání pokračují vlevo a vpravo od tohoto prvrku.\n",
    "* Metoda je **oblíbená** - zdánlivě jednodušší, protože nemusím posouvat indexy ze dvou stran.\n",
    "* Je ale **méně efektivní** - musím provádět více výměn, zejména:\n",
    "  * V poli, kde je více prvků se stejným klíčem\n",
    "  * V poli, kde jsou už seřazené prvky\n",
    "* Druhý rozdíl je ve funkci **QuickSortII**, kdy máme jen 1 podmínku: **left < right**, která vede na situace, kdy by QuickSort vůbec nebylo nutné rekurzivně volat. On se ale zavolá a hned skončí :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "id": "f65e6ec9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def partitionII (A, left, right):\n",
    "    i = left - 1\n",
    "    PM = A[right]\n",
    "    \n",
    "    for j in irange(left, right-1):\n",
    "        if A[j] <= PM:\n",
    "            i = i+1\n",
    "            swap_elements(A, i, j)\n",
    "            \n",
    "    swap_elements(A, i+1, right)\n",
    "    return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "id": "678615f3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "A = [4, 2, 6, 1, 5]\n",
    "\n",
    "def QuickSortII (A, left, right):\n",
    "    if left < right:\n",
    "        q = partitionII (A, left, right)\n",
    "        QuickSortII(A, left, q-1)\n",
    "        QuickSortII(A, q+1, right)\n",
    "        \n",
    "def QSII (A):\n",
    "    QuickSortII (A, 0, len(A)-1)\n",
    "    \n",
    "QSII(A)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "682d5914",
   "metadata": {},
   "source": [
    "## Nerekurzivní Quicksort\n",
    "\n",
    "* Využívá **zásobník**\n",
    "* Dva segmenty v zásobníku -> jeden se dělí rovnou, hranice druhého se uloží do zásobníku\n",
    "* Zde: levou část dělím rovnou, pravé části odkládám do zásobníku.\n",
    "* Využívá  **2 cykly**:\n",
    "  * **Vnitřní** - provádí opakované dělení segmentu pole a uchovávání hraničních bodů druhého segmentu v zásobníku. Cyklus se **ukončí, až není co dělit** a opakuje se vnější cyklus.\n",
    "  * **Vnější** - vyzvedne ze zásobníku hraniční body dalšího segmentu a vstoupí do vnitřního cyklu. Vnější cyklus se **ukončí, když je zásobník prázdný a není žádný další segment k dělení.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 299,
   "id": "268b8447",
   "metadata": {},
   "outputs": [],
   "source": [
    "def NonRecQuicksort(A, left, right):\n",
    "    s = []           # InitStack(s)\n",
    "    Push(s, left)\n",
    "    Push(s, right)\n",
    "    \n",
    "    while not IsEmpty(s):\n",
    "        print(\"====== STACK: \", end=\"\"); print(s, end=\"\"); print(\"======\")\n",
    "        right = Top(s)\n",
    "        Pop(s)\n",
    "        left = Top(s)\n",
    "        Pop(s)\n",
    "    \n",
    "        while left < right:\n",
    "            i, j = partition(A, left, right)\n",
    "            Push(s, i)\n",
    "            Push(s, right)\n",
    "            right = j\n",
    "    \n",
    "def NRQS(A):\n",
    "    NonRecQuicksort(A, 0, len(A)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 300,
   "id": "aa8c5871",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "====== STACK: [0, 4]======\n",
      "---- partition(A, 0, 4) ----\n",
      "[5, 2, 0, 1, 6]\n",
      "PM: 0\n",
      "SWAP: 5 <--> 0\n",
      "** PARTITION RESULT **\n",
      "0...0: [0]\n",
      "4...1: [2, 5, 1, 6]\n",
      "i=1, j=0\n",
      "----------------------------\n",
      "====== STACK: [1, 4]======\n",
      "---- partition(A, 1, 4) ----\n",
      "[2, 5, 1, 6]\n",
      "PM: 5\n",
      "SWAP: 5 <--> 1\n",
      "** PARTITION RESULT **\n",
      "1...2: [2, 1]\n",
      "4...3: [5, 6]\n",
      "i=3, j=2\n",
      "----------------------------\n",
      "---- partition(A, 1, 2) ----\n",
      "[2, 1]\n",
      "PM: 2\n",
      "SWAP: 2 <--> 1\n",
      "** PARTITION RESULT **\n",
      "1...1: [1]\n",
      "2...2: [2]\n",
      "i=2, j=1\n",
      "----------------------------\n",
      "====== STACK: [3, 4, 2, 2]======\n",
      "====== STACK: [3, 4]======\n",
      "---- partition(A, 3, 4) ----\n",
      "[5, 6]\n",
      "PM: 5\n",
      "SWAP: 5 <--> 5\n",
      "** PARTITION RESULT **\n",
      "3...2: []\n",
      "4...4: [6]\n",
      "i=4, j=2\n",
      "----------------------------\n",
      "====== STACK: [4, 4]======\n",
      "[0, 1, 2, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "#A = [4, 7, 5, 1, 8, 15, 0, 5, 6]\n",
    "#A = [7, 4, 13, 1, 6, 9, 2]\n",
    "A = [5, 2, 0, 1, 6]\n",
    "\n",
    "NRQS(A)\n",
    "\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa67b941",
   "metadata": {},
   "source": [
    "### Quick sort - zhodnocení\n",
    "\n",
    "* Patří **mezi nejrychlejší** algorithmy pro řazení polí\n",
    "* Je **nestabilní** a **nepracuje přirozeně**.\n",
    "* Pro **vhodně zvolený pseudomedián** je **linearitmická** O(n*log(n))\n",
    "  * Když budeme mít smůlu - a při každém volání **Partition** bude PM minimum nebo maximum, pak bude degradovat na kvadratickou (n^2).\n",
    "  * Zlepšení výběru: Výběr tří náhodných hodnot + výběr prostřední z nich.\n",
    "* **Standardní implementace nepracuje in situ** - potřebuje pomocnou paměť O(log n), ačkoli **existují** i varianty in situ, např. QUICKSORT WITHOUT STACK (Branislav Ďurian: VÚVT) - ale je to výměnou za cenu nižší výkon.\n",
    "\n",
    "* Paralelní varianty\n",
    "  * **Parallel Quicksort** (klasický)\n",
    "    * P procesů - každý má index (**i**)\n",
    "    * Distribuovaná paměť - každý proces má segment neseřazené posloupnosti (ideálně stejně velký)\n",
    "    * Pivot se vezme náhodně od 1 z procesů a broatcastem se pošle ostatním.\n",
    "    * Každý proces rozdělí segmenty část s na prvky <= pivot a část s prvky > pivot.\n",
    "    * Následně pošle spodní část partnerovi s nižším **i** a obdrží spodní část od partnera s vyšším **i**.\n",
    "    * Horní polovina procesů má nyní hodnoty > pivot.\n",
    "    * Procesy se rozdělí do 2 skupin a rekurzivně se pokračuje.\n",
    "    * Po log(P) rekurzí má každý proces neseřazenou posloupnost hodnot kompletně disjunktní od ostatních procesů. Zároveň **nejvyšší hodnota** procesu **i** bude **menší** než **nejnižší hodnota** procesu **i+1**.\n",
    "    * Každý proces už jen seřadí svou posloupnost pomocí sekvenčního Quicksortu.\n",
    "  * Hyperquicksort\n",
    "    * Paralell Quicksort na hyperkostce\n",
    "    * Efektivnější než klasický Parallel Quicksort\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4d4f23d",
   "metadata": {},
   "source": [
    "## Shell sort\n",
    "\n",
    "* Princip **rozdělování** (stejně jako Quicksort)\n",
    "* Snižující se přírůstek.\n",
    "* Využívá **opakované průchody polem**, ve kterých řadí vždy jen určitou **posloupnost** původní sekvence:\n",
    "  * Pole rozdělíme na několik podposloupností, do kterých vybereme **prvky vzdálené od sebe o určitý krok**.\n",
    "  * Prvky v každé podsekvenci jsou uspořádány jedním bublinovým průchodem, konkrétně **Bubble-insert sort**.\n",
    "    * Bublinkový průchod provádí zavedení prvku z indexu **j+step** na jeho místo v dané posloupnosti - tj. **porovnává** jeho hodnotu **s hodnotou prvků na indexech snížených o krok (step)**.\n",
    "    * Se zaváděním prvku končí, je-li hodnota prvku na sníženém indexu **menší** než hodnota zaváděného prvku.\n",
    "  * Po **seřazení všech podposloupností** se **krok zmenší** a řazení se opakuje pro nové podsekvence.\n",
    "  * V poslední etapě řazení je **krok == 1**, všechny prvky jsou v **jedné posloupnosti**, a řazení je dokončeno posledním bublinovým průchodem.\n",
    "* Implementace níže má počáteční krok délky **MAX / 2**, přičemž s každou další iterací se **zmenšuje na polovinu**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 305,
   "id": "8c451fc3",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 4, 0, 2, 8, 7, 1, 9, 6]\n",
      "========== STEP 4 ===========\n",
      "[5, 4, 0, 2, 8, 7, 1, 9, 6]\n",
      "---- FOR (i=4, j=0) ----\n",
      "---- FOR (i=5, j=1) ----\n",
      "---- FOR (i=6, j=2) ----\n",
      "---- FOR (i=7, j=3) ----\n",
      "---- FOR (i=8, j=4) ----\n",
      "SWAP 8 <--> 6\n",
      "j = 4 - 4 = 0\n",
      "[5, 4, 0, 2, 6, 7, 1, 9, 8]\n",
      "========== STEP 2 ===========\n",
      "[5, 4, 0, 2, 6, 7, 1, 9, 8]\n",
      "---- FOR (i=2, j=0) ----\n",
      "SWAP 5 <--> 0\n",
      "j = 0 - 2 = -2\n",
      "[0, 4, 5, 2, 6, 7, 1, 9, 8]\n",
      "---- FOR (i=3, j=1) ----\n",
      "SWAP 4 <--> 2\n",
      "j = 1 - 2 = -1\n",
      "[0, 2, 5, 4, 6, 7, 1, 9, 8]\n",
      "---- FOR (i=4, j=2) ----\n",
      "---- FOR (i=5, j=3) ----\n",
      "---- FOR (i=6, j=4) ----\n",
      "SWAP 6 <--> 1\n",
      "j = 4 - 2 = 2\n",
      "[0, 2, 5, 4, 1, 7, 6, 9, 8]\n",
      "SWAP 5 <--> 1\n",
      "j = 2 - 2 = 0\n",
      "[0, 2, 1, 4, 5, 7, 6, 9, 8]\n",
      "---- FOR (i=7, j=5) ----\n",
      "---- FOR (i=8, j=6) ----\n",
      "========== STEP 1 ===========\n",
      "[0, 2, 1, 4, 5, 7, 6, 9, 8]\n",
      "---- FOR (i=1, j=0) ----\n",
      "---- FOR (i=2, j=1) ----\n",
      "SWAP 2 <--> 1\n",
      "j = 1 - 1 = 0\n",
      "[0, 1, 2, 4, 5, 7, 6, 9, 8]\n",
      "---- FOR (i=3, j=2) ----\n",
      "---- FOR (i=4, j=3) ----\n",
      "---- FOR (i=5, j=4) ----\n",
      "---- FOR (i=6, j=5) ----\n",
      "SWAP 7 <--> 6\n",
      "j = 5 - 1 = 4\n",
      "[0, 1, 2, 4, 5, 6, 7, 9, 8]\n",
      "---- FOR (i=7, j=6) ----\n",
      "---- FOR (i=8, j=7) ----\n",
      "SWAP 9 <--> 8\n",
      "j = 7 - 1 = 6\n",
      "[0, 1, 2, 4, 5, 6, 7, 8, 9]\n",
      "[0, 1, 2, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "A = [20, 12, 65, 8, 10, 16, 43, 35, 23, 88, 2, 56, 41, 27, 67, 56]\n",
    "A = [5, 4, 0, 2, 8, 7, 1, 9, 6]\n",
    "\n",
    "print(A)\n",
    "\n",
    "def ShellSort (A):\n",
    "    MAX = len(A)\n",
    "    step = int(MAX / 2)\n",
    "    while step > 0:\n",
    "\n",
    "        print(f\"========== STEP {step} ===========\"); print(A)\n",
    "\n",
    "        for i in irange(step, MAX-1):\n",
    "            j = i - step                                   ;print(f\"---- FOR (i={i}, j={j}) ----\");\n",
    "\n",
    "            while (j >= 0) and (A[j] > A[j+step]):\n",
    "                swap_elements(A, j, j+step)                ;print(f\"SWAP {A[j+step]} <--> {A[j]}\\nj = {j} - {step} = {j-step}\");\n",
    "                j = j - step                               ;print(A)\n",
    "\n",
    "        step = int(step / 2)\n",
    "\n",
    "ShellSort(A)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 245,
   "id": "a7d05b34",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "========== STEP 8 ===========\n",
      "[1, 9, 11, 24, 13, 0, 7, 6, 85, 4, 90, 1, 8, 29, 23, 30, 40]\n",
      "---- FOR (i=8, j=0) ----\n",
      "---- FOR (i=9, j=1) ----\n",
      "SWAP 9 <--> 4\n",
      "j = 1 - 8 = -7\n",
      "[1, 4, 11, 24, 13, 0, 7, 6, 85, 9, 90, 1, 8, 29, 23, 30, 40]\n",
      "---- FOR (i=10, j=2) ----\n",
      "---- FOR (i=11, j=3) ----\n",
      "SWAP 24 <--> 1\n",
      "j = 3 - 8 = -5\n",
      "[1, 4, 11, 1, 13, 0, 7, 6, 85, 9, 90, 24, 8, 29, 23, 30, 40]\n",
      "---- FOR (i=12, j=4) ----\n",
      "SWAP 13 <--> 8\n",
      "j = 4 - 8 = -4\n",
      "[1, 4, 11, 1, 8, 0, 7, 6, 85, 9, 90, 24, 13, 29, 23, 30, 40]\n",
      "---- FOR (i=13, j=5) ----\n",
      "---- FOR (i=14, j=6) ----\n",
      "---- FOR (i=15, j=7) ----\n",
      "---- FOR (i=16, j=8) ----\n",
      "SWAP 85 <--> 40\n",
      "j = 8 - 8 = 0\n",
      "[1, 4, 11, 1, 8, 0, 7, 6, 40, 9, 90, 24, 13, 29, 23, 30, 85]\n",
      "========== STEP 4 ===========\n",
      "[1, 4, 11, 1, 8, 0, 7, 6, 40, 9, 90, 24, 13, 29, 23, 30, 85]\n",
      "---- FOR (i=4, j=0) ----\n",
      "---- FOR (i=5, j=1) ----\n",
      "SWAP 4 <--> 0\n",
      "j = 1 - 4 = -3\n",
      "[1, 0, 11, 1, 8, 4, 7, 6, 40, 9, 90, 24, 13, 29, 23, 30, 85]\n",
      "---- FOR (i=6, j=2) ----\n",
      "SWAP 11 <--> 7\n",
      "j = 2 - 4 = -2\n",
      "[1, 0, 7, 1, 8, 4, 11, 6, 40, 9, 90, 24, 13, 29, 23, 30, 85]\n",
      "---- FOR (i=7, j=3) ----\n",
      "---- FOR (i=8, j=4) ----\n",
      "---- FOR (i=9, j=5) ----\n",
      "---- FOR (i=10, j=6) ----\n",
      "---- FOR (i=11, j=7) ----\n",
      "---- FOR (i=12, j=8) ----\n",
      "SWAP 40 <--> 13\n",
      "j = 8 - 4 = 4\n",
      "[1, 0, 7, 1, 8, 4, 11, 6, 13, 9, 90, 24, 40, 29, 23, 30, 85]\n",
      "---- FOR (i=13, j=9) ----\n",
      "---- FOR (i=14, j=10) ----\n",
      "SWAP 90 <--> 23\n",
      "j = 10 - 4 = 6\n",
      "[1, 0, 7, 1, 8, 4, 11, 6, 13, 9, 23, 24, 40, 29, 90, 30, 85]\n",
      "---- FOR (i=15, j=11) ----\n",
      "---- FOR (i=16, j=12) ----\n",
      "========== STEP 2 ===========\n",
      "[1, 0, 7, 1, 8, 4, 11, 6, 13, 9, 23, 24, 40, 29, 90, 30, 85]\n",
      "---- FOR (i=2, j=0) ----\n",
      "---- FOR (i=3, j=1) ----\n",
      "---- FOR (i=4, j=2) ----\n",
      "---- FOR (i=5, j=3) ----\n",
      "---- FOR (i=6, j=4) ----\n",
      "---- FOR (i=7, j=5) ----\n",
      "---- FOR (i=8, j=6) ----\n",
      "---- FOR (i=9, j=7) ----\n",
      "---- FOR (i=10, j=8) ----\n",
      "---- FOR (i=11, j=9) ----\n",
      "---- FOR (i=12, j=10) ----\n",
      "---- FOR (i=13, j=11) ----\n",
      "---- FOR (i=14, j=12) ----\n",
      "---- FOR (i=15, j=13) ----\n",
      "---- FOR (i=16, j=14) ----\n",
      "SWAP 90 <--> 85\n",
      "j = 14 - 2 = 12\n",
      "[1, 0, 7, 1, 8, 4, 11, 6, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "========== STEP 1 ===========\n",
      "[1, 0, 7, 1, 8, 4, 11, 6, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "---- FOR (i=1, j=0) ----\n",
      "SWAP 1 <--> 0\n",
      "j = 0 - 1 = -1\n",
      "[0, 1, 7, 1, 8, 4, 11, 6, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "---- FOR (i=2, j=1) ----\n",
      "---- FOR (i=3, j=2) ----\n",
      "SWAP 7 <--> 1\n",
      "j = 2 - 1 = 1\n",
      "[0, 1, 1, 7, 8, 4, 11, 6, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "---- FOR (i=4, j=3) ----\n",
      "---- FOR (i=5, j=4) ----\n",
      "SWAP 8 <--> 4\n",
      "j = 4 - 1 = 3\n",
      "[0, 1, 1, 7, 4, 8, 11, 6, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "SWAP 7 <--> 4\n",
      "j = 3 - 1 = 2\n",
      "[0, 1, 1, 4, 7, 8, 11, 6, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "---- FOR (i=6, j=5) ----\n",
      "---- FOR (i=7, j=6) ----\n",
      "SWAP 11 <--> 6\n",
      "j = 6 - 1 = 5\n",
      "[0, 1, 1, 4, 7, 8, 6, 11, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "SWAP 8 <--> 6\n",
      "j = 5 - 1 = 4\n",
      "[0, 1, 1, 4, 7, 6, 8, 11, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "SWAP 7 <--> 6\n",
      "j = 4 - 1 = 3\n",
      "[0, 1, 1, 4, 6, 7, 8, 11, 13, 9, 23, 24, 40, 29, 85, 30, 90]\n",
      "---- FOR (i=8, j=7) ----\n",
      "---- FOR (i=9, j=8) ----\n",
      "SWAP 13 <--> 9\n",
      "j = 8 - 1 = 7\n",
      "[0, 1, 1, 4, 6, 7, 8, 11, 9, 13, 23, 24, 40, 29, 85, 30, 90]\n",
      "SWAP 11 <--> 9\n",
      "j = 7 - 1 = 6\n",
      "[0, 1, 1, 4, 6, 7, 8, 9, 11, 13, 23, 24, 40, 29, 85, 30, 90]\n",
      "---- FOR (i=10, j=9) ----\n",
      "---- FOR (i=11, j=10) ----\n",
      "---- FOR (i=12, j=11) ----\n",
      "---- FOR (i=13, j=12) ----\n",
      "SWAP 40 <--> 29\n",
      "j = 12 - 1 = 11\n",
      "[0, 1, 1, 4, 6, 7, 8, 9, 11, 13, 23, 24, 29, 40, 85, 30, 90]\n",
      "---- FOR (i=14, j=13) ----\n",
      "---- FOR (i=15, j=14) ----\n",
      "SWAP 85 <--> 30\n",
      "j = 14 - 1 = 13\n",
      "[0, 1, 1, 4, 6, 7, 8, 9, 11, 13, 23, 24, 29, 40, 30, 85, 90]\n",
      "SWAP 40 <--> 30\n",
      "j = 13 - 1 = 12\n",
      "[0, 1, 1, 4, 6, 7, 8, 9, 11, 13, 23, 24, 29, 30, 40, 85, 90]\n",
      "---- FOR (i=16, j=15) ----\n",
      "[0, 1, 1, 4, 6, 7, 8, 9, 11, 13, 23, 24, 29, 30, 40, 85, 90]\n"
     ]
    }
   ],
   "source": [
    "A = [1, 9, 11, 24, 13, 0, 7, 6, 85, 4, 90, 1, 8, 29, 23, 30, 40]\n",
    "#    +---------------------------+----------------------------+   (STEP 8)\n",
    "#       +---------------------------+\n",
    "#           +---------------------------+\n",
    "#               +--------------------------+\n",
    "#                   +-------------------------+\n",
    "#                      +--------------------------+\n",
    "#                         +---------------------------+\n",
    "#                            +----------------------------+\n",
    "#                                +----------------------------+\n",
    "#\n",
    "#   [1, 4, 11, 1, 8, 0, 7, 6, 40, 9, 90, 24, 13, 29, 23, 30, 85]\n",
    "#    +--------------+------------+------------+---------------+   (STEP 4)\n",
    "#       +--------------+------------+-------------+\n",
    "#           +-------------+-------------+-------------+\n",
    "#               +------------+-------------+--------------+\n",
    "#                   +------------+------------+---------------+\n",
    "#\n",
    "#   [1, 0, 7, 1, 8, 4, 11, 6, 13, 9, 23, 24, 40, 29, 90, 30, 85]   (STEP 2)\n",
    "#    +------+-------+-----+------+------+-----+-------+-------+\n",
    "#       +-------+------+-----+------+------+------+-------+\n",
    "#\n",
    "#   [1, 0, 7, 1, 8, 4, 11, 6, 13, 9, 23, 24, 40, 29, 85, 30, 90]   (STEP 1)\n",
    "#    +--+---+---+---+--+--+--+---+--+---+--+--+---+---+---+---+\n",
    "#\n",
    "#   [0, 1, 1, 4, 6, 7, 8, 9, 11, 13, 23, 24, 29, 30, 40, 85, 90]   (DONE)\n",
    "ShellSort(A)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 246,
   "id": "59a7cf5f",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "========== STEP 4 ===========\n",
      "[9, 2, 0, 7, 5, 3, 4, 8]\n",
      "---- FOR (i=4, j=0) ----\n",
      "SWAP 9 <--> 5\n",
      "j = 0 - 4 = -4\n",
      "[5, 2, 0, 7, 9, 3, 4, 8]\n",
      "---- FOR (i=5, j=1) ----\n",
      "---- FOR (i=6, j=2) ----\n",
      "---- FOR (i=7, j=3) ----\n",
      "========== STEP 2 ===========\n",
      "[5, 2, 0, 7, 9, 3, 4, 8]\n",
      "---- FOR (i=2, j=0) ----\n",
      "SWAP 5 <--> 0\n",
      "j = 0 - 2 = -2\n",
      "[0, 2, 5, 7, 9, 3, 4, 8]\n",
      "---- FOR (i=3, j=1) ----\n",
      "---- FOR (i=4, j=2) ----\n",
      "---- FOR (i=5, j=3) ----\n",
      "SWAP 7 <--> 3\n",
      "j = 3 - 2 = 1\n",
      "[0, 2, 5, 3, 9, 7, 4, 8]\n",
      "---- FOR (i=6, j=4) ----\n",
      "SWAP 9 <--> 4\n",
      "j = 4 - 2 = 2\n",
      "[0, 2, 5, 3, 4, 7, 9, 8]\n",
      "SWAP 5 <--> 4\n",
      "j = 2 - 2 = 0\n",
      "[0, 2, 4, 3, 5, 7, 9, 8]\n",
      "---- FOR (i=7, j=5) ----\n",
      "========== STEP 1 ===========\n",
      "[0, 2, 4, 3, 5, 7, 9, 8]\n",
      "---- FOR (i=1, j=0) ----\n",
      "---- FOR (i=2, j=1) ----\n",
      "---- FOR (i=3, j=2) ----\n",
      "SWAP 4 <--> 3\n",
      "j = 2 - 1 = 1\n",
      "[0, 2, 3, 4, 5, 7, 9, 8]\n",
      "---- FOR (i=4, j=3) ----\n",
      "---- FOR (i=5, j=4) ----\n",
      "---- FOR (i=6, j=5) ----\n",
      "---- FOR (i=7, j=6) ----\n",
      "SWAP 9 <--> 8\n",
      "j = 6 - 1 = 5\n",
      "[0, 2, 3, 4, 5, 7, 8, 9]\n",
      "[0, 2, 3, 4, 5, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "A = [9, 2, 0, 7, 5, 3, 4, 8]\n",
    "#    +-----------+             (STEP 4)\n",
    "#       +-----------+\n",
    "#          +-----------+\n",
    "#             +-----------+\n",
    "#\n",
    "#   [5, 2, 0, 7, 9, 3, 4, 8]\n",
    "#    +-----+-----+-----+       (STEP 2)\n",
    "#       +-----+-----+-----+\n",
    "#\n",
    "#   [0, 2, 4, 3, 5, 7, 9, 8]\n",
    "#    +--+--+--+--+--+--+--+    (STEP 1)\n",
    "#\n",
    "#   [0, 2, 3, 4, 5, 7, 8, 9]\n",
    "\n",
    "ShellSort(A)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22b011c8",
   "metadata": {},
   "source": [
    "### Zhodnocení Shell sort\n",
    "\n",
    "* **Nestabilní** metoda\n",
    "* Chová se **přirozeně**\n",
    "* Pracuje **in situ**\n",
    "* Výhoda: **nepotřebuje rekurzi ani zásobník**.\n",
    "* Časová složitost **závisí na zvolené řadě kroků**:\n",
    "  * Pro uvedenou verzi (n/2, n/4, ..., 1) je v nejhorším případě n^2.\n",
    "  * Existují řady, kde je složitost n^(3/2) nebo n*log^2(n) == (n*log(n))^2\n",
    "* V uvedené modifikaci pracuje rychleji než Heap sort, ale pomaleji než Quick sort"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1adf5688",
   "metadata": {},
   "source": [
    "## Merge sort\n",
    "* Založen na **principu slučování** (merging), též **setřiďování**.\n",
    "* Princip:\n",
    "    * Pole rozdělujeme do tzv. **běhů** - souvislých úseků, kde jsou prvky **už seřazeny**.\n",
    "    * Na začátku budou všechny běhy 1-prvkové,\n",
    "    * Postupně spojujeme vždy **dva sousední běhy** do jediného setříděného.\n",
    "    * V poslední iteraci máme jediný běh s **kompletní seřazenou posloupností**.\n",
    "* Vyžaduje **pomocné pole** (nebo pomocná pole) pro uložení setříděné posloupnosti (nebo uložení vstupních posloupností).\n",
    "* **Rekurzivní varianta** - metoda postupně volá sebe same pro **levou** a **pravou** polovinu v zadané části pole. Při návratu z rekurze spojuje již seřazené posloupnosti.\n",
    "\n",
    "* Funkce **Merge**\n",
    "    * Na začátku si obě posloupnosti překopíruje do pomocných polí **L** a **R**.\n",
    "    * Postupně zpracovává prvky L a R zleva a porovnává je. Menší z nich je vždy uložen do výstupní posloupnosti (a je inkrementován příslušný index)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "id": "ec4f198f",
   "metadata": {},
   "outputs": [],
   "source": [
    "MaxInt = 99999\n",
    "\n",
    "def Merge (A, left, mid, right):\n",
    "    left_count = mid - left + 1\n",
    "    right_count = right - mid\n",
    "    L = []\n",
    "    R = []\n",
    "    \n",
    "    for i in irange(0, left_count-1):\n",
    "        L.append(A[left+i])              #L[i] = A[left+i]\n",
    "        \n",
    "    for j in irange(0, right_count-1):\n",
    "        R.append(A[mid+1+j])              #R[j] = A[mid+1+j]\n",
    "        \n",
    "    L.append(MaxInt)                     #L[left_count] = MaxInt\n",
    "    R.append(MaxInt)                     #R[right_count] = MaxInt\n",
    "    \n",
    "    i = 0\n",
    "    j = 0\n",
    "    \n",
    "    for k in irange(left, right):\n",
    "        if L[i] <= R[j]:\n",
    "            A[k] = L[i]\n",
    "            i = i + 1\n",
    "        else:\n",
    "            A[k] = R[j]\n",
    "            j = j + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 267,
   "id": "c891838c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def MergeSort (A, left, right):\n",
    "    if (left < right):\n",
    "        q = int((left + right) / 2)\n",
    "        MergeSort(A, left, q)\n",
    "        MergeSort(A, q+1, right)\n",
    "        Merge(A, left, q, right)\n",
    "    \n",
    "def MS (A):\n",
    "    MergeSort(A, 0, len(A)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 268,
   "id": "b8c1ff6c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 4, 5, 7, 8, 11]\n"
     ]
    }
   ],
   "source": [
    "A = [4, 5, 1, 3, 11, 8, 7, 0]\n",
    "MS(A)\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3846dbc",
   "metadata": {},
   "source": [
    "### Zhodnocení Merge sort\n",
    "\n",
    "* **Stabilní** metoda\n",
    "* Chová se **přirozeně**\n",
    "* **Nepracuje in situ** - potřebuje **pomocné pole!** (dodatečná paměť O(n)))\n",
    "* **Linearitmická** složitost: n*log(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "789ff7da",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}