{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "k00",
   "metadata": {},
   "source": [
    "# Sortowanie\n",
    "\n",
    "*Wersja notatnika: 2026-10-16 · przygotowanie: dr inż. Szczepan Górtowski*\n",
    "\n",
    "`sorted()` znasz od zajęć 2. Dziś zaglądasz do środka: napiszesz sortowanie bąbelkowe, przez wybieranie, przez\n",
    "wstawianie i przez scalanie, policzysz ich porównania i zobaczysz, dlaczego żadne sortowanie przez porównania nie\n",
    "zejdzie poniżej ok. `n log n` porównań — i jak to obejść, gdy wartości jest mało.\n",
    "\n",
    "### Jak korzystać\n",
    "1. Uruchamiaj komórki po kolei: `Ctrl + Enter` albo `Shift + Enter`.\n",
    "2. Przy ramkach **Przewidź, zanim uruchomisz** najpierw zgadnij, potem uruchom, na końcu rozwiń odpowiedź.\n",
    "3. W zadaniach zamień `pass` i `TODO` na swój kod i uruchom komórkę **Sprawdź**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k01",
   "metadata": {},
   "source": [
    "## Spis treści\n",
    "1. Problem sortowania i dane do porównań\n",
    "2. Sortowanie bąbelkowe\n",
    "3. Sortowanie przez wybieranie\n",
    "4. Sortowanie przez wstawianie\n",
    "5. Sortowanie przez scalanie (*merge sort*)\n",
    "6. Quicksort\n",
    "7. Ile porównań naprawdę potrzeba? Dolna granica `log₂(n!)`\n",
    "8. Pomiar czasu: O(n²), O(n log n) i `sorted()`\n",
    "9. Sortowanie przez zliczanie: gdy wartości jest mało\n",
    "10. Zadania 9.0–9.3 i zadanie 9.4 dla chętnych"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k02",
   "metadata": {},
   "source": [
    "## 1) Problem sortowania i dane do porównań\n",
    "\n",
    "Każdy algorytm poniżej dostaje listę i zwraca **nową** posortowaną listę oraz liczniki: ile razy porównał dwa\n",
    "elementy i ile razy coś przestawił. Liczby porównań to język, w którym porównujemy algorytmy — niezależny od komputera.\n",
    "Dane: 8 kart z ćwiczenia na kartkach i 1000 losowych liczb (stałe ziarno, więc wyniki są powtarzalne)."
   ]
  },
  {
   "cell_type": "code",
   "id": "k03",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "KARTY = [5, 2, 8, 1, 9, 3, 7, 4]\n",
    "random.seed(2026)\n",
    "DANE = [random.randint(0, 1_000_000) for _ in range(1000)]\n",
    "print(\"karty:\", KARTY)\n",
    "print(\"dane: \", len(DANE), \"liczb, np.\", DANE[:5])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k04",
   "metadata": {},
   "source": [
    "## 2) Sortowanie bąbelkowe\n",
    "\n",
    "Porównuj **sąsiadów** od lewej do prawej i zamieniaj, jeśli stoją źle. Po pierwszym przebiegu największy element\n",
    "„wypływa” na koniec jak bąbelek. Jeśli w przebiegu nie było żadnej zamiany, lista jest posortowana — kończysz wcześniej."
   ]
  },
  {
   "cell_type": "code",
   "id": "k05",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def babelkowe(lista):\n",
    "    a = list(lista)\n",
    "    porownania = zamiany = 0\n",
    "    for koniec in range(len(a) - 1, 0, -1):\n",
    "        zamiana = False\n",
    "        for j in range(koniec):\n",
    "            porownania += 1\n",
    "            if a[j] > a[j + 1]:\n",
    "                a[j], a[j + 1] = a[j + 1], a[j]\n",
    "                zamiany += 1\n",
    "                zamiana = True\n",
    "        if not zamiana:\n",
    "            break\n",
    "    return a, porownania, zamiany\n",
    "\n",
    "print(babelkowe(KARTY))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k06",
   "metadata": {},
   "source": [
    "## 3) Sortowanie przez wybieranie\n",
    "\n",
    "Znajdź **najmniejszy** element w nieposortowanej części i zamień go z pierwszym. Powtórz dla reszty. Porównań jest zawsze\n",
    "tyle samo — ok. `n²/2` — ale zamian najwyżej `n − 1`. Przydaje się, gdy zamiana jest droga."
   ]
  },
  {
   "cell_type": "code",
   "id": "k07",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def wybieranie(lista):\n",
    "    a = list(lista)\n",
    "    porownania = zamiany = 0\n",
    "    for i in range(len(a) - 1):\n",
    "        najmn = i\n",
    "        for j in range(i + 1, len(a)):\n",
    "            porownania += 1\n",
    "            if a[j] < a[najmn]:\n",
    "                najmn = j\n",
    "        if najmn != i:\n",
    "            a[i], a[najmn] = a[najmn], a[i]\n",
    "            zamiany += 1\n",
    "    return a, porownania, zamiany\n",
    "\n",
    "print(wybieranie(KARTY))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k08",
   "metadata": {},
   "source": [
    "## 4) Sortowanie przez wstawianie\n",
    "\n",
    "Tak układasz karty w ręce: bierzesz kolejną i **wsuwasz** ją w lewo, aż trafi na swoje miejsce. Dla listy prawie\n",
    "posortowanej robi bardzo mało pracy — dlatego Timsort i Powersort (zajęcia 2) sortują nim krótkie fragmenty."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k09",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** które z trzech sortowań zrobi najmniej porównań dla listy **już posortowanej**?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> Bąbelkowe z wczesnym wyjściem i przez wstawianie: po `n − 1` porównań. Przez wybieranie — zawsze `n(n − 1)/2`, bo nie wie, że lista jest posortowana.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k10",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def wstawianie(lista):\n",
    "    a = list(lista)\n",
    "    porownania = przesuniecia = 0\n",
    "    for i in range(1, len(a)):\n",
    "        klucz = a[i]\n",
    "        j = i - 1\n",
    "        while j >= 0:\n",
    "            porownania += 1\n",
    "            if a[j] > klucz:\n",
    "                a[j + 1] = a[j]\n",
    "                przesuniecia += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                break\n",
    "        a[j + 1] = klucz\n",
    "    return a, porownania, przesuniecia\n",
    "\n",
    "print(wstawianie(KARTY))\n",
    "posortowane = sorted(DANE)\n",
    "for f in (babelkowe, wybieranie, wstawianie):\n",
    "    p = f(posortowane)[1]\n",
    "    print(f\"{f.__name__:<11} posortowana lista: {p:>7} porównań\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k11",
   "metadata": {},
   "source": [
    "## 5) Sortowanie przez scalanie (*merge sort*)\n",
    "\n",
    "Rekurencja z zajęć 8 i strategia **dziel i zwyciężaj**: podziel listę na połowy, posortuj każdą (rekurencyjnie),\n",
    "a potem **scal** dwie posortowane listy, biorąc zawsze mniejszy z dwóch początków. Scalanie znasz z zadania 4.3\n",
    "(kopiec), tu wystarczą dwa wskaźniki. Poziomów podziału jest `log₂ n`, na każdym scalasz `n` elementów: O(n log n)."
   ]
  },
  {
   "cell_type": "code",
   "id": "k12",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def scal_licz(a, b, licznik):\n",
    "    wynik = []\n",
    "    i = j = 0\n",
    "    while i < len(a) and j < len(b):\n",
    "        licznik[0] += 1\n",
    "        if a[i] <= b[j]:\n",
    "            wynik.append(a[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            wynik.append(b[j])\n",
    "            j += 1\n",
    "    return wynik + a[i:] + b[j:]\n",
    "\n",
    "def scalanie(lista, licznik=None):\n",
    "    if licznik is None:\n",
    "        licznik = [0]\n",
    "    if len(lista) <= 1:\n",
    "        return list(lista), licznik[0]\n",
    "    srodek = len(lista) // 2\n",
    "    lewa, _ = scalanie(lista[:srodek], licznik)\n",
    "    prawa, _ = scalanie(lista[srodek:], licznik)\n",
    "    return scal_licz(lewa, prawa, licznik), licznik[0]\n",
    "\n",
    "print(scalanie(KARTY))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k13",
   "metadata": {},
   "source": [
    "## 6) Quicksort\n",
    "\n",
    "Wybierz **pivot** (element podziału), rozdziel resztę na mniejsze i większe, posortuj obie części rekurencyjnie.\n",
    "Algorytm wymyślił Tony Hoare w 1959 r. jako student na Uniwersytecie Moskiewskim, opublikował w 1961 r.\n",
    "(*Communications of the ACM*, „Algorithm 64: Quicksort”). Średnio O(n log n), ale przy złym pivocie — np. pierwszym\n",
    "elemencie listy już posortowanej — O(n²). Wersja poniżej jest czytelna, ale tworzy nowe listy; prawdziwy quicksort\n",
    "przestawia elementy w miejscu."
   ]
  },
  {
   "cell_type": "code",
   "id": "k14",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def quicksort(lista):\n",
    "    if len(lista) <= 1:\n",
    "        return list(lista)\n",
    "    pivot = lista[len(lista) // 2]\n",
    "    mniejsze = [x for x in lista if x < pivot]\n",
    "    rowne = [x for x in lista if x == pivot]\n",
    "    wieksze = [x for x in lista if x > pivot]\n",
    "    return quicksort(mniejsze) + rowne + quicksort(wieksze)\n",
    "\n",
    "print(quicksort(KARTY))\n",
    "print(quicksort(DANE) == sorted(DANE))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k15",
   "metadata": {},
   "source": [
    "## 7) Ile porównań naprawdę potrzeba? Dolna granica `log₂(n!)`\n",
    "\n",
    "`n` elementów można ułożyć na `n!` sposobów. Każde porównanie daje odpowiedź tak/nie, czyli najwyżej **połowi**\n",
    "zbiór możliwych ułożeń — jak pytania w „zgadnij liczbę” z zajęć 8. Żeby wskazać jedno ułożenie z `n!`, trzeba więc\n",
    "co najmniej `log₂(n!)` porównań (w najgorszym przypadku). Dla `n = 1000` to ok. 8 530 — a to mniej więcej `n log₂ n`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k16",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "wyniki = {\n",
    "    \"bąbelkowe\": babelkowe(DANE)[1],\n",
    "    \"wybieranie\": wybieranie(DANE)[1],\n",
    "    \"wstawianie\": wstawianie(DANE)[1],\n",
    "    \"scalanie\": scalanie(DANE)[1],\n",
    "}\n",
    "granica = math.lgamma(len(DANE) + 1) / math.log(2)    # log2(1000!)\n",
    "for nazwa, p in wyniki.items():\n",
    "    print(f\"{nazwa:<11} {p:>8} porównań\")\n",
    "print(f\"{'granica':<11} {granica:>8.0f}  = log2(1000!)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k17",
   "metadata": {},
   "source": [
    "## 8) Pomiar czasu: O(n²), O(n log n) i `sorted()`\n",
    "\n",
    "Liczby porównań przekładają się na czas. `sorted()` jest napisane w C i używa Powersorta (zajęcia 2), więc wygrywa\n",
    "z każdą wersją w Pythonie — ale **tempo wzrostu** jest takie samo jak u sortowania przez scalanie."
   ]
  },
  {
   "cell_type": "code",
   "id": "k18",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def czas(funkcja, dane):\n",
    "    start = time.perf_counter()\n",
    "    funkcja(dane)\n",
    "    return (time.perf_counter() - start) * 1000\n",
    "\n",
    "print(f\"{'n':>6} {'wstawianie':>11} {'scalanie':>9} {'sorted':>8}  [ms]\")\n",
    "for n in [500, 1000, 2000]:\n",
    "    dane = [random.random() for _ in range(n)]\n",
    "    print(f\"{n:>6} {czas(wstawianie, dane):>11.1f} \"\n",
    "          f\"{czas(scalanie, dane):>9.2f} {czas(sorted, dane):>8.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k19",
   "metadata": {},
   "source": [
    "## 9) Sortowanie przez zliczanie: gdy wartości jest mało\n",
    "\n",
    "Granica `log₂(n!)` dotyczy sortowania **przez porównania**. Jeśli możliwych wartości jest niewiele — np. oceny\n",
    "2,0–5,0 — możesz policzyć, ile jest każdej, i wypisać je po kolei. Zero porównań między elementami, czas O(n + k),\n",
    "gdzie `k` to liczba możliwych wartości. To zadanie 9.4."
   ]
  },
  {
   "cell_type": "code",
   "id": "k20",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "oceny = [4.0, 3.0, 5.0, 3.0, 4.5, 2.0, 4.0, 3.5]\n",
    "ile = Counter(oceny)\n",
    "print(ile)\n",
    "print([ocena for ocena in sorted(ile) for _ in range(ile[ocena])])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k21",
   "metadata": {},
   "source": [
    "**Zobacz:** projekt AlgoRythmics z Uniwersytetu Sapientia (Târgu Mureș) pokazuje sortowania jako tańce ludowe —\n",
    "filmy znajdziesz na YouTube, wpisując „AlgoRythmics insert sort” albo „AlgoRythmics bubble sort”."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k22",
   "metadata": {},
   "source": [
    "## 10) Zadanie 9.0 — czy lista jest posortowana?\n",
    "\n",
    "Napisz `czy_posortowana(lista)`: `True`, gdy każdy element jest nie większy od następnego. Pusta lista i lista\n",
    "z jednym elementem są posortowane."
   ]
  },
  {
   "cell_type": "code",
   "id": "k23",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def czy_posortowana(lista: list) -> bool:\n",
    "    \"\"\"True, jeśli każdy element jest nie większy od następnego.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k24",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert czy_posortowana([1, 2, 2, 5])\n",
    "    assert not czy_posortowana([1, 3, 2])\n",
    "    assert czy_posortowana([]) and czy_posortowana([7])\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 9.0 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k25",
   "metadata": {},
   "source": [
    "## Zadanie 9.1 — sortowanie przez wstawianie\n",
    "\n",
    "Napisz `sortuj_wstawianie(lista)`: zwraca **nową** posortowaną listę, oryginału nie zmienia. Bez `sort` i `sorted`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k26",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def sortuj_wstawianie(lista: list) -> list:\n",
    "    \"\"\"Nowa, posortowana lista; oryginał bez zmian.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k27",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    dane = [5, 2, 8, 1, 9, 3, 7, 4]\n",
    "    assert sortuj_wstawianie(dane) == [1, 2, 3, 4, 5, 7, 8, 9]\n",
    "    assert dane == [5, 2, 8, 1, 9, 3, 7, 4], 'oryginał się zmienił'\n",
    "    assert sortuj_wstawianie([]) == []\n",
    "    assert sortuj_wstawianie([3, 1, 3]) == [1, 3, 3]\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 9.1 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k28",
   "metadata": {},
   "source": [
    "## Zadanie 9.2 — scalanie dwóch posortowanych list\n",
    "\n",
    "Napisz `scal(a, b)`: z dwóch posortowanych list robi jedną posortowaną. Dwa wskaźniki `i`, `j`; bierz mniejszy\n",
    "z `a[i]` i `b[j]`. Na końcu doklej to, co zostało."
   ]
  },
  {
   "cell_type": "code",
   "id": "k29",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def scal(a: list, b: list) -> list:\n",
    "    \"\"\"Scala dwie posortowane listy w jedną posortowaną.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k30",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert scal([1, 4, 9], [2, 3, 10, 11]) == [1, 2, 3, 4, 9, 10, 11]\n",
    "    assert scal([], [1, 2]) == [1, 2] and scal([3], []) == [3]\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 9.2 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k31",
   "metadata": {},
   "source": [
    "## Zadanie 9.3 — sortowanie przez scalanie\n",
    "\n",
    "Napisz rekurencyjne `sortuj_scalanie(lista)`, używając swojej funkcji `scal` z zadania 9.2.\n",
    "Przypadek bazowy: lista długości 0 albo 1."
   ]
  },
  {
   "cell_type": "code",
   "id": "k32",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def sortuj_scalanie(lista: list) -> list:\n",
    "    \"\"\"Sortowanie przez scalanie: podziel, posortuj połowy, scal.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k33",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert sortuj_scalanie(KARTY) == [1, 2, 3, 4, 5, 7, 8, 9]\n",
    "    assert sortuj_scalanie([]) == []\n",
    "    assert sortuj_scalanie(DANE) == sorted(DANE)\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 9.3 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k34",
   "metadata": {},
   "source": [
    "## Zadanie 9.4 dla chętnych — sortowanie przez zliczanie\n",
    "\n",
    "Napisz `sortuj_zliczanie(oceny)` dla ocen ze skali UEP `(2.0, 3.0, 3.5, 4.0, 4.5, 5.0)` — bez `sort`, `sorted`\n",
    "i bez porównywania ocen między sobą. Policz wystąpienia każdej oceny i wypisz je w kolejności skali."
   ]
  },
  {
   "cell_type": "code",
   "id": "k35",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def sortuj_zliczanie(oceny: list) -> list:\n",
    "    \"\"\"Sortuje oceny ze skali UEP bez porównywania elementów.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k36",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert sortuj_zliczanie([4.0, 2.0, 5.0, 4.0]) == [2.0, 4.0, 4.0, 5.0]\n",
    "    assert sortuj_zliczanie([]) == []\n",
    "    skala = [2.0, 3.0, 3.5, 4.0, 4.5, 5.0]\n",
    "    duzo = [random.choice(skala) for _ in range(10_000)]\n",
    "    assert sortuj_zliczanie(duzo) == sorted(duzo)\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 9.4 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k37",
   "metadata": {},
   "source": [
    "## Zapamiętaj\n",
    "\n",
    "| Algorytm | Porównania (typowo) | Uwagi |\n",
    "|---|---|---|\n",
    "| bąbelkowe | O(n²) | proste; z wczesnym wyjściem szybkie dla posortowanych |\n",
    "| przez wybieranie | O(n²) zawsze | najwyżej `n − 1` zamian |\n",
    "| przez wstawianie | O(n²), dla prawie posortowanych ~O(n) | jak karty w ręce; część Timsorta i Powersorta |\n",
    "| przez scalanie | O(n log n) | dziel i zwyciężaj; stabilne |\n",
    "| quicksort | średnio O(n log n), najgorzej O(n²) | zależy od pivota |\n",
    "| przez zliczanie | O(n + k), bez porównań | tylko gdy wartości jest mało |\n",
    "\n",
    "Żadne sortowanie **przez porównania** nie zejdzie poniżej `log₂(n!) ≈ n log₂ n` porównań.\n",
    "\n",
    "## Zadania dodatkowe\n",
    "\n",
    "1. Dla jakich danych sortowanie przez wstawianie jest najwolniejsze? Sprawdź licznikiem.\n",
    "2. Które z algorytmów są stabilne (zajęcia 2)? Sprawdź na parach `(ocena, imię)`.\n",
    "3. Dlaczego `quicksort` z pivotem `lista[0]` jest wolny dla posortowanej listy?"
   ]
  }
 ],
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  }
 }
}