{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ricerca lineare e ricerca binaria"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copiare qui l'algoritmo di riceca linare visto nella lezione precedente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linear_search(l, x):\n",
    "    \"\"\"\n",
    "    Restituisce la posizione di x in l se esiste, altrimenti restituisce -1.\n",
    "    \"\"\"\n",
    "    for i in range(len(l)):\n",
    "        if l[i] == x:\n",
    "            return i\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Questo è invece l'algoritmo di ricerca binaria."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(l, x):\n",
    "    \"\"\"\n",
    "    Restituisce la posizione di x in l se esiste, altrimenti restituisce -1.\n",
    "    La lista l deve essere ordinata.\n",
    "    \"\"\"\n",
    "    start = 0\n",
    "    end = len(l) - 1\n",
    "    while end >= start:\n",
    "        middle = (start + end) // 2\n",
    "        if l[middle] == x:\n",
    "            return middle\n",
    "        elif l[middle] < x:\n",
    "            start = middle + 1\n",
    "        else:\n",
    "            end = middle - 1\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Facciamo un paio di prove per vedere se la funzione `binary_search` funziona."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [2, 5, 10, 15, 23, 99]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binary_search(l, 23)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binary_search(l, 17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Carichiamo la lista words di circa 450.000 parole che abbiamo già usato nella lezione precedente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"words.txt\", \"r\") as f:\n",
    "    words = f.read().splitlines()\n",
    "words.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "466550"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Misuriamo il tempo di esecuzione della funzione `linear_search` su un valore che non esiste (che è il caso peggiore, perchè richiede di controllare tutti gli elementi della lista)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13.2 ms ± 289 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "linear_search(words, \"abcxyz\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Questo è invece il tempo di esecuzione della funzione `binary_search`. Attenzione che il risultato è in micro-secondi, mentre per `linear_search` era in milli-secondi. Dunque, la ricerca binaria, almeno in questa occasione, è più di 1000 volte più veloce."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.69 µs ± 22.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "binary_search(words, \"abcxyz\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In realtà, Python mette a disposizione il metodo `index` per la classe `list`, che implementa una ricerca lineare simile alla nostra `linear_search`. Tuttavia, `index` genera un errore se l'elemento cercato non esiste. Siccome vogliamo controllare le prestazione di `index` rispetto a `linear_search`, proviamo a cercare una parola esistenze nella lista `words`, ovvero la parola `zebra`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12.2 ms ± 698 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "linear_search(words, \"zebra\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.93 ms ± 411 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "words.index(\"zebra\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vediamo che il metodo di Python è più veloce di quello implementato da noi. Tuttavia, il miglioramento è un fattore di circa 2 o 3, non paragonabile al fattore 1000 che otteniamo usando la ricerca binaria."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.74 µs ± 30.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "binary_search(words, \"zebra\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ordinamento di liste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un altro classico problema in informatica è l'ordinamento (tant'è che in francese il computer si chiama ordinateur, ovvero *colui che ordina*). Il problema dell'ordinamento consiste, data una lista `l` qualunque, nel permutare gli elementi di `l` in maniera tale da ordinarla dall'elemento più piccolo al più grade."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python mette a disposizione il metodo `sort` per le liste che fa esattamente quello."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-4, 0, 1, 12, 44]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [ 12, 44, 1, -4, 0]\n",
    "l.sort()\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vedremo l'algoritmo noto come *selection sort* o anche *ordinamento per selezione*. Prima di tutto ci serve una funzione ausiliara che restituisce la posizione dell'elemento più piccolo in una lista. Si tratta di una funzione che abbiamo già scritto in passato, ma adesso ci serve una variante che determina il minino non di tutta la lista, ma solo di una porzione.\n",
    "\n",
    "In pratica, vogliamo una funzione `minimum_position(l, start)` che determina la posizione dell'elemento minimo tra `l[start]`, `l[start+1]`, `l[start+2]` e così via fino alla fine della lista."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimum_position(l, start):\n",
    "    \"\"\"\n",
    "    Restituisce la posizione dell'elemento minimo nella sottolista l[start:].\n",
    "    Si assume che start sia una posizione valida per l.\n",
    "    \"\"\"\n",
    "    # la variabile min_pos mantiene l'indice del valore più piccolo trovato\n",
    "    # fino ad un dato momento. La inizializziamo con start.\n",
    "    minpos = start\n",
    "    # facciamo fariare l'indice i tra start+1 e la fine della lista, alla ricerca\n",
    "    # del valore più piccolo\n",
    "    for i in range(start + 1, len(l)):\n",
    "        # se il valore corrente è più piccolo di quello minimo trovato finora,\n",
    "        # aggiorna minpos\n",
    "        if l[i] < l[minpos]:\n",
    "            minpos = i\n",
    "    return minpos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Proviamo se funziona:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "print(minimum_position([-1, 10, 4, 3], 0))\n",
    "print(minimum_position([-1, 10, 4, 3], 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Adesso possiamo usare `minimum_positon` per implementare il selection sort."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(l):\n",
    "    \"\"\"Ordina gli elementi di l.\"\"\"\n",
    "    # La variabile i è la posizione del primo elemento della lista che rimane\n",
    "    # da ordinare. Inizialmente i = 0 perché tutta la lista è da ordinare.\n",
    "    i = 0\n",
    "    # Ad ogni iterazione, metto a posto l'elemento in posizione i col valore\n",
    "    # corretto. Quando i raggiunge len(l)-1 (quindi rimane un solo elemento da\n",
    "    # ordinare nella lista), mi posso fermare perché una lista formata da un solo\n",
    "    # elemento è sicuramente ordinata.\n",
    "    while i < len(l) - 1:\n",
    "        # Determino la posizione dell'elemento minimo nella sottolista di l che parte\n",
    "        # alla posizione i. L'elemento che trovo andrà messo in posizione i.\n",
    "        m = minimum_position(l, i)\n",
    "        # Scambio l'elemento in posizione m con l'elemento in posizione i. In questo\n",
    "        # modo l[i] assume il valore correto.\n",
    "        # Lo scambio lo realizzo usando le tuple, invece della variabile ausiliaria\n",
    "        # di appoggio che abbiamo usato in altre circostanze.\n",
    "        l[i], l[m] = l[m], l[i]\n",
    "        # Incremento i perché l'elemento in posizione i è ormai sistemato.\n",
    "        i = i + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Proviamo se funziona."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-3, 1, 2, 4, 5, 10]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [1, 4, -3, 2, 10, 5]\n",
    "selection_sort(l)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notare che in realtà il ciclo `while` di sopra potremmo rimpiazzarlo con un `for`, per rendere il codice più compatto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(l):\n",
    "    \"\"\"Ordina gli elementi di l.\"\"\"\n",
    "    for i in range(len(l) - 1):\n",
    "        m = minimum_position(l, i)\n",
    "        l[i], l[m] = l[m], l[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-3, 1, 2, 4, 5, 10]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [1, 4, -3, 2, 10, 5]\n",
    "selection_sort(l)\n",
    "l"
   ]
  }
 ],
 "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.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}