Algoritmus

Porovnanie algoritmov

Zvyčajne existuje viac ako jeden spôsob riešenia problému. Môže existovať mnoho rôznych receptov na prípravu určitého pokrmu, ktorý vyzerá inak, ale nakoniec chutí rovnako, keď je všetko povedané a urobené. To isté platí aj pre algoritmy. Niektoré z týchto spôsobov však budú lepšie ako iné. Ak recept potrebuje veľa zložitých prísad, ktoré nemáte, nie je taký dobrý ako jednoduchý recept. Keď sa pozeráme na algoritmy ako na spôsob riešenia problémov, často chceme vedieť, ako dlho by trvalo počítaču vyriešiť problém pomocou konkrétneho algoritmu. Keď píšeme algoritmy, chceme, aby náš algoritmus trval čo najmenej času, aby sme mohli náš problém vyriešiť čo najrýchlejšie.

Pri varení sú niektoré recepty náročnejšie ako iné, pretože ich dokončenie trvá dlhšie alebo je potrebné sledovať viac vecí. Rovnako je to aj pri algoritmoch a algoritmy sú lepšie, keď sú pre počítač jednoduchšie. Vec, ktorá meria náročnosť algoritmu, sa nazýva zložitosť. Keď sa pýtame, aký zložitý je algoritmus, často chceme vedieť, ako dlho bude počítaču trvať vyriešiť problém, ktorý chceme, aby vyriešil.

Triedenie

Toto je príklad algoritmu na triedenie kariet s farbami na hromádky rovnakej farby:

1. Pozbierajte všetky karty.
2. Vyberte si kartu z ruky a pozrite sa na jej farbu.
3. Ak už existuje hromádka kariet tejto farby, položte túto kartu na túto hromádku.
4. Ak nemáte žiadnu hromádku kariet tejto farby, vytvorte novú hromádku len tejto farby kariet.
5. Ak máte v ruke ešte nejakú kartu, vráťte sa k druhému kroku.
6. Ak v ruke ešte nemáte žiadnu kartu, karty sú zoradené. Skončili ste.

Triedenie podľa čísel

Toto sú príklady algoritmov na triedenie hromady kariet s mnohými rôznymi číslami tak, aby boli čísla zoradené.

Hráči začínajú s hromádkou kariet, ktoré neboli roztriedené.

Prvý algoritmus

Tento algoritmus prechádza hromadu kariet po jednej karte. Táto karta sa porovná s ďalšou kartou v zásobníku. Všimnite si, že táto pozícia sa mení až v kroku 6. Tento algoritmus sa nazýva bublinové triedenie. Je pomalý.

1. Ak je kôpka kariet prázdna alebo obsahuje len jednu kartu, je roztriedená a vy ste skončili.
2. Vezmite si hromadu kariet. Pozrite sa na prvú kartu (vrchnú) v kope.
3. Karta, na ktorú sa pozeráte, je karta A. Pozícia, na ktorej sa karta A práve nachádza, je v balíčku P.
4. Ak po karte A nie sú v zásobníku žiadne ďalšie karty, prejdite na krok 8.
5. Ďalšou kartou v zásobníku je karta B.
6. Ak má karta B menšie číslo ako karta A, prehoďte pozície kariet A a B. Zapamätajte si, že ste to urobili. Pri výmene kariet nemeňte pozíciu P.
7. Ak je v zásobníku po pozícii P ďalšia karta, pozrite sa na ňu; vráťte sa ku kroku 3.
8. Ak ste v poslednom kole nevymenili pozíciu žiadnej karty, skončili ste; hromada kariet je zoradená.
9. V opačnom prípade sa vráťte ku kroku 2.

Príklad krok za krokom

Vezmime hromadu kariet s číslami "5 1 4 2 8" a zoraďme ju od najmenšieho čísla po najväčšie pomocou tohto algoritmu. V každom kroku algoritmus porovnáva prvky napísané tučným písmom. Vrchol kopy kariet je na ľavej strane.

Prvý priechod:
( 5 1 4 2 8 ) → {\displaystyle \to } ( 1 5 4 2 8 ) Tu algoritmus porovná prvé dva prvky a vymení ich.
( 1 5 4 2 8 ) → {\displaystyle \to } ( 1 4 5 2 8 )
( 1 4 5 2 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 ) Tieto prvky sú už zoradené, takže algoritmus ich nemení.
Druhý priechod:
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )(
1 4 2 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Teraz je už
 hromada kariet zoradená, ale náš algoritmus to nevie. Algoritmus potrebuje jeden celý priechod bez akejkoľvek výmeny, aby vedel, že je zoradený.
Tretí priechod:
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Nakoniec je pole zoradené a algoritmus sa môže zastaviť.

História

Ide o ľahko pochopiteľný algoritmus triedenia. Počítačoví vedci ho nazvali Bubble sort (bublinkové triedenie), pretože menšie prvky stúpajú nahor a v každom behu menia svoju pozíciu. Bohužiaľ, algoritmus nie je veľmi dobrý, pretože na triedenie potrebuje dlhý čas (veľa prechodov cez kopu kariet).

Druhý algoritmus

Tento algoritmus využíva inú myšlienku. Niekedy je riešenie problému náročné, ale problém sa dá zmeniť tak, že sa skladá z jednoduchších problémov, ktoré sa ľahšie riešia. Tento postup sa nazýva rekurzia. Je to náročnejšie na pochopenie ako prvý príklad, ale poskytne to lepší algoritmus.

Základná myšlienka

1. Ak na hromádke nie sú žiadne karty alebo je na nej len jedna karta, je roztriedená a vy ste skončili.
2. Rozdeľte hromadu kariet na dve približne rovnako veľké polovice. Ak je počet kariet nepárny, jedna z týchto dvoch hromádok bude mať o jednu kartu viac ako druhá.
3. Zoraďte každý z týchto dvoch zásobníkov pomocou tohto algoritmu (Pre každý zásobník začnite od položky 1 tohto zoznamu).
4. Zlúčte oba zoradené zásobníky dohromady, ako je opísané nižšie.
5. Výsledkom je zoradená kopa kariet. Ste hotoví.

Zlúčenie dvoch zásobníkov

Tento postup funguje s dvoma hromádkami kariet. Jedna z nich sa nazýva A, druhá B. Na začiatku je tretia kôpka, ktorá je prázdna a nazýva sa C. Na konci bude obsahovať výsledok.

1. Ak je zásobník A alebo zásobník B prázdny, položte všetky karty zo zásobníka, ktorý nie je prázdny, na vrch zásobníka C; tým ste skončili, zásobník C je výsledkom zlúčenia. (Poznámka: vezmite celý zásobník a položte ho na zásobník C; ak to budete robiť po jednotlivých kartách, zmení sa poradie a nebude to fungovať tak, ako by malo.)
2. Pozrite sa na vrchné karty z hromádky A a hromádky B. Kartu s nižším číslom položte na vrch hromádky C. Ak v hromádke C neboli žiadne karty, teraz v nej bude jedna karta.
3. Ak v kôpke A alebo v kôpke B zostali karty, vráťte sa ku kroku 1 a roztrieďte ich.

História

John von Neumann vyvinul tento algoritmus v roku 1945. Nenazval ho triedenie podľa čísel, ale Mergesort. V porovnaní s inými algoritmami je to veľmi dobrý algoritmus na triedenie.

Tretí algoritmus

Prvému algoritmu trvá triedenie kariet oveľa dlhšie ako druhému, ale dá sa vylepšiť (skvalitniť). Pri pohľade na bublinkové triedenie si možno všimnúť, že karty s vysokými číslami sa z vrchnej časti hromádky presúvajú pomerne rýchlo, ale kartám s nízkymi číslami v spodnej časti hromádky trvá dlho, kým sa zdvihnú (presunú na vrch). Na zlepšenie prvého algoritmu je tu nápad:

Namiesto porovnávania dvoch kariet, ktoré sú vedľa seba, sa na začiatku vyberie "špeciálna" karta. Všetky ostatné karty sa potom porovnávajú s touto kartou.

1. Začneme so zásobníkom A. Budú existovať ďalšie dva zásobníky B a C, ktoré vytvoríme neskôr.
2. Ak hromádka A nemá žiadne karty alebo má len jednu kartu, triedenie sme ukončili.
3. Z balíčka A sa vyberie karta, pokiaľ možno náhodne. Táto karta sa nazýva pivot.
4. Všetky zostávajúce karty z balíčka A sa porovnajú s týmto pivotom. Karty s menším číslom idú na kôpku B, karty s rovnakým alebo väčším číslom idú na kôpku C.
5. Ak sú nejaké karty v zásobníkoch B alebo C, je potrebné tieto zásobníky zoradiť rovnakým algoritmom (Začnite postupne od pozície 1 tohto zoznamu pre zásobník B aj zásobník C).
6. Hotovo. V zoradenej kope kariet je najprv zoradená kopa B, potom pivot a potom zoradená kopa C.

História

Tento algoritmus vyvinul C. A. R. Hoare v roku 1960. Je to jeden z najpoužívanejších algoritmov na triedenie v súčasnosti. Nazýva sa Quicksort.

Animácia, ktorá ukazuje, ako funguje bublinové triedenie


Triedenie 7 čísel pomocou druhého algoritmu Triedenie podľa čísel (Mergesort)


Tretí algoritmus na triedenie kariet. Prvok s červeným pruhom je vybraný ako pivot. Na začiatku je to prvok úplne vpravo. Tento algoritmus sa nazýva Quicksort.

Zostavenie algoritmov

Ak majú hráči karty s farbami a číslami, môžu ich zoradiť podľa farieb a čísel, ak vykonajú algoritmus "triedenia podľa farieb", potom vykonajú algoritmus "triedenia podľa čísel" pre každú farebnú kôpku a potom dajú kôpky dohromady.

Algoritmy triedenia podľa čísel sú náročnejšie ako algoritmy triedenia podľa farieb, pretože sa môže stať, že jednotlivé kroky budú musieť opakovať mnohokrát. Dalo by sa povedať, že triedenie podľa čísel je zložitejšie.

Súvisiace stránky

• Euklidov algoritmus bol objavený pred viac ako 2000 rokmi. Dokáže nájsť najväčšieho spoločného deliteľa dvoch čísel.