potrebuje 2-násobok veľkosti poľa

postupuje poľom zľava i sprava, zotrieďuje proti sebe 2 neklesajúce postupnosti, výsledok sa ukladá do cieľového poľa a počíta sa počet vzniknutých postupností

končí, keď vznikne jedna cieľová postupnosť

húpačkový mechanizmus

nestabilná

nechová sa prirodzene

časová zložitosť je linearitmická

video: http://www.youtube.com/watch?v=GCae1WNvnZM

řazení polí pomocou zoznamov

najprv zreťazíme neklesajúce postupnosti do zoznamu a vložíme ich začiatky do zoznamu začiatkov

v ďalšom cykle zoberieme zo zoznamu začiatky dvoch zreťazených postupností, zotriedime ich a vznikne 1 neklesajúca postupnosť, tej začiatok vložíme na koniec zoznamu

pokračujeme dovtedy, kým nie je v zozname už len 1 začiatok neklesajúcej zreťazenej postupnosti

pracuje bez presunu položiek

potenciálne stabilná (ale je to dosť komplikované)

síce povedal, že to vôbec nemusíme vedieť, ale…

řazení triedením

počítačévá verzia řazení derných štítkov v triediacich strojoch

je založený na BCD

pracuje bez presunu položiek

od najnižšiehorádu po najvyšší (najprv jednotky, potom desiatky, potom stovky…)

toto skúša: v prvom priechode idem poľom prvok po prvku a pridávam ho do zoznamu podľa toho, akú hodnotu má rád, ktorý skúmam (1 do 9…) zoznamy spojím do jedného zoznamu, tým mám zoznam neklesajúcich prvkov (podľa poslednej číslice), potom to prechádzam znovu, ale teraz to už nie je podľa indexu, ale podľa ukazateľov

stabilná

principiálne má lineárnu zložitosť ⇒ teoreticky patrí k najrýchlejším algoritmom (ale práca s BCD)

video: http://www.youtube.com/watch?v=50_TCQGjNJc