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

Co si z toho odnést: graf je jen new string('█', hodnota) a řazení uvidíš podle toho, jak se sloupce postupně srovnávají do schodů.

Co si z toho odnést: po každém průchodu je vpravo o jedno číslo „doma". A ten sloupeček počtů porovnání je jediné, co dnes opravdu porovnáváme.

Co si z toho odnést: nejvíc odsazené řádky jsou nejmenší hromádky. Postupují zdola nahoru — čím výš, tím větší a hotovější kousky pole.

Co si z toho odnést: quicksort nic nesluje — hromádky jsou už ve správném pořadí, stačí je slepit za sebe pomocí AddRange.

Co si z toho odnést: OrderBy vyrobí nový seřazený seznam, Sort přerovná ten původní. Když se ti pořadí „záhadně" změnilo, sáhl jsi na Sort.

Zadání:

Napiš bubble sort tak, aby bylo po každém průchodu vidět, co se v poli stalo.

1. Dokonči metodu Vykresli a vypiš pole před řazením
   💡 Poradit

   Projdi pole cyklem foreach a každou hodnotu vypiš jako sloupec:
   Console.WriteLine($"{hodnota,3} │{new string('█', hodnota)}");
{hodnota,3} zarovná číslo na tři znaky, aby byla svislítka pod sebou.
   Řádek čísel vyrobíš pomocí string.Join(" ", pole).
2. Napiš vnitřní cyklus: porovnej každé dva sousedy a prohoď je
   💡 Poradit

   Cyklus musí skončit o jedno dřív, protože saháš i na pole[j + 1]:
   for (int j = 0; j < pole.Length - 1; j++)
   Uvnitř: if (pole[j] > pole[j + 1]) (pole[j], pole[j + 1]) = (pole[j + 1], pole[j]);
3. Obal ho vnějším cyklem a po každém průchodu vypiš stav pole
   💡 Poradit

   Vnější cyklus: for (int i = 0; i < pole.Length - 1; i++)
   Vnitřní se smí pokaždé zkrátit, konec pole je už hotový:
   for (int j = 0; j < pole.Length - 1 - i; j++)
   Za vnitřním cyklem (ale ještě uvnitř vnějšího) vypiš string.Join(" ", pole).
4. Přidej počitadla porovnani a prohozeni a vypiš je na konci
   💡 Poradit

   Obě proměnné si připrav před cykly: int porovnani = 0;
porovnani++; patří hned před if — porovnání proběhne vždycky.
   prohozeni++; patří dovnitř if — prohodí se jen někdy.
5. Zastav řazení dřív, když se v průchodu nic neprohodilo
   💡 Poradit

   Na začátku každého průchodu nastav bool prohozenoVPruchodu = false;
   Při každém prohození ji přepni na true.
   Na konci průchodu: if (!prohozenoVPruchodu) break;

Zadání:

Celý merge sort stojí na jedné jediné dovednosti: slít dvě seřazené hromádky. Tu si nejdřív vyrob.

1. Napiš hlavní cyklus metody Slij: dokud mají obě hromádky prvky, ber menší z vrchu
   💡 Poradit

   Potřebuješ dva ukazatele: int i = 0; do levé a int j = 0; do pravé hromádky.
   while (i < leva.Count && j < prava.Count)
   Uvnitř porovnej vrchy a ten menší přidej do výsledku:
   if (leva[i] <= prava[j]) { vysledek.Add(leva[i]); i++; }
else { vysledek.Add(prava[j]); j++; }
2. Dolij zbytek hromádky, která ještě něco má, a Slij vyzkoušej
   💡 Poradit

   Když jedna hromádka dojde, druhá je celá větší — stačí ji přilepit:
   while (i < leva.Count) { vysledek.Add(leva[i]); i++; }
while (j < prava.Count) { vysledek.Add(prava[j]); j++; }
   Bez těchhle dvou řádků ti na konci budou chybět čísla.
3. Doplň MergeSort: dno rekurze, rozdělení na půlky a volání sebe sama
   💡 Poradit

   Dno rekurze: if (data.Count <= 1) return data; — jeden prvek je seřazený sám o sobě.
   Rozdělení: int stred = data.Count / 2;
var leva = MergeSort(data.GetRange(0, stred));
var prava = MergeSort(data.GetRange(stred, data.Count - stred));
   Druhý parametr GetRange je počet prvků, ne index konce.
4. Vypisuj každé slévání s odsazením podle hloubky rekurze
   💡 Poradit

   Přidej metodě parametr int hloubka a při rekurzi předávej hloubka + 1.
   Odsazení vyrobíš stejně jako sloupce: string odsazeni = new string(' ', hloubka * 2);
   Vypiš to až po slití: $"{odsazeni}[{string.Join(" ", leva)}] + [{string.Join(" ", prava)}] → [{string.Join(" ", spojene)}]"
5. Přidej počitadlo porovnání a srovnej ho s bubble sortem na stejných datech
   💡 Poradit

   Proměnnou int porovnani = 0; si dej úplně nahoru, ať na ni obě metody vidí.
   porovnani++; patří dovnitř hlavního cyklu ve Slij, hned před if.
   Na bubble sort si napiš metodu, která vrátí jen počet porovnání — dovnitř si udělej kopii dat: var kopie = new List<int>(vstup);

Zadání:

Quicksort nic nesluje. Vybere si jedno číslo a podle něj celé pole rozhází na tři hromádky.

1. V metodě QuickSort vyber pivot ze středu a připrav tři prázdné hromádky
   💡 Poradit

   Pivot bereme ze středu, protože zleva by to na seřazených datech dopadlo špatně:
   int pivot = data[data.Count / 2];
   Hromádky jsou obyčejné seznamy:
   var mensi = new List<int>();, var stejne = new List<int>();, var vetsi = new List<int>();
2. Rozděl všechny prvky do hromádek a vypiš je
   💡 Poradit

   Projdi data cyklem foreach a každé číslo pošli do správné hromádky:
   if (hodnota < pivot) mensi.Add(hodnota);
else if (hodnota > pivot) vetsi.Add(hodnota);
else stejne.Add(hodnota);
   Rovné prvky musí jít do stejne, jinak by se pivot vracel pořád dokola.
3. Doplň dno rekurze, rekurzivní volání a slep výsledek
   💡 Poradit

   Dno rekurze patří úplně nahoru: if (data.Count <= 1) return data;
   Slepení se dělá metodou AddRange, a to přesně v tomhle pořadí:
   vysledek.AddRange(QuickSort(mensi, hloubka + 1));
vysledek.AddRange(stejne);
vysledek.AddRange(QuickSort(vetsi, hloubka + 1));
4. Přidej odsazení podle hloubky a počitadlo porovnání
   💡 Poradit

   string odsazeni = new string(' ', hloubka * 2); a při rekurzi předávej hloubka + 1.
   porovnani++; dej dovnitř foreach — každý prvek se s pivotem porovnává.
   Proměnnou int porovnani = 0; si připrav nahoře, ať na ni metoda vidí.
5. Porovnej pivot ze středu a pivot zleva na už seřazeném poli
   💡 Poradit

   Přidej metodě parametr bool pivotZleva a hned za výběrem pivota:
   if (pivotZleva) pivot = data[0];
   Před každým během vynuluj počitadlo: porovnani = 0;
   Pusť obě varianty na new List<int> { 1, 2, 3, 4, 5, 6, 7, 8 } a porovnej čísla i odsazení výpisu.

Zadání:

Teď to zkus naostro. Tisíc dvě stě čísel — a uvidíš, kde je hranice mezi „hloupým" a „hotovým".

1. Vyrob pole POCET náhodných čísel pomocí new Random(42) a vypiš prvních deset
   💡 Poradit

   Číslo v závorce je semínko — se stejným semínkem dostaneš pokaždé stejná čísla.
   var generator = new Random(42);
data[k] = generator.Next(1, 1000); vrátí číslo od 1 do 999.
   Prvních deset vypíšeš přes LINQ: string.Join(" ", data.Take(10))
2. Napiš metodu BubbleSort, která pole seřadí a vrátí počet porovnání
   💡 Poradit

   Je to přesně ten kód z cvičení 1, jen zabalený do metody s návratovou hodnotou:
   int BubbleSort(int[] data) { ... return porovnani; }
   Pouštěj ho na kopii, ať máš pořád i původní data: int[] kopie = puvodni.ToArray();
3. Seřaď druhou kopii pomocí Array.Sort a ověř, že výsledky jsou stejné
   💡 Poradit

   Array.Sort(kopieB); seřadí pole rovnou na místě, nic nevrací.
   Shodu ověříš jedním voláním z LINQ:
   bool stejne = kopieA.SequenceEqual(kopieB);
   Kdyby vyšlo false, máš v bubble sortu chybu.
4. Změř obě řazení pomocí Stopwatch
   💡 Poradit

   Nahoru přidej using System.Diagnostics;
var stopky = Stopwatch.StartNew(); … stopky.Stop();
   Výsledek přečteš jako stopky.Elapsed.TotalMilliseconds a zaokrouhlíš:
   $"{stopky.Elapsed.TotalMilliseconds:F1} ms"
5. Vypiš pomocí LINQ pět největších čísel a pět nejmenších
   💡 Poradit

   puvodni.OrderByDescending(x => x).Take(5) vrátí pět největších.
   puvodni.OrderBy(x => x).Take(5) vrátí pět nejmenších.
   Obojí pak vypiš přes string.Join(" ", ...). Všimni si, že původní pole se nezměnilo.

Zadání:

Hrdina nasbíral hromadu věcí a batoh je v nepořádku. Zařiď, ať si ho umí srovnat podle čehokoliv.

1. Vytvoř inventář jako seznam n-tic a vypiš ho jako tabulku
   💡 Poradit

   Typ napiš celý: var inventar = new List<(string nazev, int cena, string vzacnost)>();
   Předmět přidáš jako trojici: ("Lektvar zdraví", 25, "běžný")
   V metodě Vypis zarovnej názvy: polozka.nazev.PadRight(22) a cenu {polozka.cena,4}.
2. Seřaď kopii inventáře bubble sortem podle ceny
   💡 Poradit

   Kopii vyrobíš takhle: var kopie = new List<(string nazev, int cena, string vzacnost)>(inventar);
   Porovnává se jen jedna položka n-tice: if (kopie[j].cena > kopie[j + 1].cena)
   Prohození funguje úplně stejně jako u čísel: (kopie[j], kopie[j + 1]) = (kopie[j + 1], kopie[j]);
3. To samé jedním řádkem přes OrderByDescending a vypiš tři nejcennější
   💡 Poradit

   inventar.OrderByDescending(p => p.cena).Take(3).ToList()
   Zápis p => p.cena znamená „u každé položky se dívej na její cenu".
   OrderBy původní seznam nemění — vrací nový.
4. Seřaď podle vzácnosti a uvnitř každé skupiny podle ceny sestupně
   💡 Poradit

   Abeceda by dala špatné pořadí, tak si vzácnostem přiděl čísla:
   var PORADI = new Dictionary<string, int> { ["legendární"] = 0, ["vzácný"] = 1, ["běžný"] = 2 };
   Pak se řadí dvakrát za sebou:
   inventar.OrderBy(p => PORADI[p.vzacnost]).ThenByDescending(p => p.cena).ToList()
5. Vypiš souhrn: celkovou hodnotu, nejdražší předmět a počty podle vzácnosti
   💡 Poradit

   Součet i maximum umí LINQ: inventar.Sum(p => p.cena) a inventar.Max(p => p.cena).
   Nejdražší předmět dostaneš jako první z seřazeného seznamu:
   var nejdrazsi = inventar.OrderByDescending(p => p.cena).First();
   Počty spočítej cyklem přes PORADI.Keys a inventar.Count(p => p.vzacnost == klic).

Vyrob program „Žebříček hrdinů". Připrav si pět hrdinů jako n-tice (jméno, úroveň, zlato) a pak:

• vypiš hrdiny tak, jak jsi je zadal,
• seřaď je vlastním bubble sortem podle úrovně od nejvyšší,
• totéž udělej jedním řádkem přes OrderByDescending a ověř, že vyšlo to samé,
• přidej druhé kritérium: při stejné úrovni rozhoduje zlato (ThenByDescending),
• a ke každému hrdinovi dokresli sloupec z █ podle jeho úrovně.

Přines soubor Program.cs nebo snímek obrazovky s výstupem.

Všechno, co jsme dnes použili, je popsané na Microsoft Learn. Odkazy jsou anglicky — klidně si je nech přeložit prohlížečem, kód je stejný v každém jazyce.

Dnešek nebyl o tom naučit se nazpaměť tři algoritmy. Byl o jedné myšlence: stejný úkol se dá vyřešit chytře nebo hloupě, a ten rozdíl je vidět v číslech.

• Umíš porovnat a prohodit dva prvky a víš, proč je potřeba dočasná proměnná.
• Napsal jsi bubble sort a spočítal jsi, kolik práce ho stojí.
• Rozumíš principu rozděl a panuj — merge sort rozdělí, seřadí a slije.
• Víš, co je pivot a proč na jeho volbě u quicksortu záleží.
• Používáš Array.Sort, List.Sort a LINQ OrderBy a víš, čím se liší.
• A hlavně: umíš změřit, který postup je lepší, místo abys hádal.

Tohle je přesně to, co dělá informatik. Ne že by znal víc příkazů — ale že se umí zeptat „kolik práce to doopravdy dá?" a odpověď si ověřit.

Příště se podíváme na to, jak si všechny ty seřazené inventáře a žebříčky uložit do souboru, aby nezmizely, když program skončí.