Sort na několik způsobů
Tenhle článek bude tak trochu o třídění nebo jak se říká o sortění.
Kdo tyhle algoritmy zná ať si to taky klidně přečte. Pokud se vám
bude zdát, že jsou někde chyby nebo by šlo něco napsat efektivněji,
tak mě prosím nepomlouvejte, ale napište mi (thy@email.cz) ať se
přiučím.
No takže úvod máme za sebou. (uff :-)
Třídění je úloha tak klasická, že snad ani klasičtější není. Máme
množinu prvků a ty máme podle nějakého klíče setřídit (jedno zda
vzestupně nebo sestupně). Pro jednoduchost se omezím vždy na 100
čísel.
Nejznámější algoritmy jsou:
1) Hledáním maxima (minima)
2) Přímým zatříďováním
3) Bubble sort (bublinkový tříďění)
4) Quick sort
5) Merge sort
6) Heap sort (Tříďení haldou)
Radix sort
Pokud někoho vůbec nezajímají nějaký kecy a chce rovnou THE FASTEST,
tak hned zkraje řeknu, že je to Radix a že už je to nějakej pátek co
ho Buh of Píči popisoval v nějakým diskmagu. Pokud ten článek někdo
bude chtít tak mu to pošlu, ale sem to nedáme, páč by nás pak mohli
fakovat. Pokud máte doma sbírku diskmagů, tak doporučuju najít, psal
to Buh a je to tedy rychly a jednoduchy.
Hledání maxima
Máte čísla v poli a vždycky ho projdete, vyberete maximum dáte si ho na
začatek (tedy prohodíte počáteční prvek a nalezené maximum) a jedete od
znova akorát si musíte posunout začátek.
Příklad:
Posloupnost |11 15 3 8 6 7
znak | označuje aktuální začátek
1. průchod 15 |11 3 8 6 7 (prohodili jsme 15 a 11)
2. průchod 15 11 |3 8 6 7 (11 <-> 11 - takže nic)
3. průchod 15 11 8 |3 6 7 (8 <-> 3)
4. průchod 15 11 8 7 |6 3 (7 <-> 3)
5. průchod 15 11 8 7 6 |3 (6 <-> 6 - taky nic)
A jaký to je ? No algoritmus je to spíš hloupoučkej. Třídí sice na
místě (nepotřebuje přebytečnou pamět) ale pro každý maximum musíte
projít nejhůř skoro celý pole.
Přímé zatřiďování
Zase máte čísla v poli. Tentokrát, ale vemete číslo po číslu a
nejdete mu místo kam patří v už setříděný posloupnosti. No jo to je
sice hezký, ale kde vezemte tu už setříděnou posloupnost ? Použijete
malý trik, který se mi vždycky líbil. Řeknete si, že jednočlenná
posloupnost už je setříděná. Dobrý ne ? :)) Ne ? :( Dobře tak byste
na to taky přišli, ale mě to připadá vychytralý.
Posloupnost 11 |15 3 8 6 7
znak | označuje, kam až sahá setříděná posloupnost
1. průchod 11 15 |3 8 6 7 (prošli jsme celou setříděnou
posloupnost a zjistili, že 15 patří za 11)
2. průchod 3 11 15 |8 6 7
3. průchod 3 8 11 15 |6 7
4. průchod 3 6 8 11 15 |7
5. průchod 3 6 7 8 11 15
Tohle je podobný předchozímu, obzvláště to zařazování není nic pro
mne.
Bublinkové třídění
Tohleto asi všici znáte. Když jsem o tom slyšel poprvý myslel jsem,
že je to ta nejvymakanější věc. Zkrátka jde o to dát o jeden gól víc
než soupeř... Eh to sem nepatří. Procházíte celou posloupnost a
porovnáváte sousední prvky jestli jsou ve správném uspořádání ( >
nebo < ) no a když nejsou tak je prohodíte. Děláte to tak dlouho až
už neni co prohodit potom skončíte. Taky každý projetí posloupnosti
nemusíte dělat až dokonce. Stačí kontrolovat v každým projetí o 1
prvek míň.
Posloupnost 11 15 3 8 6 7
1.průchod: 11<15 3 8 6 7 o.k.
11 3<15 8 6 7 prohodili jsme 3 a 15
11 3 8<15 6 7 8 <-> 15
11 3 8 6<15 7 6 <-> 15
11 3 8 6 7 15 7 <-> 15
maximální prvek 15 nám "probublal" až na konec, proto bublinky
2. průchod 3 8 6 7 11 15
3. průchod 3 6 7 8 11 15
4. průchod 3 6 7 8 11 15
Při 4. průchodu jsme nic nezměnili a tedy konec.
Quick sort
Tenhleten je založenej na rekurzi. Jde o to, že máte proceduru,
která má na vstupu posloupnost. Když má ta posloupnost jen jeden
prvek tak nedělá nic. Pokud má víc jak jeden tak si zvolí tzv.
pivota což je jeden z prvků posloupnosti. Poté projíždí posloupnost
na vstupu zároveň odleva i odprava dokud nenajde nalevo prvek vetší
než pivot a na pravý prvek menší než pivot. Ty dva potom prohodí a
pokračuje až dokud se indexy procházení zleva a zprava nesetkaj.
Tím, že se setkaj se posloupnost rozdělí na 2 podposloupnosti (ne
nutně půlky) a na ty se pak zavolá ta samá procedura.
Myslim, že nejlíp se to dá pochopit z přiloženého zdrojáku v Basicu.
Merge sort
Opět jeden rekurzivní a možná i trochu podobnej. Tady danou
posloupnost procedurou rozdělíte na poloviny a na ně opět poštvete
tuto proceduru. Je-li posloupnost jednočlenná neděláte nic. Takže po
zavolání této procedury máte 2 setříděné podposloupnosti a zbývá už
je jenom slít (merge). To děláte tak, že jedete po obou
posloupnostech a vybíráte vždy ten menší a ten si dáváte do
pomocného pole. (No klidně to dělejte jak vás napadne) Tenhle sort
mam docela rád. Má jen jednu malou vadu (pro mě). Až příliš využívá
předávání parametrů procedurám a tedy v assembleru bylo nad mé síly
ho napsat :(( Sorry
Heap sort
To je asi nejlepší třídění založený na porovnávání prvků. Rychlý je
to stejné jako Quicksort jenže to třídí na místě. Quicksort ne páč
si musí pamatovat hranice podposloupností. Halda je binární strom.
Vsuvka: Co je binární strom
No horko těžko jsem to pochopil, a tak nevim jestli ode mě
pochopíte. Strom je datová struktura, kde každý prvek může mít
několik synů (binární jich má maximálně 2) a jen jediného otce.
Každý strom má jeden kořen - tedy jak správně tušíte je to prvek,
který nemá otce. No a prvky, které nemají syny jsou listy.
Malý příklad:
o -kořen -\
/ \ \
o o - } toto jsou tzv. hladiny
| / \ /
o o o -listy -/
Zatím si to můžete představovat tak, že prvky mají nejen hodnotu,
ale i ukazatele na své syny (obvykle to tak je - u haldy to není
potřeba).
No a teď ta halda. Jak jsem říkal je to binární strom s nějakými
vlastnostmi navíc:
1) Každý prvek je menší nebo roven svým synům.
2) Každa hladina kromě poslední je zaplněná bezezbytku (to pro náš
příklad platí)
3) Poslední hladina se zaplňuje zleva (to pro náš příklad neplatí)
Musel by vypadat takto:
o
/ \
o o
/ \ |
o o o
Díky podmínce 1 je v kořeni minimální hodnota.
Takže jakmile máme haldu postavenou, vybereme hodnotu v kořeni a
znovu předěláme haldu (aby zůstala haldou) a znova a znova dokud ji
celou nevybereme. No a jak se staví halda ? No já to dělám tak, že
postupně přidávám jeden prvek za druhým. A to tak, že ho přidám na
nové místo v haldě. Tedy buď na "nejpravější" volné místo ve volné
hladině nebo na první místo v hladině nové. Takhle když to píšu se
mi to zdá složitý, ale díky tomu, že haldu budeme mít uloženou v
poli (aha to sem eště neřek), je místo, kam budeme nový prvek dávat
prostě na konci pole. Ještě k tomu poli - synové jakéhokoli prvku v
poli (třeba s indexem x - v blitzu: pole(x) ) mají indexi 2*x resp.
2*x+1 ( pole(2*x), pole(2*x+1) ). No takže máme přidanej prvek jenže
v tuhle chvíli jsme porušili pravidla haldy, poněvadž tatík našeho
přidaného syna může být větší. No takže to zkontrolujeme (+
zkotrolujeme jestli nějakej otec vůbec je) a když jsou tak jak
nemají být no tak je prohodíme. S druhým synem se nezatěžujeme,
protože to už mělo být (a bylo:) v pořádku předtím a výměnou se to
nemohlo zpackat. Ale tím jsme mohli porušit Takže malý příkladek
(stavění):
3
/ \
/ \
5 12
/ \ / \
7 9 13 16
/ \ |
11 10 23
Takovouhle už máme haldu a přidáváme číslo 2
3 3 3
/ \ / \ / \
/ \ / \ / \
5 12 5 12 2 12
/ \ / \ / \ / \ / \ / \
7 9 13 16 7 2 13 16 7 5 13 16
/| / \ /| / \ /| / \
11 10 23 2 11 10 23 9 11 10 23 9
Dáme 2 na konec 2<->9 2<->5
2
/ \
/ \
3 12
/ \ / \
7 5 13 16
/| / \
11 10 23 9
2<->3
No a konec protože už není otec.
Vsuvka: Složitost takového stavění je O(N*log(N)), ale dá se prý
postavit se složitostí O(N), to bohužel neumím a prosím pokud víte,
napište mi jak to děláte.
Halda je hotová a za náma je teprve půlka :( Dál už to ale bude
podobný.
Jak už jsem řek, teď vybíráme až do úplného vyčerpání (haldy nebo
Amčy). Neřek jsem, ale jak se halda spraví po vybrání toho prvku. No
místo něj dáme prvek poslední a zmenšíme si počitadlo prvků v haldě.
Poté procházíme haldu podobně jako při budování akorát, že zeshora.
V každém kroku vybereme menšího ze synů prvku a porovnáme je. V
případě, že otec je větší než syn prohodíme jejich hodnoty a v
příštím kroku kontrolujeme syna. Tak postupujeme dokud má prvek
menšího syna (má-li ho vůbec). A halda je opravená.
Radix sort
Neboli přihrádkové třídění je nejrychlejší. Je to proto, že není
založený na porovnávání čísel, ale na jakémsi (velmi chytrém)
zařazování čísel do "přihrádek". Řekněme, že máme třídit max.
čtyřmístný čísla v 16-ový soustavě. Tedy vlastně wordy. Takže třeba:
16A4 1E71 95B1 C9A5 0253 48FF 2563 Uděláme si 16 přihrádek (je to
podle půlbytu - tedy jedné cifry). Nejprve je dáme do přihrádky
podle hodnoty v 1. cifře:
přihrádky:
0- 8-
1- 1E71, 95B1 9-
2- A-
3- 0253, 2563 B-
4- 16A4 C-
5- C9A5 D-
6- E-
7- F- 48FF
Uložíme si je stranou v pořadí v jakým jsou a znovu je zařadíme do
přihrádek tentokrát, ale podle druhé cifry. 2. možnost je, že máme 2
tabulky a přeřazujeme z jedné do druhé (tak to dělá Buh).
přihrádky:
0- 8-
1- 9-
2- A- 16A4, C9A5
3- B- 95B1
4- C-
5- 0253 D-
6- 2563 E-
7- 1E71 F- 48FF
Podle 3. cifry:
0- 8- 48FF
1- 9- C9A5
2- 0253 A-
3- B-
4- C-
5- 2563, 95B1 D-
6- 16A4 E- 1E71
7- F-
Podle 4. cifry:
0- 0253 8-
1- 16A4, 1E71 9- 95B1
2- 2563 A-
3- B-
4- 48FF C- C9A5
5- D-
6- E-
7- F-
Setříděné: 0253,16A4,1E71,2563,48FF,95B1,C9A5
Závěr
Většinu algoritmů, které jsem tady popsal můžete najít v knize Pavla
Topfera "Algoritmy a programovací techniky". Čerpal jsem z ní možná
víc než je zdrávo, ale sám jsem měl při chápání těchto algoritmů
nejasnosti a ty jsem se snažil tady rozvíst víc. Reakce pište na
thy@email.cz
Thierry von HLA