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ý.
- Ak je kôpka kariet prázdna alebo obsahuje len jednu kartu, je roztriedená a vy ste skončili.
- Vezmite si hromadu kariet. Pozrite sa na prvú kartu (vrchnú) v kope.
- 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.
- Ak po karte A nie sú v zásobníku žiadne ďalšie karty, prejdite na krok 8.
- Ďalšou kartou v zásobníku je karta B.
- 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.
- Ak je v zásobníku po pozícii P ďalšia karta, pozrite sa na ňu; vráťte sa ku kroku 3.
- Ak ste v poslednom kole nevymenili pozíciu žiadnej karty, skončili ste; hromada kariet je zoradená.
- 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
- Ak na hromádke nie sú žiadne karty alebo je na nej len jedna karta, je roztriedená a vy ste skončili.
- 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á.
- 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).
- Zlúčte oba zoradené zásobníky dohromady, ako je opísané nižšie.
- 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.
- 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.)
- 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.
- 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.
- Začneme so zásobníkom A. Budú existovať ďalšie dva zásobníky B a C, ktoré vytvoríme neskôr.
- Ak hromádka A nemá žiadne karty alebo má len jednu kartu, triedenie sme ukončili.
- Z balíčka A sa vyberie karta, pokiaľ možno náhodne. Táto karta sa nazýva pivot.
- 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.
- 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).
- 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.
