Informatika pro kombinované lyceum/Řadicí algoritmy

Jak používat klasifikační nálepkuTato cvičná stránka je součástí projektu:
střední škola
Příslušnost: skupinová

Řadicí algoritmyEditovat

Algoritmy, které se používají na seřazování nějakého seznamu (nejlépe číselného nebo abecedního), se nazývají algoritmy řadicí, či nepřesněji algoritmy třídící.

Takových algoritmů existuje celá řada. Některé jsou na jisté operace efektivnější než jiné, ale o tom později.

Základní principy řadicích algoritmůEditovat

Principielně nejzákladnější druhy řadicích algoritmů:

Iterativní algoritmyEditovat

Tyto algoritmy mají nastavený nějaký postup, který opakovaně vykonávají, dokud se nedoberou ke správnému výsledku. Mezi iterativní algoritmy patří například Bubblesort, Shellsort, Selectsort, nebo Insertsort.

Rekurzivní algoritmyEditovat

Rekurzivní algoritmy fungují tak, že celek rozdělují na menší části, ty zase na menší a takhle pořád dokola, dokud nejsou hodnoty seřazeny. Poté stačí malé části zase spojit dohromady. Mezi tyto algoritmy patří třeba Mergesort nebo Quicksort.

Druhy řadicích algoritmůEditovat

Insertion sortEditovat

Tento algoritmus funguje na principu porovnávání. Časově je nejefektivnějším algoritmem z iterativní skupiny.

Select sortEditovat

Tento algoritmus se nejčastěji využívá pro řazení menších skupin, protože časově není až tak efektivní.

Bubble sortEditovat

V tomto algoritmu se vždy velikostně porovnávají dva sousedi. Ten větší jde na jednu stranu, menší na druhou. Opakováním tohoto kroku u každé dvojičky postupně vznikne správně seřazená řada. Prakticky se Bubble sort moc nevyužívá, protože potřebuje hodně času.

Shell sortEditovat

 
schéma principu Shellsortu

Shellsort funguje hodně podobně jako Insertsort. S tím rozdílem, že Shellsort neporovnává vždy dalšího souseda, ale porovnává prvky v jistých rozestupech. Přičemž s každým dalším opakováním se tento rozestup o něco málo zmenší. Tento algoritmus je rychlý.

Merge sortEditovat

V tomto algoritmu je využita metoda rozděl a panuj.

Quick sortEditovat

Quicksort je jedním z nejpoužívanějších algoritmů pro jeho jednoduchost.

 
Jak přesně funguje Quicksort?









Odkazuji zde na stránky algoritmy a třídící/řadící algoritmy, na kterých jsem sama nejlépe pochopila, jak to celé funguje. Můžete si všimnout, že u každého algoritmu je možno pustit si vizualizaci, aby i ti, kteří si popis těžko dostávají do hlavy, si dokázali něco představit. Pokud stále tápete, odkazuji Vás na maďarskou skupinu Algorithmics, kteří ztvárnili tyto řadicí algoritmy pomocí tance. Videa jsou k dispozici na YouTube zde.

Účinnost řadicích algoritmůEditovat

Ne všechny algoritmy jsou vždy stejně účinné. Záleží jen na nás, jestli potřebujeme, aby algoritmus zvládl úlohu vyřešit za co nejkratší čas, nebo snad aby nám celý program zabíral co nejméně místa. Zde je odkaz na stránku, kde se člověk může podívat a trochu si pohrát s tím, jak různé algoritmy (i více naráz, podle toho, co si vyberete) řeší různé úlohy.

Odkazy pro možnost dalšího studia řadicích algoritmůEditovat

http://www.itnetwork.cz/algoritmy/razeni

Již výše zmíněné stránky: https://www.algoritmy.net/article/1240/Algoritmus a http://www.itnetwork.cz/algoritmy/razeni

http://www.sorting-algorithms.com/