Serie Algoritmy

Tato serie ma za cil seznamit Vas s jednoduchymi algoritmy, ktere treba bezne pouzivate (nebo vyuzivate) a mozna o tom ani nevite. V nekolika dilech (+ bonusovka po kazdych ctyrech - na bonusovku nebudete potrebovat sbirat zadna cisla z vicek ani nic podobneho) se mimo jine dozvite, jak Saman zjisti, kolik lidi mu prijde na GeoSkorapky, jak se vyhledava v textu a jak se tridi zaznamy. Pokud Vas tohle vsechno zajima, pak je druha cast serie urcena prave Vam!

Problem trideni

Zacatek druhe casti serie bude oddychovka, kdy po Vas nebudu nic moc chtit. Zadarmo Vam ten bodik ale taky nedam, takze hura na trideni.

Problem trideni je velice casty a velice stary a proto existuje spousta algoritmu na jeho reseni a obecna problematika je pomerne dukladne prozkoumana. Zacnu jednim dulezitym tvrzenim:
Trideni N obecnych polozek trva asymptoticky nejmene N*log(N).
Tohle tvrzeni je dulezite, protoze nam rika, jak (radove) nejrychleji jsme schopni setridit data. Dukaz tohoto tvrzeni uprimne nesnasim, takze ho tu neuvedu.

Tridici algoritmy si muzeme rozdelit na dve kategorie podle asymptoticke slozitosti: na pomalejsi algoritmy se slozitosti O(N²), ktere jsou ovsem mnohem jednodussi na implementaci a pochopeni, a na algoritmy rychle, se slozitosti O(n*log(n)), ktere jsou o poznani sofistikovanejsi.

Jeste jsem zapomnel zminit jeden predpoklad, a sice, ze pokud chceme nejake polozky setridit, musime byt schopni je porovnat.

Jednoduche algoritmy

Prime trideni

... je nejjednodussi algoritmus, jaky si vubec muzeme predstavit. Mame pole nesetridenych polozek A a prazdne pole B, kam budeme setridene polozky ukladat. Postupne prochazime pole A, pri kazdem pruchodu vybereme nejvetsi (nejmensi) prvek, pridame ho na konec B a smazeme v A. To je vse - desne slozite, ze .

Prime zatrizovani

... funguje tak, ze od kraje zvetsujeme setrizenou cast pole: vezmeme n-ty prvek, zaradime ho na spravne misto mezi predchozich n-1 prvku (tim se nam velikost setrizene casti zvetsi na n) a pokracujeme stejne s (n+1)-tym prvkem. Sice nepotrebujeme skoro zadnou pamet navic (napr. prime trizeni potrebuje dvojnasobek), zato ale neustale nekam neco stehujeme (odsouvani kusu setridene casti), coz se projevi na rychlosti vypoctu; vyjimka je, pokud mame data v tzv. spojovem seznamu, pak se nic nepresouva, pouze se prepoji 2 ukazatele a je hotovo (ale spojaky bych radsi neresil...).

Priklad: (svislitko oddeluje setridenou cast)
1) 2 | 3, 1, 6, 4, 5 (zadne presuny)
2) 2, 3 | 1, 6, 4, 5 (zadne presuny)
3) 1, 2, 3 | 6, 4, 5 (museli jsme odsunout 2 a 3)
4) 1, 2, 3, 6 | 4, 5 (zadne presuny)
5) 1, 2, 3, 4, 6 | 5 (museli jsme odsunout 6)
6) 1, 2, 3, 4, 5, 6 | (museli jsme odsunout 6)
7) hotovo (je videt, ze treba 6 se nam tady presouva casteji nez je zdravo)

Bubble sort

... je o neco propracovanejsi a zajimavejsi nez prime trideni. Funguje nasledujicicm zpusobem:

1. neustale opakuj nasledujici:
   1. projdi tridene pole A a pokud A[j-1] < A[j], vymen hodnoty A[j-1] a A[j]
   2. pokud pri poslednim pruchodu nedoslo k zadne vymene, zastav cyklus

"Pomalych" algoritmu je jeste vic, ale temi se uz nebudeme zdrzovat a vrhneme se na ty rychle.

Rychle algoritmy

... jsou (az na modifikace) tri: HeapSort, MergeSort a QuickSort.

Heap-Sort

Zakladni myslenka tohoto algoritmu vyplyva z vlastnosti haldy. Jedna dulezita vlastnost je, ze po odebrani minima (tj. korene), umime zbytek "zhaldit" v logaritmickem case. Druha dulezita vlastnost je ta, ze pokud stavime haldu "odspoda", umime ji postavit v linearnim case. Algoritmus pak funguje nasledujicim zpusobem:

1. postavim haldu
2. dokud mi nejaka halda zbyva
   1. vezmu ji koren a pridam ho na konec setrideneho pole vysledku
   2. poskozenou haldu znovu "zhaldim"

Jeste prozradim, jak se provadi delete korene haldy: odeberu posledni prvek (tj. ten v nejnizsi vrstve nejvic vpravo) a jeho hodnotu vlozim do korene, nacez ho necham probublavat dolu podle pravidla o nerovnosti, dokud to, co mi zbylo, neni opet halda.

Jak je videt, trideni skutecne bezi v case O(n * log(n)): haldu mame hotovou v linearnim case a pri rozebirani n-krat "haldime" zbytek haldy, tj. n*log(n).

Mergesort

... patri mezi rekurzivni algoritmy. Rekurze je potvora a snazim se ji vyhybat, nicmene merge- a quick- sort jsou natolik zname algoritmy, ze je nemuzu vynechat. Takze jdeme na vec. Rekurzivni funkce se vyznacuje tim, ze vola sama sebe. Pouzivaji se v resenich typu "divide et impera" (rozdel a panuj), coz je presne vec, kterou pouzijeme pri merge-sortu.

Cely algoritmus funguje tak, ze na tridene pole pustime funkci mergesort. Ta vypada tak, ze pole rozdeli na dve poloviny a pokud maji vic prvku nez jeden, pusti na ne opet mergesort, aby si je setridila, jinak vraci ten jeden prvek, co ma. Takto setridene poloviny pak sleva do jednoho celku, ktery pak preda o uroven vys, kde tento setrideny kus opet poslouzi jako polovina pro slevani (popr. jako uz hotovy vystup).
Slevani funguje tak, ze ze dvou setridenych poli postupne ubiram nejmensi prvky tak, ze vzdy odeberu mensi z obou nejmensich prvku a vlozim ho do pole vysledku.

Nejsem sadista, takze pseudokodu Vas usetrim. Pokud by to nekdo opravdu chtel videt, tady je link na wikipedii: http://cs.wikipedia.org/wiki/Merge_sort - nejspis to tam bude i lip vysvetlene nez tady ode me.
Pridam par poznamek o vyuzitelnosti a zrychlitelnosti:

• mergesort je prumerne pomalejsi nez quicksort nebo heapsort
• mergesort je mnohem "prirozenejsi" / "intuitivnejsi" nez oba ostatni rychle algoritmy
• mergesort jde snadno uzpusobit na "vnejsi trideni" - trideni souboru, ktere se nevejdou cele do pameti
• mergesort jde i zrychlit: muzeme slevat vic poli (uplatnuje se hlavne pri vnejsim trideni, kdy diskove operace jsou natolik pomale, ze nas rozhodne nemusi bolet hlava ze zpomaleni vznikleho tim, ze misto obycejneho porovnani tridime) a/nebo nenechat dojit rekurzi az k poli delky 1, ale zastavit ji driv (treba na 15ti) a pole delky 15 setridit treba bubblesortem (tim se zmensi hloubka rekurze a usetri se pamet)

Quicksort

Jelikoz uz je listing az moc dlouhy a i u mergesortu si myslim, ze jsem ho nedokazal vysvetlit uplne optimalne, zcela sebekriticky prohlasuji, ze na quick si netroufam a odkazuji Vas na wikipedii, kde je velice podrobny a myslim, ze i srozumitelne napsany clanek vcetne prikladu. Timto se omlouvam vsem, ktere jsem zklamal.

Radixsort

Uplne nakonec Vam ukazu jeste jeden algoritmus, kteremu staci projit tridene pole pouze dvakrat, tj. je linearne slozity. To je na prvni pohled v rozporu s tvrzenim, ktere jsem psal na zacatku. Jenze uz na druhy pohled tu zadny rozpor neni - tvrzeni plati pro obecne prvky a radixsort funguje jenom pro velice specificke klicove prvky - takove, kterymi muzeme indexovat pole (to zalezi na prog. jazyku, ale obecne to jsou pouze prirozena cisla), navic musi mit nejaky rozumny rozsah a tento interval by take mel byt nejak rozumne "zaplneny" - tridit radixsortem 5 prvku podle klicu 1, 5, 150, 400 a 10 000 neni nejlepsi napad.
A ted uz k tomu, jak algoritmus funguje: vytvorime pole velikosti dane rozsahem klicu (v predchozim nevhodnem priklade by to bylo 1 az 10 000) a pri prvnim pruchodu nasypeme tridena data do pole podle klice (tj. polozku (5,hodnota) zpracujeme na pole[5] := hodnota). Pri druhem pruchodu pak pouze projdeme sekvencne pole a hodnoty postupne vypisujeme do vysledku (tim odstranime pripadne mezery v poli).

Finalka

Ukol bude tentokrat veskrze trapny. Dostanete seznam usporadanych dvojic (klic,hodnota) a Vasim ukolem bude tento seznam setridit podle klicu od nejmensiho k nejvetsimu; hodnoty Vam pak daji souradnice. Vim, ze to jde i bez znalosti nejakych lepsich algoritmu nez je prime trideni, ale pokud mi chcete udelat radost, vyzkousite si na tom aspon jeden z tech slozitejsich - pochlubte se tim v logu

Keska

... je velka krabicka od tic-tacu a je ulozena na miste na prvni pohled kapku odpudivem. Je nutna zvysena opatrnost a rozhodne nedoporucuji mit s sebou svoje ratolesti nebo pejsky. Asi se ted ptate proc je keska zrovna tady - je to kvuli vyhledu na udoli, ktery se od kesky otevira a aspon me se libi natolik, ze jsem prekonal i svuj odpor k autum. Tak se na me prosim nezlobte a ja za to slibuji, ze pristi dil serie bude zase v lese.

Provazej Vas Signal!