Řadicí algoritmy — od bublin po chytré řazení

Než se vrhneme na celé algoritmy, ukaž si tu úplně nejmenší stavební cihličku, ze které jsou postavené úplně všechny dnešní řadicí algoritmy.

Minule jsme hledali nejkratší cestu bludištěm, dnes budeme „hledat správné pořadí“.
Každé číslo je výška sloupce. Cíl: sloupce od nejnižšího po nejvyšší.

Bubble sort porovnává sousedy. Když jsou obráceně, prohodí je. A pořád dokola.

Představ si řadu čísel jako frontu dětí. Vždycky se podíváš na dvě děti vedle sebe: když vyšší stojí vlevo a menší vpravo, prohodí si místa. Takto projdeš celou řadu zleva doprava a pak to uděláš znovu, znovu a znovu, dokud už není co prohazovat. Je to jako když bublinky postupně "vyplavou" na správné místo. Je to ale pomalé, protože u velké hromady čísel děláš skoro tolik průchodů, kolik je čísel, a v každém průchodu kontroluješ skoro všechno znovu.

Merge sort pole rozdělí, seřadí malé části a pak je postupně sloučí.

Tady použijeme trik "rozděl a panuj". Velkou hromadu nejdřív rozpůlíš, potom každou půlku zase rozpůlíš, až zbudou hromádky po jednom čísle. Hromádka s jedním číslem je vlastně už seřazená. Pak začneš hromádky spojovat zpátky: vždy vezmeš menší číslo zepředu levé nebo pravé hromádky. Je to podobné jako když spojuješ dva už seřazené balíčky karet do jednoho seřazeného balíčku.

Quick sort si vybere pivot a rozdělí pole na menší/větší část.

Quick sort si vždy vybere jedno číslo jako "pivot" (takové dočasné pravítko). Pak projde ostatní čísla a menší dá nalevo od pivotu, větší napravo. Tím vzniknou dvě menší skupiny, které se dají řešit úplně stejným trikem znovu. Znovu vybereš pivot, rozdělíš, a pokračuješ, dokud nejsou skupiny hotové. Nakonec z toho složíš celé seřazené pole.

Reální programátoři většinou nepíšou vlastní řazení od nuly. Použijí sorted() nebo .sort().

V praxi skoro nikdy nepíšeš vlastní bubble, merge ani quick sort od nuly. Python už má vestavěné řazení, které je rychlé, odladěné a používá se v reálných projektech každý den. Nejčastěji sáhneš po sorted() (vrátí nový seřazený seznam) nebo po .sort() (seřadí původní seznam). Parametr key= říká Pythonu, podle čeho se má řadit, třeba podle hodnoty předmětu místo podle jeho názvu. Díky tomu umíš snadno řadit i složitější data, nejen samotná čísla.

Zadání:

1. Napiš funkci bubble_kroky(data), která vrátí seřazené kroky bubble sortu
   💡 Poradit

   Nejdřív si připrav funkci, která dostane seznam a vrátí výsledky. Uvnitř pracuj s kopií, ať původní data zůstanou nedotčená.
   Bubble sort je jen opakované porovnání dvou sousedů a jejich případné prohození.

   def bubble_kroky(data):
       arr = data.copy()
       for i in range(len(arr)):
           for j in range(len(arr) - 1 - i):
               ...  # porovnej arr[j] a arr[j + 1]

2. Ukládej snímky po každém porovnání a zobraz je přes slider + st.bar_chart
   💡 Poradit

   Po každém porovnání si ulož „fotku“ pole — tedy arr.copy(), ne samotné arr (jinak by se ti všechny snímky měnily naráz).
   Slider ti pak vybere jeden snímek ze seznamu a ten vykreslíš grafem.

   kroky.append({"pole": arr.copy(), "popis": popis})
   i = st.slider("Krok", 0, len(kroky) - 1, 0)
   st.bar_chart(kroky[i]["pole"])

3. Přidej počitadla porovnani a prohozeni
   💡 Poradit

   Založ si dvě proměnné na nulu ještě před smyčkami. porovnani zvyšuj pokaždé, když dva prvky porovnáš — tedy v každém průchodu vnitřní smyčky. prohozeni zvyšuj jen tehdy, když opravdu došlo k výměně.
   Na konci obě čísla vrať spolu s kroky.
4. (Rozšíření) Přidej text, co se v aktuálním kroku stalo
   💡 Poradit

   Text si vytvoř jako obyčejný řetězec a ulož ho do snímku vedle pole (klíč popis). U slideru pak popis jen vypíšeš.

   popis = f"Porovnání {porovnani}: {arr[j]} a {arr[j + 1]} — prohozeno"

5. (Výzva) Přidej tlačítko na nové náhodné pole
   💡 Poradit

   Bonus: tlačítko st.button("Nové pole") vrací True, když se na něj klikne. V tu chvíli si vygeneruj nový seznam přes random.sample(range(1, 50), 10) a ulož ho do st.session_state, aby nezmizel při dalším překreslení.

Očekávaný výsledek: bubble sort, který jde krokovat sliderem a ukáže počty porovnání/prohození.

Zadání:

1. Napiš merge_sort_kroky(data) (s rekurzí) a vrať seznam kroků
   💡 Poradit

   Merge sort nejdřív rozdělí rozsah na dvě poloviny a na každou zavolá sám sebe. Uvnitř hlavní funkce si udělej pomocnou funkci, která pracuje s indexy l a r.
   Zastavení rekurze je, když už je část jednoprvková.

   def merge_sort(l, r):
       if l >= r:
           return
       m = (l + r) // 2

2. Ulož snímek po každém zápisu do původního pole
   💡 Poradit

   Při slučování zapisuješ hodnoty zpátky do arr na pozici k. Právě po každém takovém zápisu ulož snímek arr.copy() do seznamu kroků — pak uvidíš, jak se pole skládá.

   arr[k] = leva[i]
   kroky.append({"pole": arr.copy(), "popis": "Zápis"})

3. Zobraz krokování přes slider + st.bar_chart
   💡 Poradit

   Slider ti vrátí číslo kroku a ty z něj vezmeš uložený snímek. Graf pak kreslíš vždy jen z jednoho snímku.

   krok = st.slider("Krok", 0, len(kroky) - 1, 0)
   st.bar_chart(kroky[krok]["pole"])

4. (Rozšíření) Přidej počitadlo porovnání
   💡 Poradit

   Rozšíření: porovnani zvyš vždy, když ve slučování porovnáváš prvek z levé a pravé části. Protože počítáš uvnitř vnořené funkce, přidej na její začátek nonlocal porovnani.
5. (Výzva) Přidej text, jaké části se právě slučují
   💡 Poradit

   Výzva: při každém slučování už znáš indexy l, m a r — z nich si poskládej popisný text a ulož ho do snímku.

   popis = f"Slučuji {l}–{m} a {m + 1}–{r}"

Očekávaný výsledek: merge sort, který se dá projet krok po kroku.

Zadání:

1. Napiš quick_sort_kroky(data) (pivot = poslední prvek)
   💡 Poradit

   Udělej si uvnitř pomocnou funkci quick(lo, hi), která si vezme poslední prvek části jako pivot. Menší nebo rovné prvky posouvej doleva přes index i, na konci pivot prohoď na pozici i.

   pivot = arr[hi]
   i = lo

2. Ukládej snímky při důležitých krocích (porovnání + uložení pivotu)
   💡 Poradit

   Snímek ukládej na dvou místech: po každém porovnání prvku s pivotem a hlavně po tom, co pivot přijde na svou finální pozici. Vždy ukládej kopii pole.

   kroky.append({"pole": arr.copy(), "popis": f"Pivot {pivot} je na místě"})

3. Zobraz krokování přes slider + st.bar_chart
   💡 Poradit

   Zobrazení je stejné jako u ostatních cvičení: slider vybere index kroku, graf vykreslí ten jeden snímek.

   krok = st.slider("Krok", 0, len(kroky) - 1, 0)
   st.bar_chart(kroky[krok]["pole"])

4. (Rozšíření) Přidej celkový počet porovnání
   💡 Poradit

   Rozšíření: porovnani navyš pokaždé, když porovnáš aktuální prvek s pivotem. Ve vnořené funkci nezapomeň na nonlocal porovnani a číslo pak zobraz třeba přes st.metric.
5. (Výzva) Přidej popis „vlevo od pivotu / vpravo od pivotu“
   💡 Poradit

   Výzva: po porovnání víš, jestli je prvek menší než pivot (patří vlevo), nebo větší (zůstává vpravo). Podle toho si sestav text do popis.

   strana = "vlevo od pivotu" if arr[j] <= pivot else "vpravo od pivotu"

Očekávaný výsledek: quick sort krokovaný sliderem.

Zadání:

1. Připrav jedno náhodné pole (aspoň 150 čísel)
   💡 Poradit

   Vygeneruj jeden seznam a ulož si ho do proměnné — oba způsoby řazení pak musí dostat přesně stejná data, jinak by porovnání nebylo férové.

   data = [random.randint(1, 999) for _ in range(150)]

2. Seřaď ho bubble sortem a změř čas
   💡 Poradit

   Zavolej svůj bubble sort na kopii dat a čas si změř přes time.perf_counter() před a po. Rozdíl obou hodnot je doba běhu v sekundách.

   t0 = time.perf_counter()
   bubble_vysledek = bubble_sort(data.copy())
   cas_bubble = time.perf_counter() - t0

3. Seřaď stejné pole přes sorted() a změř čas
   💡 Poradit

   Stejným způsobem změř i sorted(data). Pak ověř, že oba výsledky vyšly stejně — porovnáš je obyčejným ==.

   t0 = time.perf_counter()
   python_vysledek = sorted(data)
   cas_sorted = time.perf_counter() - t0

4. (Rozšíření) Zobraz časy vedle sebe přes st.metric
   💡 Poradit

   Rozšíření: vyrob si dva sloupce přes st.columns(2) a do každého dej jednu metriku. Čas převeď na milisekundy, ať jsou čísla čitelná.

   c1, c2 = st.columns(2)
   c1.metric("Bubble", f"{cas_bubble * 1000:.1f} ms")

5. (Výzva) Ukaž i řazení seznamu slovníků pomocí key= (+ klidně reverse=True)
   💡 Poradit

   Výzva: u seznamu slovníků musíš sorted() říct, podle čeho řadit — od toho je parametr key=.

   serazeno = sorted(hrdinove, key=lambda h: h["level"], reverse=True)

Očekávaný výsledek: jasné porovnání, proč je vestavěné řazení praktické.

Zadání:

1. Použij st.session_state.hrdina se strukturou {"jmeno", "zivoty", "zlato", "inventar"}
   💡 Poradit

   Hrdinu vytvoř jen jednou — hlídej si, jestli už v session_state je. Jinak by se ti při každém kliknutí resetoval.

   if "hrdina" not in st.session_state:
       st.session_state.hrdina = {"jmeno": "Aria", "zivoty": 100, "zlato": 50, "inventar": []}

2. Inventář udělej jako seznam slovníků (nazev, hodnota, rarita)
   💡 Poradit

   Každý předmět je jeden slovník se stejnými klíči. Celý inventář je pak obyčejný seznam těchto slovníků.

   inventar = [
       {"nazev": "Meč", "hodnota": 120, "rarita": "vzácný"},
   ]

3. Přidej volbu, podle čeho řadit (nazev/hodnota/rarita) a zobraz seřazený inventář
   💡 Poradit

   Volbu nabídni přes st.selectbox — vrátí ti text, který je zároveň klíčem ve slovníku předmětu. Ten pak použij v key=.

   podle = st.selectbox("Řadit podle", ["nazev", "hodnota", "rarita"])
   serazeno = sorted(h["inventar"], key=lambda x: x[podle])

4. (Rozšíření) Přidej přepínač vzestupně/sestupně (reverse)
   💡 Poradit

   Rozšíření: st.toggle vrací True/False a přesně to potřebuje parametr reverse.

   sestupne = st.toggle("Sestupně", value=False)
   serazeno = sorted(h["inventar"], key=lambda x: x[podle], reverse=sestupne)

5. (Výzva) Přidej sloupcový graf hodnot + tlačítko „náhodná kořist“
   💡 Poradit

   Výzva: pro graf si vytáhni jen hodnoty předmětů do jednoho seznamu. Tlačítko „náhodná kořist“ pak přidá nový slovník do h["inventar"].

   st.bar_chart([p["hodnota"] for p in serazeno])

Očekávaný výsledek: hrdina hned vidí, co je nejcennější kus kořisti.

Postav miniaplikaci „Aréna řazení“: vygeneruj jedno pole čísel a porovnej na něm bubble sort, merge sort, quick sort a sorted().
Zobraz časy a počty porovnání. U jednoho vybraného algoritmu přidej i krokování přes slider a sloupcový graf.