{
 "nbformat": 4,
 "nbformat_minor": 0,
 "metadata": {
  "colab": {
   "name": "MoreTutor — sortowania i wyszukiwanie (4.10)",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "start"
   },
   "source": [
    "# Sortowania, wyszukiwanie binarne, złożoność\n",
    "\n",
    "**Sesja 4 października** · matura rozszerzona z informatyki · MoreTutor\n",
    "\n",
    "Jak pracujemy:\n",
    "\n",
    "1. Każde zadanie ma swoją komórkę. Odpowiedź wpisujesz tam, gdzie stoi `# TWOJA ODPOWIEDŹ`.\n",
    "2. Uruchamiasz komórkę (**Ctrl+Enter**) i od razu widzisz, co się zgadza, a co nie.\n",
    "3. Nic nie instalujesz — kod wykonuje się po stronie Google, Ty masz tylko przeglądarkę.\n",
    "\n",
    "Zacznij od uruchomienia komórki poniżej: ustawia dane i sprawdzarki.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "setup"
   },
   "outputs": [],
   "source": [
    "DANE = [8, 3, 5, 1, 9, 2]\n",
    "POSORTOWANA = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]\n",
    "\n",
    "\n",
    "def _porownaj(nazwa, twoje, wzorzec):\n",
    "    \"\"\"Pokazuje, ktory wiersz sie nie zgadza — zamiast suchego 'zle'.\"\"\"\n",
    "    if twoje == wzorzec:\n",
    "        print(nazwa + ': zgadza sie w calosci (' + str(len(wzorzec)) + ' wierszy)')\n",
    "        return True\n",
    "    if len(twoje) != len(wzorzec):\n",
    "        print(nazwa + ': masz ' + str(len(twoje)) + ' wierszy, powinno byc ' + str(len(wzorzec)))\n",
    "    for i in range(min(len(twoje), len(wzorzec))):\n",
    "        if twoje[i] != wzorzec[i]:\n",
    "            print('  wiersz ' + str(i + 1) + ': masz    ' + str(twoje[i]))\n",
    "            print('            powinno ' + str(wzorzec[i]))\n",
    "    return False\n",
    "\n",
    "\n",
    "def _babelkowe(dane):\n",
    "    t = list(dane)\n",
    "    stany, porownania, zamiany = [], 0, 0\n",
    "    for i in range(len(t) - 1):\n",
    "        for j in range(len(t) - 1 - i):\n",
    "            porownania += 1\n",
    "            if t[j] > t[j + 1]:\n",
    "                t[j], t[j + 1] = t[j + 1], t[j]\n",
    "                zamiany += 1\n",
    "        stany.append(list(t))\n",
    "    return stany, porownania, zamiany\n",
    "\n",
    "\n",
    "def _przez_wybor(dane):\n",
    "    t = list(dane)\n",
    "    stany, porownania, zamiany = [], 0, 0\n",
    "    for i in range(len(t) - 1):\n",
    "        m = i\n",
    "        for j in range(i + 1, len(t)):\n",
    "            porownania += 1\n",
    "            if t[j] < t[m]:\n",
    "                m = j\n",
    "        if m != i:\n",
    "            t[i], t[m] = t[m], t[i]\n",
    "            zamiany += 1\n",
    "        stany.append(list(t))\n",
    "    return stany, porownania, zamiany\n",
    "\n",
    "\n",
    "def _przez_wstawianie(dane):\n",
    "    t = list(dane)\n",
    "    stany, porownania, przesuniecia = [], 0, 0\n",
    "    for i in range(1, len(t)):\n",
    "        klucz, j = t[i], i - 1\n",
    "        while j >= 0:\n",
    "            porownania += 1\n",
    "            if t[j] > klucz:\n",
    "                t[j + 1] = t[j]\n",
    "                przesuniecia += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                break\n",
    "        t[j + 1] = klucz\n",
    "        stany.append(list(t))\n",
    "    return stany, porownania, przesuniecia\n",
    "\n",
    "\n",
    "def _trasa_binarna(tablica, cel):\n",
    "    l, p, trasa = 0, len(tablica) - 1, []\n",
    "    while l <= p:\n",
    "        s = (l + p) // 2\n",
    "        trasa.append((l, s, p))\n",
    "        if tablica[s] == cel:\n",
    "            return trasa, s\n",
    "        if tablica[s] < cel:\n",
    "            l = s + 1\n",
    "        else:\n",
    "            p = s - 1\n",
    "    return trasa, -1\n",
    "\n",
    "\n",
    "print('Gotowe. Dane do zadan 4.1-4.3:', DANE)\n",
    "print('Tablica do zadania 4.5:      ', POSORTOWANA)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zad41"
   },
   "source": [
    "## Zadanie 4.1 — sortowanie bąbelkowe\n",
    "\n",
    "Posortuj rosnąco tablicę `8, 3, 5, 1, 9, 2` metodą bąbelkową.\n",
    "\n",
    "Wpisz zawartość tablicy **po każdym przebiegu** (jest ich pięć) oraz łączną liczbę porównań i zamian.\n",
    "\n",
    "> Przebieg to jedno przejście pętli wewnętrznej przez całą nieposortowaną część — nie pojedyncza zamiana.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "zad41_kod"
   },
   "outputs": [],
   "source": [
    "# TWOJA ODPOWIEDZ — uzupelnij listy i dwie liczby\n",
    "moje_przebiegi = [\n",
    "    [],   # po przebiegu 1\n",
    "    [],   # po przebiegu 2\n",
    "    [],   # po przebiegu 3\n",
    "    [],   # po przebiegu 4\n",
    "    [],   # po przebiegu 5\n",
    "]\n",
    "moje_porownania = 0\n",
    "moje_zamiany = 0\n",
    "\n",
    "# --- sprawdzenie ---\n",
    "wzorzec, porownania, zamiany = _babelkowe(DANE)\n",
    "_porownaj('Przebiegi', moje_przebiegi, wzorzec)\n",
    "print('Porownania:', 'OK' if moje_porownania == porownania else 'masz ' + str(moje_porownania) + ', powinno ' + str(porownania))\n",
    "print('Zamiany:   ', 'OK' if moje_zamiany == zamiany else 'masz ' + str(moje_zamiany) + ', powinno ' + str(zamiany))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zad42"
   },
   "source": [
    "## Zadanie 4.2 — sortowanie przez wybór\n",
    "\n",
    "Ta sama tablica, metoda przez wybór. Wpisz stan **po każdym kroku** (pięć kroków) oraz liczbę porównań i zamian.\n",
    "\n",
    "Po uruchomieniu odpowiedz sobie: dlaczego porównań jest tyle samo co w 4.1, a zamian prawie dwa razy mniej?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "zad42_kod"
   },
   "outputs": [],
   "source": [
    "# TWOJA ODPOWIEDZ\n",
    "moje_kroki = [\n",
    "    [],   # po kroku 1\n",
    "    [],   # po kroku 2\n",
    "    [],   # po kroku 3\n",
    "    [],   # po kroku 4\n",
    "    [],   # po kroku 5\n",
    "]\n",
    "moje_porownania = 0\n",
    "moje_zamiany = 0\n",
    "\n",
    "# --- sprawdzenie ---\n",
    "wzorzec, porownania, zamiany = _przez_wybor(DANE)\n",
    "_porownaj('Kroki', moje_kroki, wzorzec)\n",
    "print('Porownania:', 'OK' if moje_porownania == porownania else 'masz ' + str(moje_porownania) + ', powinno ' + str(porownania))\n",
    "print('Zamiany:   ', 'OK' if moje_zamiany == zamiany else 'masz ' + str(moje_zamiany) + ', powinno ' + str(zamiany))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zad43"
   },
   "source": [
    "## Zadanie 4.3 — sortowanie przez wstawianie\n",
    "\n",
    "Ta sama tablica. Wpisz stan **po wstawieniu każdego kolejnego elementu** (3, 5, 1, 9, 2) oraz liczbę porównań i przesunięć.\n",
    "\n",
    "Zwróć uwagę na element `9` — ile przesunięć wymagał i dlaczego?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "zad43_kod"
   },
   "outputs": [],
   "source": [
    "# TWOJA ODPOWIEDZ\n",
    "moje_wstawienia = [\n",
    "    [],   # po wstawieniu 3\n",
    "    [],   # po wstawieniu 5\n",
    "    [],   # po wstawieniu 1\n",
    "    [],   # po wstawieniu 9\n",
    "    [],   # po wstawieniu 2\n",
    "]\n",
    "moje_porownania = 0\n",
    "moje_przesuniecia = 0\n",
    "\n",
    "# --- sprawdzenie ---\n",
    "wzorzec, porownania, przesuniecia = _przez_wstawianie(DANE)\n",
    "_porownaj('Wstawienia', moje_wstawienia, wzorzec)\n",
    "print('Porownania:  ', 'OK' if moje_porownania == porownania else 'masz ' + str(moje_porownania) + ', powinno ' + str(porownania))\n",
    "print('Przesuniecia:', 'OK' if moje_przesuniecia == przesuniecia else 'masz ' + str(moje_przesuniecia) + ', powinno ' + str(przesuniecia))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zad44"
   },
   "source": [
    "## Zadanie 4.4 — złożoność obliczeniowa\n",
    "\n",
    "Przypisz każdemu algorytmowi jego złożoność **średnią**. Format dokładnie taki: `O(1)`, `O(log n)`, `O(n)`, `O(n log n)`, `O(n^2)`.\n",
    "\n",
    "Pod spodem zobaczysz, ile operacji oznacza każda klasa dla realnych rozmiarów danych — to jest sedno tego zadania, nie same symbole.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "zad44_kod"
   },
   "outputs": [],
   "source": [
    "# TWOJA ODPOWIEDZ\n",
    "moje_zlozonosci = {\n",
    "    'babelkowe':            '',\n",
    "    'przez_wybor':          '',\n",
    "    'przez_wstawianie':     '',\n",
    "    'quicksort':            '',\n",
    "    'mergesort':            '',\n",
    "    'wyszukiwanie_liniowe': '',\n",
    "    'wyszukiwanie_binarne': '',\n",
    "}\n",
    "\n",
    "# --- sprawdzenie ---\n",
    "import math\n",
    "\n",
    "wzorzec = {\n",
    "    'babelkowe': 'O(n^2)',\n",
    "    'przez_wybor': 'O(n^2)',\n",
    "    'przez_wstawianie': 'O(n^2)',\n",
    "    'quicksort': 'O(n log n)',\n",
    "    'mergesort': 'O(n log n)',\n",
    "    'wyszukiwanie_liniowe': 'O(n)',\n",
    "    'wyszukiwanie_binarne': 'O(log n)',\n",
    "}\n",
    "for nazwa in wzorzec:\n",
    "    twoja = (moje_zlozonosci.get(nazwa) or '').replace(' ', '')\n",
    "    poprawna = wzorzec[nazwa]\n",
    "    if twoja == poprawna.replace(' ', ''):\n",
    "        print(nazwa.ljust(22) + 'OK')\n",
    "    else:\n",
    "        print(nazwa.ljust(22) + 'masz ' + (moje_zlozonosci.get(nazwa) or '(puste)') + ', powinno ' + poprawna)\n",
    "\n",
    "print()\n",
    "print('       n   O(log n)        O(n)     O(n log n)             O(n^2)')\n",
    "for n in (100, 1000, 50000):\n",
    "    print(str(n).rjust(8) + str(round(math.log2(n))).rjust(11) + str(n).rjust(12)\n",
    "          + str(round(n * math.log2(n))).rjust(15) + str(n ** 2).rjust(19))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zad45"
   },
   "source": [
    "## Zadanie 4.5 — wyszukiwanie binarne\n",
    "\n",
    "Tablica posortowana, indeksy 0–10:\n",
    "\n",
    "`2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91`\n",
    "\n",
    "Rozpisz wyszukiwanie wartości **72** oraz **40**. Każdy krok to trójka `(lewy, środek, prawy)` — wartości **przed** podjęciem decyzji.\n",
    "\n",
    "Na koniec podaj maksymalną liczbę kroków dla tej tablicy.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "zad45_kod"
   },
   "outputs": [],
   "source": [
    "# TWOJA ODPOWIEDZ — kazdy krok jako (lewy, srodek, prawy)\n",
    "trasa_72 = [\n",
    "    # (0, 5, 10),\n",
    "]\n",
    "trasa_40 = [\n",
    "\n",
    "]\n",
    "maksymalna_liczba_krokow = 0\n",
    "\n",
    "# --- sprawdzenie ---\n",
    "import math\n",
    "\n",
    "for cel, twoja in ((72, trasa_72), (40, trasa_40)):\n",
    "    wzorzec, indeks = _trasa_binarna(POSORTOWANA, cel)\n",
    "    _porownaj('Trasa dla ' + str(cel), [tuple(k) for k in twoja], wzorzec)\n",
    "    opis = 'indeks ' + str(indeks) if indeks >= 0 else 'nie ma w tablicy'\n",
    "    print('  wynik: ' + opis + ', krokow: ' + str(len(wzorzec)))\n",
    "\n",
    "maks = math.floor(math.log2(len(POSORTOWANA))) + 1\n",
    "print('Maksymalna liczba krokow:', 'OK' if maksymalna_liczba_krokow == maks else 'masz ' + str(maksymalna_liczba_krokow) + ', powinno ' + str(maks))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zad46"
   },
   "source": [
    "## Zadanie 4.6 — implementacja (typ maturalny)\n",
    "\n",
    "Napisz funkcję `sortuj_przez_wybor(lista)`, która:\n",
    "\n",
    "- sortuje listę **rosnąco**,\n",
    "- zwraca **dwie** wartości: posortowaną listę oraz liczbę wykonanych porównań,\n",
    "- **nie modyfikuje** listy przekazanej w argumencie.\n",
    "\n",
    "Sprawdzarka policzy też, ile porównań wychodzi dla stu elementów — porównaj to ze wzorem `n(n-1)/2`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "zad46_kod"
   },
   "outputs": [],
   "source": [
    "# TWOJA ODPOWIEDZ\n",
    "def sortuj_przez_wybor(lista):\n",
    "    pass\n",
    "\n",
    "\n",
    "# --- sprawdzenie ---\n",
    "oryginal = [8, 3, 5, 1, 9, 2]\n",
    "kopia = list(oryginal)\n",
    "wynik = sortuj_przez_wybor(oryginal)\n",
    "\n",
    "if not isinstance(wynik, tuple) or len(wynik) != 2:\n",
    "    print('Funkcja ma zwracac dwie wartosci: liste i liczbe porownan')\n",
    "else:\n",
    "    posortowana, porownania = wynik\n",
    "    print('Sortowanie:        ', 'OK' if posortowana == sorted(kopia) else 'masz ' + str(posortowana))\n",
    "    print('Porownania:        ', 'OK' if porownania == 15 else 'masz ' + str(porownania) + ', powinno 15')\n",
    "    print('Oryginal nietkniety:', 'OK' if oryginal == kopia else 'NIE — zrob kopie przez lista[:]')\n",
    "    print('Dla 100 elementow: ', sortuj_przez_wybor(list(range(100, 0, -1)))[1], '(wzor n(n-1)/2 = 4950)')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "zad47"
   },
   "source": [
    "## Zadanie 4.7 — do domu\n",
    "\n",
    "Dopisz do sortowania bąbelkowego flagę, która przerywa pętlę zewnętrzną, gdy w całym przebiegu nie wykonano żadnej zamiany.\n",
    "\n",
    "Funkcja ma zwracać posortowaną listę **oraz liczbę wykonanych przebiegów**. Pytanie na koniec: jaka jest złożoność tej wersji dla tablicy już posortowanej?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "zad47_kod"
   },
   "outputs": [],
   "source": [
    "# TWOJA ODPOWIEDZ — zwroc (posortowana_lista, liczba_przebiegow)\n",
    "def sortuj_babelkowo(lista):\n",
    "    pass\n",
    "\n",
    "\n",
    "# --- sprawdzenie ---\n",
    "wynik = sortuj_babelkowo([1, 2, 3, 4, 5, 6])\n",
    "if not isinstance(wynik, tuple) or len(wynik) != 2:\n",
    "    print('Funkcja ma zwracac liste i liczbe wykonanych przebiegow')\n",
    "else:\n",
    "    lista, przebiegi = wynik\n",
    "    print('Posortowana:', 'OK' if lista == [1, 2, 3, 4, 5, 6] else 'masz ' + str(lista))\n",
    "    print('Przebiegi dla danych posortowanych:', 'OK' if przebiegi == 1 else 'masz ' + str(przebiegi) + ', powinno 1')\n",
    "    print('Test na danych losowych:', sortuj_babelkowo([8, 3, 5, 1, 9, 2])[0])\n"
   ]
  }
 ]
}