intro:
-vecer, tma, svieti len monitor a blikaju ledky na pocitaci, zvuk vetrakov prerusuje hrajuca mp3ka, tukanie do klavesnice, obcasne pipnute speakera a pripadne nadavanie codera ktoremu rozpisany assemblerovsky program zasa zasegfoultoval... chyba vam to ? tak je tu pre vas dalsia (a snad nie posledna) cast blackhole programming contestu
problem:
-uloha bude o nieco zlozitejsia ako minule - ale ked sme sa tak pekne rozsortili tak pri tom ostaneme ale tentokrat budeme chciet byt rychli, cize quick takze narade je quicksort (a pravdepodobne posledny sort v conteste
zadanie:
-napisat co najmensiu implementaciu quicksortu
-mal by plnohodnotne nahradit klasicky ceckovy qsort (man 3 qsort)
-a aby to nebolo take jednoduche quicksort moze byt rychly a este rychlejsi a nas zaujima prave ten najrychlejsi (s minimalnym poctom volani memcpy) a to aj za cenu velkosti - takze pre spresnenie chceme najmensiu implementaciu najrychlejsieho quicksortu
-nemal by sa spoliehat na obsah registrov pred zavolanim a na konci by ich mal vratit do povodneho stavu
popis algoritmu:
-vyberieme si z pola nahodny prvok X a pole usporiadame tak aby pred prvkom X boli vsetky prvky ktore su mensie alebo rovne ako X a za prvkom X vsetky ktore su vacsie alebo rovne ako X
-zavolame rekurzivne qsort cast pola ktora obsahuje vsetky prvky pred X
-zavolame rekurzivne qsort cast pola ktora obsahuje vsetky prvky za X
priklad (rekurziu riesime pre jednoduchost v jednom kroku):
-mame vstupne pole
4 2 7 6 1 3 5
-ako pivot (prvox X) si zvolime (nahodne) 4
-uplatnime prvy krok algoritmu a pole zoradime tak aby vsetky prvky mensie alebo rovne ako 4 boli pre 4 a vsetky vacsie alebo rovne za 4
2 1 3 4 6 7 5
-rekurzivne usporiadame cast pola pred 4
1 2 3 4 6 7 5
-rekurzivne usporiadame cast pola za 4
1 2 3 4 5 6 7
poznamky:
-algoritmus prehadzovania prvkov pri prvom kroku algoritmu nie je specifikovany, bolo by vsak dobre minimalizovat pocet kopirovani prvkov
-velkost dat v poli nemusi byt nutne 32bitov a teda obsah jedneho prvku pola sa nemusi vojst do 32bitoveho registru
-ceckovy zdrojak vam radsej nedavam a to z dvoch dovodov - som zvedavy na vas sposob implementacie (v pripade nudze pomoze ujo google) a nerad by som aby boli vsetky riesenia take viac-menej rovnake
moje riesenie:
-bude zverejnene po skonceni sutaze a taktiez bude zverejnene to co z neho spravil v92 vratane komentarov vylepseni
vyhra:
-osvietenie, upevnenie vedomosti, mozno aj nejake tricko ked ich budeme mat vela (ehm... blackhole, hysterka, 2600, alebo nejake stare pouzite spinave derave s logom m$
cas:
-mno povedal by som ze taky mesiac je postacujuci, takze ked je dnes 15.10. tak bude stacit ked to budem mat v mailboxe 15.11. vecer o 23:59:59 lokalneho casu na serveri
outro:
-a naco to vsetko ? osvojit si asm... a nabuduce (ked nejake nabuduce bude) si ukazeme aj nejake prakticke pouzitie assembleru....
sven, sven<zavinac>hysteria<bodka>sk
v92, v92<zavinac>hysteria<bodka>sksven, v92
