Napredno urejanje.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3593095b-bd9e-4a31-bb04-0a532e38f2cc",
   "metadata": {},
   "source": [
    "# Napredno urejanje\n",
    "\n",
    "Kot smo videli do sedaj, so imeli vsi \"naravni\" algoritmi za urejanje kvadratno časovno zahtevnost. To pomeni, da imamo resno težavo že, če bi želeli urediti dva milijona prebivalcev Slovenije. Izkaže pa se, da lahko problem urejanja rešimo veliko bolj učinkovito."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f03feb4b-8cd3-4c49-9b40-2bfe306e645e",
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <vector>\n",
    "#include <iostream>\n",
    "#include <algorithm>\n",
    "#include <random>\n",
    "using namespace std;\n",
    "\n",
    "typedef vector<int> VectorInt;\n",
    "typedef array<VectorInt,3> VectorInt3;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3ed607c-6868-4f6f-9ba1-3a144c79d6b4",
   "metadata": {},
   "source": [
    "Ker imajo zapiski težave s kompleksnejšimi tipi, bomo uporabljali `VectorInt` kot drugo ime za `vector<int>`. Prav nam bo prišlo pa še nekaj pomožnih funkcij. \n",
    "\n",
    "Na tem mestu lahko demonstriramo še enostavno uporabo predlog (*template*) v C++. Funkcija `print` bi izgledala skoraj enako, če imamo opravka s seznamom celih števil, decimalnih števil ali pa nizov, razlika bi bila samo v tipu. S spodnjo sintakso povemo prevajalniku, naj naredi kopije funkcije in sicer po potrebi za vse tipe, ki bodo kdaj uporabljali to funkcijo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b035bc52-27a4-4135-a0e2-dfb755383018",
   "metadata": {},
   "outputs": [],
   "source": [
    "template<typename T>\n",
    "void print(const vector<T> &s) {\n",
    "    for (T x : s) cout << x << \" \";\n",
    "    cout << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4b48137e-9007-41ba-907e-4e699bf36759",
   "metadata": {},
   "outputs": [],
   "source": [
    "VectorInt concat(VectorInt a, VectorInt b) {\n",
    "    a.reserve(a.size()+b.size());\n",
    "    a.insert(a.end(), b.begin(), b.end());\n",
    "    return a;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5a6f275b-9113-4772-8918-cc6cb59bd2db",
   "metadata": {},
   "outputs": [],
   "source": [
    "VectorInt random_numbers(int n, int x=1000000) {\n",
    "    default_random_engine rnd(123);\n",
    "    VectorInt v;\n",
    "    for (int i=0;i<n;i++) v.push_back(rnd()%x);\n",
    "    return v;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52d73d33-a375-4642-b1e6-32dc10ae1464",
   "metadata": {},
   "source": [
    "## Napredni urejevalni algoritmi\n",
    "\n",
    "Še vedno se bomo ukvarjali z algoritmi, ki temeljijo na medsebojnih primerjavah elementov. Ogledali si bomo primere algoritmov, ki dosežejo časovno zahtevnost $O(n \\log n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "757b4b5c-91d7-40c0-a218-4637de877183",
   "metadata": {},
   "source": [
    "### Urejanje z zlivanjem (*mergesort*)\n",
    "\n",
    "Ta algoritem razdeli elemente seznama na prvo in drugo polovico. Rekurzivno uredi vsako polovico na enak način, nato pa združi dva urejena seznama (iz prve in druge polovice) v skupen urejen seznam.\n",
    "\n",
    "Najprej si oglejmo, kako bi združili dva urejena seznama v enega samega. Na vsakem koraku preverimo najmanjša (prva) elementa v obeh seznamih in v združen seznam dodamo manjšega od njiju ter ga odstranimo iz seznama."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "57e1ba2b-25a5-4094-a7a6-d3b090fb7d48",
   "metadata": {},
   "outputs": [],
   "source": [
    "VectorInt merge(VectorInt a, VectorInt b) {\n",
    "    int i=0, j=0;\n",
    "    VectorInt c;\n",
    "    while (i<a.size() || j<b.size()) {\n",
    "        if (i<a.size() && j<b.size()) {\n",
    "            if (a[i]<=b[j]) c.push_back(a[i++]);\n",
    "            else c.push_back(b[j++]);\n",
    "        } else if (i<a.size()) c.push_back(a[i++]);\n",
    "        else c.push_back(b[j++]);\n",
    "    }\n",
    "    return c;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e1f96c9-6b04-43c8-9f49-29cf036a590f",
   "metadata": {},
   "source": [
    "Zlivanje seznamov je sicer poučno, vendar je dovolj pogosto, da je našlo svoje mesto tudi kot funkcija `merge` v knjižnici `algorithms`.\n",
    "\n",
    "Algoritem je od tu naprej precej enostaven. Seznam razdelimo na pol, rekurzivno uredimo vsako polovico in združimo rezultata."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "dd63d27c-a39e-49a8-bc28-307558545c1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "VectorInt mergesort(VectorInt sez) {\n",
    "    int n=sez.size();\n",
    "    if (n<=1) return sez;\n",
    "    VectorInt levo(sez.begin(), sez.begin()+n/2);\n",
    "    VectorInt desno(sez.begin()+n/2, sez.end());\n",
    "    levo = mergesort(levo);\n",
    "    desno = mergesort(desno);\n",
    "    return merge(levo, desno);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "69097112-4ed4-4980-b444-c16fbbd0aa31",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 \n"
     ]
    }
   ],
   "source": [
    "vector<int> sez = {5,3,4,6,2,7,1};\n",
    "sez = mergesort(sez);\n",
    "print(sez);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d0ea5c2a-a37d-421b-92e3-94fe3c11d24d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "urejeno\n"
     ]
    }
   ],
   "source": [
    "vector<int> sez = random_numbers(1000000);\n",
    "sez = mergesort(sez);\n",
    "if (is_sorted(sez.begin(), sez.end())) cout << \"urejeno\" << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2421970e-dd3f-4595-8b61-003fd8fd2310",
   "metadata": {},
   "source": [
    "Ker seznam vsakič razdelimo na pol, bo globina rekurzije $O(\\log n)$. Na najglobljem nivoju se bodo združevali pari seznamov dolžine 1, en nivo višje pari seznamov dolžine 2, nato 4, itd. Za združevanjem bomo na posameznem nivoju potrebovali $O(n)$ časa.\n",
    "\n",
    "Časovna zahtevnost (najslabša, povprečna, najboljša): $O(n \\log n)$, $O(n \\log n)$, $O(n \\log n)$.\n",
    "\n",
    "Prostorska zahtevnost je odvisna od implementacije. Zgornja ima prostorsko zahtevnost $O(n \\log n)$, ker na vsakem nivoju rekurzije obstaja ena kopija vsakega elementa. To lahko enostavno izboljšamo, če ne ustvarjamo novih seznamov (ampak uporabljamo indekse za določitev podseznamov), za vse korake zlivanja pa uporabimo isto pomožno tabelo velikosti $O(n)$. Omenimo, da je možno tudi urejanje z zlivanjem izvesti povsem na mestu brez dodatnega pomnilnika, vendar je to že bolj zakomplicirano."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d24649ec-40c2-4563-9d0d-032e68ef5d7d",
   "metadata": {},
   "source": [
    "### Hitro urejanje (*quicksort*)\n",
    "\n",
    "Algoritem hitrega urejanja se loti urejanja tako, da razdeli elemente seznama na majhne in velike. Majhni bodo na začetku seznama, veliki pa na koncu. Seznam majhnih in velikih pa lahko vsakega zase rekurzivno uredimo na enak način. S tem smo v posameznem koraku opravili samo manjši del urejanja: elemente smo razdelili na majhne in velike. Če to ponovimo rekurzivno, pa bomo na koncu uspešno uredili seznam.\n",
    "\n",
    "Kako naj razdelimo (*partition*) seznam na majhne in velike elemente? Idealno bi bilo, če bi jih lahko razbili na enako veliki skupini, vendar to izgleda kot ravno tako težek problem. Izbrali bomo enostavnejšo strategijo. Iz seznama, ki ga urejamo, si izberimo neko (naključno) število (*pivot*). Lahko je to kar prvi element. Elemente, ki so manjši, bomo razglasili za majhne, tiste, ki so večji, pa za velike. Imamo pa še tretjo skupino, in to so elementi, ki so enaki pivotu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b6822347-3198-4c01-8c2c-ddb317153ee1",
   "metadata": {},
   "outputs": [],
   "source": [
    "VectorInt3 partition(VectorInt sez) {\n",
    "    int pivot = sez[0];\n",
    "    VectorInt majhni, enaki, veliki;\n",
    "    for (int i=0; i<sez.size(); i++) {\n",
    "        if (sez[i]<pivot) majhni.push_back(sez[i]);\n",
    "        else if (sez[i]>pivot) veliki.push_back(sez[i]);\n",
    "        else enaki.push_back(sez[i]);\n",
    "    }\n",
    "    VectorInt3 p = {majhni, enaki, veliki};\n",
    "    return p;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "90d3dd39-be73-4e8b-ba12-12374702bf4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "VectorInt quicksort(VectorInt sez) {\n",
    "    if (sez.size()<=1) return sez;\n",
    "    auto [majhni, enaki, veliki] = partition(sez);\n",
    "    VectorInt urejeni_majhni = quicksort(majhni);\n",
    "    VectorInt urejeni_veliki = quicksort(veliki);\n",
    "    return concat(concat(urejeni_majhni, enaki), urejeni_veliki);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "203dc100-b1cd-4d9c-aac1-1367f27b98a4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 \n"
     ]
    }
   ],
   "source": [
    "vector<int> sez = {5,3,4,6,2,7,1};\n",
    "sez = quicksort(sez);\n",
    "print(sez);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5893516-8c73-4620-a23d-f2ccf26fed3f",
   "metadata": {},
   "source": [
    "Razmislimo, kako učinkovit je ta postopek? Recimo, da imamo srečo, in izbiramo elemente tako, da seznam vedno razpade na dve enako veliki skupini majhnih in velikih. V tem primeru bomo imeli $O(\\log n)$ nivojev rekurzije. Na vsakem nivoju pa se bomo ukvarjali z $O(n)$ elementi. Na prvem nivoju z eno skupino $n$ elementov, na drugem nivoju z dve skupinama velikosti $n/2$ itd. S posemezno skupino nimamo prav veliko dela, v enem prehodu jih razdelimo med manjše in večje. Skupaj bomo torej naredili $O(n \\log n)$ operacij."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "1e1f379c-221b-4dd5-99ab-80648f068364",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "urejeno\n"
     ]
    }
   ],
   "source": [
    "vector<int> sez = random_numbers(1000000);\n",
    "sez = quicksort(sez);\n",
    "if (is_sorted(sez.begin(), sez.end())) cout << \"urejeno\" << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "931c755a-ade5-49a7-8539-f8df86bf6b96",
   "metadata": {},
   "source": [
    "Izkaže se, da naša predpostavka, da bomo imeli vedno srečo pri izbiri delilnega elementa, ni tako slaba. Tudi pri naključnem izbiranju, bosta velikosti seznamov malih in velikih elementov v nekem smiselnem razmerju. Če bi bilo razmerje vedno npr. 1:2 (namesto 1:1), to še vedno vodi do enake časovne zahtevnosti. Tako je pričakovana (povprečna) časovna zahtevnost enaka tisti v najboljšem primeru.\n",
    "\n",
    "Časovna zahtevnost (najslabša, povprečna, najboljša): $O(n^2)$, $O(n \\log n)$, $O(n \\log n)$.\n",
    "\n",
    "Prostorska zahtevnost je odvisna od implementacije. Zgornja koda zaradi preglednosti porabi $O(n \\log n)$ prostora. Postopek pa lahko implementiramo tudi na mestu s prestavljanjem elementov znotraj seznama, kar zmanjša prostorsko zahtevnost na $O(n)$. V sledečem primeru bomo za pivot izbrali zadnji element, nato pa preuredili preostale tako, da bodo na začetku manjši elementi, njihovo število pa bomo hranili v spremenljivki $m$. Funkcija `quicksort2` uredi seznam med indeksoma $i$ in $j$, vključno z $i$-tim in brez $j$-tega."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "a877f65b-07c5-475d-9bf5-8fa04dd53d7a",
   "metadata": {},
   "outputs": [],
   "source": [
    "void quicksort2(VectorInt &sez, int i, int j) {\n",
    "    if (j-i<=1) return;\n",
    "    int m=0, pivot=sez[j-1];\n",
    "    for (int k=i;k<j;k++) {\n",
    "        if (sez[k]<pivot) {\n",
    "            swap(sez[i+m],sez[k]);\n",
    "            m++;\n",
    "        }\n",
    "    }\n",
    "    swap(sez[i+m], sez[j-1]);\n",
    "    quicksort2(sez, i, i+m);\n",
    "    quicksort2(sez, i+m+1, j);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "110fd408-ba44-4c98-af37-57bb5b55997e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 \n"
     ]
    }
   ],
   "source": [
    "vector<int> sez = {5,3,4,6,2,7,1};\n",
    "quicksort2(sez, 0, sez.size());\n",
    "print(sez);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7a621d0-a98b-44fc-8a73-bb1210aa3a07",
   "metadata": {},
   "source": [
    "Pozor: zgornja implementacija ima resno težavo v določenem primeru. Če so vsa števila enaka, bo namreč časovna zahtevnost $O(n^2)$. Kako bi lahko odpravili?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44f61f94-752b-41c9-adb3-e99b61b73e82",
   "metadata": {},
   "source": [
    "Če primerjamo algoritma *mergesort* in *quicksort*, prvi razdeli elemente na leve in desne in večino dela z zlivanjem naredi po zaključku rekurzivnega urejanja, drugi pa jih razdeli na majhne in velike, kar zahteva večino dela z razdelitvijo pred rekurzivnim urejanjem manjših delov."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdab8782-8e0b-45a2-95ad-e662ad38fce2",
   "metadata": {},
   "source": [
    "### Urejanje s kopico (*heapsort*)\n",
    "\n",
    "Urejanje s kopico je pravzaprav izboljšava navadnega urejanja z izbiranjem (*selection sort*). Namesto, da bi vsakič znova iskali najmanjši element med še neurejenimi, lahko ta korak pohitrimo. To dosežemo tako, da hranimo neurejene elemente v posebni podatkovni strukturi, ki nam omogoča učinkovito iskanje in odstranjevanje najmanjšega elementa v njej. Točno temu je namenjena kopica (*heap*). Več o tem kdaj drugič."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9dc7c75b-93fa-4a50-9e60-e5a999aa4a99",
   "metadata": {},
   "source": [
    "## Praksa\n",
    "\n",
    "Kateri algoritmi pa se uporabljajo v praksi, npr. v standardnih knjižnicah programskih jezikov, kot so C, C++, Java, Python, itd. Običajno gre za neke kombinacije pristopov, saj se različni algoritmi obnesejo različno dobro na manjših ali večjih primerih. \n",
    "\n",
    "- C ponuja funkcijo `qsort`, kjer je že iz imena očitno, da gre za quicksort. \n",
    "- C++ uporablja t.i. *introsort*, ki je pravzaprav quicksort v kombinaciji še z dvema drugima algoritmoma. Če med urejanjem velikost seznama pade pod neko mejo, se uporabi navaden insertion sort. Če rekurzija preseže neko vnaprej definirano globino, pa se od tam naprej uporabi heapsort.\n",
    "- Python uporablja *timsort*, ki je kombinacija mergesorta in insertion sorta.\n",
    "- Java uporablja različne pristope za urejanje primitivnih tipov in za urejanje drugih objektov. Za prve uporablja različico quicksorta, za druge pa različico timsorta."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "005f39e6-83eb-4a6a-af19-dc6481df0e59",
   "metadata": {},
   "source": [
    "## Urejanje brez primerjav\n",
    "\n",
    "Do sedaj smo urejali elemente v okviru zelo splošnih omejitev, ki nam omogočajo samo primerjave med pari elementov. Včasih pa lahko izkoristimo tudi kakšno drugo lastnost podatkov, ki jih urejamo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c15b56a-c631-4c8e-ad4a-df79fe9d1d52",
   "metadata": {},
   "source": [
    "### Urejanje s štetjem (*counting sort*)\n",
    "\n",
    "Recimo, da moramo uredi seznam števil, ki predstavljajo poštne številke. Ne glede na to, kako dolg bo seznam, je nabor različnih poštnih številk precej majhen. Tako lahko za vsako poštno številko preštejemo, kolikokrat se pojavi v seznamu, in jo na koncu temu primerno večkrat vnesemo v urejen seznam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "8808b581-23c3-41e1-8ff0-bd63fbdb6c58",
   "metadata": {},
   "outputs": [],
   "source": [
    "void counting_sort(VectorInt &sez) {\n",
    "    int m = *max_element(sez.begin(), sez.end());\n",
    "    VectorInt f(m+1);\n",
    "    for (int x : sez) f[x]++;\n",
    "    int i=0;\n",
    "    for (int x=0; x<=m; x++) {\n",
    "        for (int r=0;r<f[x];r++) sez[i++]=x;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "5b40abfe-f425-4f65-9963-4909281b8f78",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 1000 2000 2000 2000 4000 \n"
     ]
    }
   ],
   "source": [
    "vector<int> sez = {1000,2000,2000,4000,2000,1000};\n",
    "counting_sort(sez);\n",
    "print(sez);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "594fbdf1-f54d-43ce-9023-498014f383f6",
   "metadata": {},
   "source": [
    "Časovna zahtevnost je linearna, torej $O(n)$. Težava pa je v prostorski zahtevnosti, ki je odvisna od največjega elementa. Kaj pa, če vrednosti niso prikladno majhna cela števila? To težavo bomo rešili, ko se bomo pogovarjali o slovarjih."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7335758-c362-45fd-90d7-e27e387be0e2",
   "metadata": {},
   "source": [
    "### Urejanje s koši (*bucket/bin sort*)\n",
    "\n",
    "Urejanje s koši (ali vedri) je zelo splošna tehnika, iz katere izhaja veliko različnih algoritmov. Osnovna ideja algoritma je, da razdeli elemente seznama v koše glede na njihovo vrednost. Med koši obstaja urejenost od košev z manjšimi elementi proti tistim z večjimi. Pri tem se zanaša na enakomerno razporejenost elementov po koših. Vsak koš lahko nato uredimo s poljubnim urejevalnim algoritmom, ali pa rekurzivno uporabimo enak postopek razdeljevanja elementov znotraj koša.\n",
    "\n",
    "Na primer, če uporabljamo dva koša, kjer prvi vsebuje elemente z vrednostmi z območja $[\\text{min}, \\text{med}]$, drugi pa $[\\text{med}+1, \\text{max}]$ in uporabimo rekurzivno strategijo, dobimo nekaj podobnega algoritmu *quicksort*, kjer je kot pivot (namesto nekega elementa iz seznama) izbrana srednja vrednost $\\text{med} = (\\text{min}+\\text{max})/2$ med najmanjšo ($\\text{min}$) in največjo ($\\text{max}$) vrednostjo iz seznama."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fe2338f-3553-4637-b576-a91fa62be438",
   "metadata": {},
   "source": [
    "#### Korensko urejanje (*radix sort*)\n",
    "\n",
    "Kot primer urejanja s koši si oglejmo še korensko urejanje. V tem algoritmu razporejamo elemente v koše glede na števke v primeru števil ali črke v primeru nizov. Obstaja več različic, mi si bomo ogledali urejanje od bolj pomembnih proti manj pomembnim znakom (MSD - Most Significant Digit) in sicer na primeru urejanja nizov po abecedi.\n",
    "\n",
    "Nize lahko razdelimo v koše glede na njihovo prvo črko, nato pa posamezen koš uredimo po enakem postopku, le da nize sedaj delimo v koše glede na drugo črko itd. Ko so koši urejeni, rezultate enostavno zložimo skupaj. Vse kar potrebujemo je tabela košev `buckets`, ki bo na mestu `buckets[c]` hranila seznam nizov, ki imajo na trenutno relevantnem mestu črko `c`. Relevantno mesto bomo hranili v argumentu `r` in ga povečevali v rekurzivnih klicih. Dodatno pa hranimo še koš prekratkih besed (`done`), ki sploh nimajo `r`-te črke."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "46c4131e-5b4f-4ec2-9170-cd61d951a953",
   "metadata": {},
   "outputs": [],
   "source": [
    "void radix_sort(vector<string> &sez, int r=0) {\n",
    "    if (sez.size()<=1) return;\n",
    "    vector<string> buckets['z'-'a'+1], done;\n",
    "    for (string x : sez) {\n",
    "        if (r>=x.size()) {\n",
    "            done.push_back(x);\n",
    "        } else {\n",
    "            int b = x[r]-'a';\n",
    "            buckets[b].push_back(x);\n",
    "        }\n",
    "    }\n",
    "    int i=0;\n",
    "    for (string s : done) sez[i++] = s;\n",
    "    for (int b=0; b<='z'-'a'; b++) {\n",
    "        radix_sort(buckets[b], r+1);\n",
    "        for (string s : buckets[b]) sez[i++] = s;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0a3564d7-b6c5-4768-aa3a-e8459b615708",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a a aa aabab az ba bab z \n"
     ]
    }
   ],
   "source": [
    "vector<string> sez = {\"bab\",\"a\",\"a\",\"aabab\",\"aa\",\"ba\",\"z\",\"az\"};\n",
    "radix_sort(sez);\n",
    "print(sez);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d5b35dd-24f8-4ceb-8b02-b72764c7e6f1",
   "metadata": {},
   "source": [
    "Časovna zahtevnost zgornjega algoritma je $O(nd)$, če je $d$ največja dolžina niza. Enako velja za prostorsko zahtevnost, saj na vsakem izmed $d$ nivojev hranimo v koših vseh $n$ elementov. Upoštevati pa moramo tudi prazne koše, ki zasedajo prostor. Teh je lahko precej. Zato je boljša ocena prostorske zahtevnosti $O(nda)$, kjer je $a$ velikost abecede (če je konstantna, to lahko zanemarimo). V vsakem izmed $O(nd)$ klicev funkcije namreč alociramo $a$ košev."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbc67d0d-0401-4601-b93c-132941b8a094",
   "metadata": {},
   "source": [
    "## Dvojiško iskanje (*binary search*)\n",
    "\n",
    "Zakaj bi sploh želeli urejati sezname? Zato, da lahko v njih učinkovito iščemo stvari. To pa počnemo z dvojiškim iskanje (bisekcijo). Ko iščemo neko vrednost v urejenem seznamu, ju lahko primerjamo z nekim elementom in če je manjši, moramo iskati na levi strani, sicer pa na desni. Če vedno izberemo srednji element, bomo velikost seznama na vsakem koraku prepolovili in tako potrebovali $O(\\log n)$ korakov, da najdemo element oz. ugotovimo, da ga ni v urejenem seznamu."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "871e3504-306a-4db8-8517-62863865f333",
   "metadata": {},
   "source": [
    "Ideja je zavajujoče enostavna in pogosto vodi do nepravilnih rešitev. Oglejmo si eno tako."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6640cbd9-40af-4c3d-85ff-e6b3f5caa05d",
   "metadata": {},
   "outputs": [],
   "source": [
    "bool bisekcija_narobe(VectorInt sez, int x) {\n",
    "    // nastavimo levo in desno mejo\n",
    "    int levo=0, desno=sez.size()-1;\n",
    "    while (1) {\n",
    "        // primerjamo s srednjim elementom\n",
    "        int i = (levo+desno)/2;\n",
    "        // popravimo meje\n",
    "        if (x < sez[i]) levo = i-1;\n",
    "        else desno = i+1;\n",
    "        // ce smo nasli element, ali so se meje prekrizale, ustavimo iskanje\n",
    "        if (sez[i] == x || desno < levo) break;\n",
    "    }\n",
    "    // ce so meje smiselne, smo ga nasli, sicer ga ni\n",
    "    return levo <= desno;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "715b9a07-60fd-4906-890c-04dbb61af458",
   "metadata": {},
   "source": [
    "S to rešitvijo je narobe cel kup stvari:\n",
    "- Popravljanje mej bi moralo biti ravno obratno. Če je iskani element manjši od srednjega, moramo premakniti desno mejo in obratno.\n",
    "- Iskanje v praznem seznamu se sesuje, ker se vedno izvede vsaj ena iteracija iskanja.\n",
    "- Največjega elementa ne bomo nikoli našli, ker se takrat, ko ga najdemo, tudi prekrižajo meje. To pa je naše merilo, ali smo našli element ali ne.\n",
    "- Časovna zahtevnost ni $O(\\log n)$, ampak $O(n)$ zaradi kopiranja seznama, ko pokličemo funkcijo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d84f4666-b17b-449e-aadf-54b02544e390",
   "metadata": {},
   "outputs": [],
   "source": [
    "bool bisekcija(VectorInt &sez, int x) {\n",
    "    int levo=0, desno=(int)sez.size()-1;\n",
    "    while (levo<=desno) {\n",
    "        int i = (levo+desno)/2;\n",
    "        if (sez[i] == x) return true;\n",
    "        else if (x < sez[i]) desno = i-1;\n",
    "        else levo = i+1;\n",
    "    }\n",
    "    return false;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df020082-da2c-4de3-acd8-595306f3a8aa",
   "metadata": {},
   "source": [
    "Oglejmo si malo težjo različice naloge. V urejenem seznamu bomo iskali mesto, kamor bi morali vanj vstaviti nek nov element, da se bo ohranjala urejenost. Če obstaja več takih mest, ker imamo več enakih števil, ga želimo vstaviti na najmanjše mesto. Npr. v seznam `{2,3,7,7,8,10,10,10}` bi število `7` želeli vstaviti na indeks 2.\n",
    "\n",
    "Pri implementaciji bisekcije in tudi drugih algoritmov moramo biti bolj sistematični, da se izognemo napakam. To storimo tako, da v iteracijah vzdržujemo neke lastnosti, ki jim rečemo *invariante*. V našem primeru imamo v urejenem seznamu nekaj števil, ki so manjša, nato pa števila, ki so večja ali enaka `{<, <, >=, >=, >=, >=, >=, >=}`. Iščemo mejo med tema dvema območjema. Uporabljali bomo indeksa `lo`in `hi`, kjer bo prvi ves čas kazal na neko manjše, drugi pa na večje ali enako število. Za inicializacijo teh dveh kazalcev, si lahko predstavljamo, da imamo pred seznamom na indeksu -1 vrednost $-\\infty$, za njim pa $\\infty$. Nato ju bomo v več korakih bisekcije bližali in ko bosta sosednja, smo našli iskano mejo, ki je takrat shranjena v `hi`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "749444d5-a454-4964-b55a-c2fe0632b22a",
   "metadata": {},
   "outputs": [],
   "source": [
    "int lokacija(VectorInt &sez, int x) {\n",
    "    int lo=-1, hi=sez.size();\n",
    "    while (hi-lo>1) {\n",
    "        int i = (lo+hi)/2;\n",
    "        if (sez[i] < x) lo = i;\n",
    "        else hi = i;\n",
    "    }\n",
    "    return hi;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "3c9b97ae-31f5-44f7-932e-323c02d1f08f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "vector<int> sez = {2,3,7,7,8,10,10,10};\n",
    "cout << lokacija(sez, 7) << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afa2d45c-a0f2-4b65-8898-f0c90579b7b1",
   "metadata": {},
   "source": [
    "Sedaj, ko to znamo, povejmo še, da C++ to funkcionalnost že ponuja v knjižnici `algorithm` s funkcijo `lower_bound`, ki vrne iterator na iskano meso. Funkcija `upper_bound` pa bi med enakovrednimi mesti za vstavljanje vrnila največje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "45c7e9ea-8b20-46b1-abe5-6aadb5ec402b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "vector<int> sez = {2,3,7,7,8,10,10,10};\n",
    "cout << lower_bound(sez.begin(), sez.end(), 7) - sez.begin() << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e51d57ea-c1b6-4c12-8c82-718badc8975e",
   "metadata": {},
   "source": [
    "K dvojiškemu iskanju se bomo ponovno vrnili, ko se bomo pogovarjali o tehniki *deli in vladaj*."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}