TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
45.1 ShellSort
45.2 Přihrádkové třídění (RadixSort)
45.3 Třídění slučováním (MergeSort)
45.4 Domácí úkol
45.5 V další lekci
45.1 ShellSort
V tomto díle se prokoušeme posledními třemi typy třídění, které mám v úmyslu probrat. Jsou to ShellSort, RadixSort a MergeSort. Tyto metody si probereme spíše teoreticky. Začneme tedy ShellSortem. Je to metoda poněkud zvláštní a přišel na ni jistý pan Donald Shell. Ze svých pozorování a experimentů zjistil, že prvek se v poli posune průměrně o jednu třetinu vzdálenosti. Tento algoritmus pracuje podobným způsobem jako BubbleSort, ale hlavní rozdíl je v tom, že se neporovnávají dva sousední prvky, ale prvky, které jsou od sebe vzdáleny na určitou délku. Takže se porovnává například prvek 0 s 4 a 9, prvek 1 s 5 a 10 prvek, 2 s 6 a 11 a prvek 3 s 7 případně i s 12, pokud je v poli tolik prvků. To je první průchod, a z něj vyplývá, že vzdálenost mezi prvky je 5. Další průchod se vzdálenost mezi prvky zmenší o 1. Budeme tedy porovnávat prvek 0 s prvky 3 a 7 a 11, prvek 1 s prvky 4 a 8 atd. Další průchod se vzdálenost mezi prvky opět sníží o 1, bude tedy 3. Až se pole vytřídí i cyklem, kde je vzdálenost mezi prvky 1, je hotovo. Pole musí být při prvním třídění rozděleno tak, aby vzdálenost mezi tříděnými prvky byla větší nebo rovna 1/3. Třídění prvků, které porovnáváme, probíhá tak, že když máme zvolené např. prvky 0, 3, 7, 11, tak je seřadíme od nejmenšího po největší. Napsání kódu není složité, nechám to tedy na vás.
45.2 Přihrádkové třídění (RadixSort)
Přihrádkové třízení je zvláštní v tom, že se třídí podle cifer. Pokud vezmeme například čísla trojciferná, rozdělíme je do přihrádek 0, 1, 2 … 9, a to podle jejich poslední cifry. Poté vezmeme přihrádku 0, ze které budeme vybírat čísla a přiřazovat je podle druhé cifry do přihrádek 0, 1, 2 … 9. Nebudou to ovšem ty samé přihrádky, ale přihrádky pro druhý řád. Tak budeme pokračovat i s čísly z přihrádek 1 – 9 prvního řádu. Teď postupně budeme brát čísla z přihrádek 2. řádu. Začneme opět u 0 a umístíme je do přihrádky 0 – 9 třetího řádu, a to právě podle třetí cifry. Čísla z přihrádek se berou v takovém pořadí, v jakém jsme je vložili. Použijeme tedy frontu (data, která jdou první dovnitř, jdou první ven, narozdíl od zásobníku, kde data, která jsme uložili naposledy, čteme jako první). Jako příklad uvedu cestu čísla 473. V prním rozmisťování se číslo dostane do přihrádky číslo 3. Z té je při následujícím přemístění přesunuto do přihrádky druhého řádu s číslem 7 a na závěr je přesunuto do přihrádky třetího řádu.
45.3 Třídění slučováním (MergeSort)
Poslední probíranou metodou třídění bude MergeSort. Ten pracuje s tím, že slučuje dvě již vytříděná pole v jedno setříděné pole. Metoda je tedy vhodná, pokud máme například dva záznamy a potřebujeme je setřídit v jeden setříděný. Nevýhoda MergeSortu je především v tom, že potřebujeme jedno pomocné pole. Je možné napsat to i bez něj, ale algoritmus se stává mnohem složitější.
45.4 Domácí úkol
Vaším úkolem pro tuto lekci je dokončit program na porovnání výkonnosti algoritmů.
45.5 V další lekci
Příště se konečně vrhneme na objektově orientované programování. Budeme tvořit objekty třídy, a tak dál, a tak dál. Toto téma, tedy OOP, nám zabere několik lekcí.
