V tomto seriálu se nebudeme učit žádné převratné funkce, které nám .NET Framework nabízí, ale pokusíme se naučit se "programátorsky myslet" a být schopni řešit různé úlohy, například jak setřídit spoustu čísel nebo najít nejkratší cestu v mapě, kterou nám někdo zadá. Tento seriál je hlavně ze začátku určen začátečníkům, pokud nějaké zkušenosti s programováním máte, pravděpodobně zde nenaleznete nic nového. Je potřeba znát základy jazyka VB.NET, doporučuji přečíst si alespoň několik prvních dílů seriálu VB.NET pro úplné začátečníky, určitě je třeba chápat cykly a pole.
Každá úloha mívá mnoho řešení a jenom některá z nich jsou dobrá. Některé řešení potřebuje spoustu paměti, ale je rychlé, jiné zase paměti potřebuje méně, ale o to je pomalejší, a některé vyžaduje paměti málo a je rychlé, ale programovali bychom ho týden, což také někdy nechceme. Proto se naučíme, jak je které řešení dobré, a jak vybrat to nejlepší. Každé se totiž hodí v jiné situaci.
Začínáme
Spusťte si Visual Studio a vytvořte nový projekt, tentokráte ovšem typu Console Application, ten nám bude bohatě stačit. V tomto díle budeme jenom třídit pár čísel, žádné uživatelské rozhraní nebude potřeba.
Visual Studio nám vygenerovalo tzv. modul. Je to soubor, do kterého můžeme psát kód, deklarovat v něm procedury, funkce, proměnné atd. Máme již nachystanou proceduru s názvem Main, do které program napíšeme.
Konzolové aplikace totiž fungují tak, že v projektu najdou proceduru Main (hledají tam, kde jim to řeknete, dá se to nastavit ve vlastnostech projektu), provedou vše, co v ní je, a potom skončí. Jakmile se tedy dorazí na konec procedury Main, program se ukončí. Vše, co chceme udělat, tedy musíme napsat do procedury Main, samozřejmě si můžeme většinu funkcionality nacpat do jiných procedur, ale volat je musíme z procedury Main.
Data, se kterými budeme pracovat
Dnes si budeme hrát celou dobu s jedním polem čísel, jeho deklarace je zde, tak si ji můžete zkopírovat nad proceduru Main. Je to normální jednorozměrné pole celých čísel.
Dim data() As Integer = {12, 1, 13, 5, 24, 26, 17, 4, 7, 10, 9, 24, 28, 9, 16}
Zahřívací úloha - nalezení největšího čísla
Jen tak pro začátek si zkuste sami napsat do procedury Main program, který pole projde a na konci vypíše největší číslo, které v poli našel. Připomínám, že první prvek pole data se čísluje od nuly a počet prvků zjistíte z data.Length, rozhodně čísla nepočítejte a nedávejte do kódu počet čísel natvrdo, zjistěte jej z data.Length.
Nakonec procedury Main si přidejte tyto dva řádky:
Console.WriteLine(nejvetsi)
Console.ReadKey()
První z nich na konzoli vypíše hodnotu proměnné nejvyssi, kterou našel, druhý počká na stisk klávesy. Bez něj by program vypsal výsledek a tím došel na konec procedury Main, takže by nám hned skončil a my si výsledek nestihli přečíst. Console.ReadKey počká, až uživatel stiskne klávesu, a pak se teprve pokračuje vykonáním dalšího řádku, v našem případě program po stisku klávesy skončí.
Pokud jste hlavičku trápili, ale nepovedlo se vám najít nejvyšší číslo v poli, zde je ukázkový kód:
Dim nejvetsi As Integer = Integer.MinValue 'nemůže zde být 0, nefungovalo by to, kdyby v poli byla jen záporná čísla; Integer.MinValue vrací nejmenší možnou hodnotu proměnné typu Integer
For i As Integer = 0 To data.Length - 1
If data(i) > nejvetsi Then nejvetsi = data(i)
Next
Funguje to velmi jednoduše, do proměnné nejvetsi si ukládáme největší číslo, které jsme zatím našli. Procházíme celé pole (od 0 do počtu prvků - 1, protože se číslují od nuly a ne od jedničky). Pokud je právě testované číslo větší než to v proměnné nejvetsi, čili největší, které jsme doposud našli, tak ho proměnné nejvetsi uložíme. Když dojdeme na konec cyklu, bude v proměnné nejvetsi největší číslo, které se v poli vyskytovalo.
Je to úplně stejné jako když byste měli 100 papírků a měli najít ten, co je největší. Také je budete brát postupně a budete si u sebe nechávat ten největší, který jste zatím nalezli. Když narazíte na nějaký větší, ten, co jste až dotěď měli, zahodíte do hromady zpracovaných a necháte si ten nově nalezený. A v proměnné nejvetsi je právě ten, co máte u sebe.
Cvičení č. 1
Zkuste nyní prográmek upravit tak, aby našel nejmenší číslo v poli. Proměnnou nejvetsi přejmenujte na nejmensi, tady se hodí pěkná vlastnost Visual Studia. Klikněte na proměnnou nejvetsi pravým tlačítkem a zvolte možnost Rename.... V okně zadejte slovo nejmensi a Visual Studio proleze celý projekt a proměnnou přejmenuje všude. U tohoto programu je to skoro rychlejší udělat ručně, ale u velkých programů se to hodí.
Druhou úpravou bude asi logicky otočení znaménka nerovnosti, protože hledáme nejmenší číslo. Ale to nebude stačit. Rozmyslete a vyzkoušejte, proč nebude a co udělat, aby to stačilo.
Prohození dvou prvků
Nyní budeme v poli chtít prohodit dva prvky, například třetí a šestý. Pokud víte, jak na to, tak je to skvělé, pokud ne, ukážu velmi jednoduchý příklad. Máte tří sklenice A a B, v první je limonáda a ve druhé pivo. Jak to udělat, aby v první bylo pivo a ve druhé limonáda? No jednoduše, vezmeme si sklenici C, do ní odlijeme limonádu, pivo nalejeme z B do A a nakonec limonádu z C do B. V praxi je lepší sklenice vypláchnout, ale to se nás v programování netýká.
Dim c As Integer = data(2)
data(2) = data(5)
data(5) = c
Tento kód nám přehodil 3. a 6. prvek v poli data. Pokud vás napadlo data(2) = data(5) a pak data(5) = data(2), je to špatně, je to jako kdybyste ve skutečnosti limonádu vylili na zem a místo ní nalili pivo. Už ale nemáte tu limonádu, kterou chcete mít ve sklenici B. Přiřazením data(5) do data(2) se hodnota, který tam byla, nenávratně ztratí. Musíme si ji před tím uložit do proměnné c, pak je to v pořádku.
Cvičení č. 2
Pokud se vrátím k předchozímu příkladu se sklenicemi, kdo dokáže vyměnit limonádu a pivo bez třetí sklenice C či jiné nádoby, je machr. S olejem a vodou by to už ale šlo, ty se tak snadno nesmíchají. V programování se dvě čísla dají prohodit i bez třetí proměnné, zkuste si to rozmyslet, stačí k tomu sčítání a odčítání. S něčím jiným než s čísly by to šlo ale už dost těžko.
Jak pole čísel setřídit?
Metod, jak třídit data, je celá řada. Jak už jsem říkal, některé jsou lepší a některé horší. Špatnou vlastností těch dobrých je to, že jsou složitější, takže se na ně dostane až ve druhém díle tohoto seriálu. Teď si ukážeme dva způsoby třídění, které se v praxi moc nepoužívají, protože jsou pomalé, jsou ale dobré pro výukové účely.
Třídění výběrem
Třídění výběrem (anglicky select sort) je asi nejotročtější třídění, které se dá vymyslet a použít v praxi. Představte si, že máte 1000 papírků označených čísly. A vždycky z nich vyberete ten nejmenší a šoupnete ho na začátek. Pak vyberete zase ten nejmenší ze zbytku a dáte jej za ten první. A tak se postupuje až do konce.
Jak to bude fungovat u nás? Vezmeme pole od 1. do posledního prvku a najdeme v nich prvek nejmenší. Dávat ho pryč do vedlejšího pole by bylo zbytečně složité a navíc bychom si museli pamatovat, že už v tom prvním poli není, což také není příliš elegantní. Místo toho ho vezmeme a prohodíme s prvkem, který nám "překáží" na místě, kam ten nejmenš patří, tedy na začátku. Nejmenší prvek tedy máme na začátku a ten, který tam byl původně, je teď kdoví kde v poli. To nám ale tak moc nevadí.
Vezmeme nyní pole až od 2. prvku a najdeme v něm ten nejmenší. Prohodíme ho s tím, co byl na druhém místě, a takhle pokračujeme dál. Postupně vybíráme z menšího a menšího úseku a nalezené nejmenší prvky dáváme na začátek. Rozmyslete si, že to funguje a že na konci budeme mít pole setříděné od nejmenšího prvku po největší. A zkuste si nejdřív tento typ třídění napsat sami, chce to trochu zkoušení a přemýšlení. Na konec procedury Main si přidejte tento kód, který vypíše pole data, abyste si mohli zkontrolovat, jestli je setříděné správně.
'vypsat setříděné pole
For i As Integer = 0 To data.Length - 1
Console.Write(data(i) & " ")
Next
Console.ReadKey()
Celý program na třídění výběrem je zde, samotné napsání je už trochu složitější, vyžaduje dva cykly v sobě:
Sub Main()
'projít celé pole kromě posledního prvku, ten je už zbytečné zpracovávat
For i = 0 To data.Length - 2
'najít nejmenší prvek z ještě nezpracovaných (začínáme tedy od i)
Dim nejmensi = i 'proměnná nejmensi tentokrát neobsahuje hodnotu nejmenšího prvku, ale jeho index v poli
For j = i To data.Length - 1
If data(j) < data(nejmensi) Then nejmensi = j
Next
'prohodit nejmenší nalezený prvek s i-tým prvkem
Dim tmp = data(nejmensi)
data(nejmensi) = data(i)
data(i) = tmp
Next
'vypsat setříděné pole
For i As Integer = 0 To data.Length - 1
Console.Write(data(i) & " ")
Next
Console.ReadKey()
End Sub
Je nutné si uvědomit, že v každém průchodu vnějšího cyklu hledáme nejmenší prvek od i až do konce a jekmile jej najdeme, dáme ho na pozici i (v prvním průchodu ho dáváme na pozici 0, v dalším na 1 atd., přesně to sedí). Při vyhledávání nejmenšího je v tomto případě praktičtější pamatovat si pouze index, tedy pořadí prvku v poli data, než jeho hodnotu. Při prohazování totiž potřebujeme vědět, kde prvek byl.
Je zde také částečně odpověď na otázku z prvního cvičení. Při vytvoření proměnnou nejmensi nastavuji na hodnotu i, tedy na index prvního prvku, který budu porovnávat. Pokud bude první testovaný prvek nejmenší, nic se nestane, a pokud v průběhu najdeme menší, tak se jeho index do proměnné nejmensi uloží. Takže to ničemu nevadí a nesmíme tam dát nulu, protože od druhého kroku je na nulté pozici pole nejmenší prvek a menší bychom již nenašli. Vnitřní cyklus by tedy ve skutečnosti mohl běžet od i + 1, protože podmínka v prvním průchodu nebude nikdy splněna, proměnné j a nejmensi mají stejnou hodnotu, tím pádem porovnáváme stejný prvek. Ale je to detail.
Poslední připomínka, nemusíme procházet vnejší cyklus až do data.Length - 1, stačí o jednu méně. Pokud totiž správně zařadíme všechny prvky kromě posledního, tak poslední bude už nutně na správném místě také a není potřeba na něj sahat, nikde jinde být totiž nemůže.
Cvičení č. 3
Přepište tento program tak, aby nejprve řadil sestupně, tedy od největšího po nejmenší, a pak aby třídil opět vzestupně, ale pomocí hledání největších prvků, tzn. najdete největší a dáte ho na poslední místo, pak najdete největší ze zbytku a dáte jej před na předposlední pozici atd.
Třídění bubláním
Druhý způsob třídění čísel má úplně jinou základní myšlenku. Tento algoritmus se dá vylepšit různými optimalizacemi, jedna bude jako další cvičení. Hlavní idea je taková, že procházíme pole od začátku do konce a když narazíme na dvojici, která je seřazená špatně, tak ji prohodíme. Sledujeme tedy dvojice prvků a když vidíme větší číslo před menším, prohodíme je mezi sebou. Jakmile dojdeme na konec, ještě ovšem nemáme vyhráno. Prohozením jsme totiž mohli narušit dvojici předchozí, musíme tedy pole procházet znovu a znovu, dokud nalézáme dvojice, které je nutné přehodit. Až nakonec projdeme pole a zjistíme, že jsme již žádnou dvojici přehazovat nemuseli, a v takovém případě můžeme skončit, víme už, že pole bude setříděné.
Tomuto algoritmu se říká třídění bubláním (anglicky bubble sort), protože malá čísla nám z konce postupně probublávají na začátek, až se někde usadí. Opět si tento algoritmus zkuste napsat, v praxi budete mít jednu proměnnou, která si bude pamatovat, jestli jste v posledním průchodu pole něco přehazovali nebo ne. Dokud tato proměnná bude True, musíte pole procházet od začátku do konce a hledat dvojice k prohození. Když nějakou prohodíte, nastavíte si proměnnou na True, nezapomeňte ji ale před každým průchodem nastavit opět na False, aby vám program někdy skončil.
A jak hledat sousední špatně seřazené dvojice? No třeba tak, že procházíte cyklem od 0 do data.Length - 2 a kontrolujete vždy prvky i a i + 1. Pokud je prvek na pozici i větší, tak tyto dva prohodíte. Procházíme pouze do data.Length - 2, protože v podledním průchodu otestujeme prvky data.Length - 2 a data.Length - 1, čili dva poslední. Po sobě jdoucích dvojic je totiž o jednu méně než prvků pole.
Pokud se vám algoritmus napsat nepodařilo, tady máte zdrojový kód:
Sub Main()
Dim nesetrideno As Boolean = True
'procházet, dokud pole je nesetříděné
While nesetrideno
nesetrideno = False 'pole může už být setříděné
'projít všechny po sobě jdoucí dvojice
For i = 0 To data.Length - 2
If data(i) > data(i + 1) Then
'pokud nejsou prvky ve dvojici seřazené, prohodit je
Dim tmp = data(i + 1)
data(i + 1) = data(i)
data(i) = tmp
'a nastavit, že pole ještě nemusí být setříděné, mohli jsme narušit předchozí dvojici
nesetrideno = True
End If
Next
End While
'vypsat setříděné pole
For i As Integer = 0 To data.Length - 1
Console.Write(data(i) & " ")
Next
Console.ReadKey()
End Sub
Cvičení č. 4
Tento algoritmus se dá zoptimalizovat mnoha způsoby, například tak, že po prohození zkontroluje, jestli se neporušila předchozí dvojice. Takže se k ní v dalším průchodu cyklem vrátí (změní proměnnou i, což mimochodem v některých programovacích jazycích konkrétně u For cyklu nejde, ale ve Visual Basicu ano). Výhodou tohoto způsobu je to, že odpadá vnější While cyklus a proměnná nesetrideno. Jakmile totiž For cyklus skončí, pole už bude setříděné. Na druhou stranu existují řádově rychlejší algoritmy, tato optimalizace sice pomůže, ale ne nijak výrazně. O tom ale až příště.
Závěrem
Pokud byl na vás tento díl příliš jednoduchý, nezoufejte, v dalších dílech bude přituhovat. Rozhodně doporučuji abyste si vše, co je v tomto článku nastíněno, zkusili napsat sami. Dá to trochu práce, ale je to nejlepší cvičení. Bez "programátorského přemýšlení" se neobejdete.
Kdo vyřeší všechna cvičení a jako první mi mailem (herceg [uzenáč] vbnet [tečka] cz) pošle správná řešení, tomu na oplátku pošlu knížku Visual Basic 2008: Build a program NOW od nakladatelství Microsoft Press, kterých nám několik poskytla společnost Microsoft Česká republika jako drobné odměny pro čtenáře. Bohužel je v angličtině, ale alespoň se procvičíte a budete mít motivaci se tento jazyk naučit. Bez něj se stejně v programování neobejdete.
To je pro tento díl vše, doufám, že se vám bude seriál líbit. Je to takové volné pokračování seriálu VB.NET pro začátečníky, kde už stejně není moc jak pokračovat.