Изворни код странице Flešsort

'''Flešsort''' ({{jez-eng-lat|Flashsort}}) je distributivni algoritam sortiranja, koji ima [[линеарно време|linearnu složenost]] '''''O(n)''''', za ravnomerno raspoređene skupove podataka i zahteva relativno malo dodatne memorije. Originalni rad objavio je Karl-Dietrich Neubert<ref name="neubert_journal">{{cite journal |last=Neubert|first=Karl-Dietrich |year=1998|title=The Flashsort Algorithm |journal=Dr. Dobb's Journal |url=http://www.ddj.com/architect/184410496 |accessdate = 6. 11. 2007.|pages=123}}</ref>, 1998. godine.

== Koncept ==

Osnovna ideja koja stoji iza flešsort algoritma je da ako imamo skup podataka sa poznatom raspodelom, možemo odmah da procenimo gde će element biti smešten nakon sortiranja, ukoliko je opseg skupa poznat. Na primer, ako imamo ravnomeran skup podataka, gde je najmanji element 1, najveći 100, a 50 se nalazi u skupu, razumno je pretpostaviti da će 50 biti blizu sredine skupa nakon sortiranja. Ova približna pozicija se naziva klasa. Ako imamo brojeve od 1 do ''m'', klasa elementa '''''Ai''''' se računa kao:

&nbsp;&nbsp;<math>K(A_i) = 1+\textrm{INT}\left((m-1)\frac{A_i-A_\textrm{min}}{A_\textrm{max}-A_\textrm{min}}\right)</math>

gde je '''''A''''' ulaz skupa. Opseg pokriven svakom od klasa je jednak, izuzev poslednje klase koja uključuje samo maksimum(e). Klasifikacija osigurava da je svaki element klase veći od bilo kog elementa niže klase. Ovo delimično raspoređuje podatke i smanjuje broj inverzija. Zatim se na klasifikovani skup primenjuje sortiranje umetanjem. Dokle god su podaci ravnomerno raspoređeni, veličina klase će biti stalna i sortiranje umetanjem će biti efikasno.

== Memorijski efikasna implementacija ==

Kako bi se flašsort izvršavao sa svojim malim memorijskim izdacima, algoritam ne koristi dodatne strukture podataka kako bi smestio klase. Umesto toga, smešta gornje granice svake klase ulaznog niz '''''A''''' u pomoćni vektor '''''L'''''. Ove gornje granice su napravljene računanjem broja elemenata u svakoj klasi i gornja granica klase je broj elemenata u toj klasi i svakoj klasi pre nje. Ove granice služe kao pokazivači na klase.

Klasifikacija se implementira kroz seriju ciklusa, gde je vođa ciklusa uzet iz ulaznog niza '''''A''''' i njegova klasa je izračunata. Pokazivači u vektoru '''''L''''' su korišćeni da umetnu vođu ciklusa u pravu klasu, a pokazivač klase u '''''L''''' se umanjuje nakon svakog umetanja. Ubacivanje lidera ciklusa će izbaciti još jedan element iz niza '''''A''''', koji će biti klasifikovan i ubačen na drugu lokaciju i tako dalje. Ciklus se završava kada se element ubaci na početnu poziciju vođe ciklusa.

Jedan element je validni vođa ciklusa ako još uvek nije bio klasifikovan. Kako algoritam iterira kroz niz '''''A''''', prethodno klasifikovani elementi se preskaču, a neklasifikovani se koriste da iniciraju nove cikluse. Moguće je razlikovati da li je element bio klasifikovan ili ne bez korišćenja dodatnih oznaka: jedan element je klasifikovan ako i samo ako je njegov indeks veći od vrednosti pokazivača klase u '''''L'''''. Da bismo ovo dokazali, razmatramo tekući indeks niza '''''A''''' koji algoritam obrađuje. Neka je taj indeks '''''i'''''. Elementi od '''''A'''''<sub>'''''0'''''</sub> do '''''A<sub>i-1</sub>''''' su već klasifikovani i umetnuti u odogvarajuću klasu. Pretpostavimo da je '''''i''''' veće od trentunog pokazivača na klasu '''''A<sub>i</sub>'''''. Sada pretpostavimo da je '''''A<sub>i</sub>''''' neklasifikovan i da bi mogao legalno biti ubačen na poziciju identifikovanu njegovim pokazivačem klase, koji bi zamenio klasifikovani element u drugoj klasi. Ovo je nemoguće, jer su početni pokazivači u svakoj klasi njihove gornje granice, što osigurava da je tačna veličina prostora alocirana za svaku klasu u nizu '''''A'''''. Zbog toga, svaki element u klasi '''''A<sub>i</sub>''''', uključujui i '''''A<sub>i</sub>''''', već je klasifikovan. Takođe, ako je element već klasifikovan, pokazivač klase bi bio umanjen ispod novog indeksa elementa.<ref name="neubert_journal" /><ref name="neubert_code">{{cite web |url=http://www.neubert.net/FSOIntro.html |title=The FlashSort Algorithm |accessdate = 6. 11. 2007. |author=Karl-Dietrich Neubert |year=1998}}</ref>

== Karakteristike ==

Jedini dodatni memorijski zahtevi su pomoćni vektor '''''L''''' za smeštanje granica klasa i konstantan broj drugih promenljivih koje se koriste.

U idelanom slučaju balansiranog skupa podataka, svaka klasa bi bila približno iste veličine, a sortiranje pojedinačne klase ima složenost '''''O(1)'''''. Ako je broj klasa '''''m''''', proporcionalan veličini ulaznog skupa '''''n''''', vreme izvršavanja konačnog sortiranja umetanjem je '''''m * O(1) = O(m) = O(n)'''''. U najgorem slučaju, kada su svi elementi u nekoliko ili jednoj klasi, složenost algoritma kao celine je ograničena performansama poslednjeg koraka metode sortiranja. Za sortiranje umetanjem, ona je '''''O(n<sub>2</sub>)'''''. Razne varijante algoritma poboljšavaju performanse najgoreg slučaja koristeći sortiranja sa boljim performansama, kao što je kviksort ili rekurzivni flešsort, na klasama koje prevazilaze izvesnu granicu veličine.<ref name="neubert_code" /><ref>{{cite web |url=http://jea.acm.org/ARTICLES/Vol5Nbr3/node4.html |title=Cache-Effective Quicksort |accessdate = 6. 11. 2007. |author1=Li Xiao |author2=Xiaodong Zhang |author3=Stefan A. Kubricht |work=Improving Memory Performance of Sorting Algorithms |publisher=Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795 |archiveurl = https://web.archive.org/web/20071102070431/http://jea.acm.org/ARTICLES/Vol5Nbr3/node4.html <!-- Bot retrieved archive --> |archivedate = 2. 11. 2007.}}</ref>

Izbor vrednosti za '''''m''''', broja klasa, trampi vreme koje se troši na klasifikovanje elemenata i vreme koje se troši u poslednjem koraku sortiranja umetanjem. Na osnovu ovog istraživanja, Neubert je pronašao da je '''''m = 0.42n''''' optimalno.

Vodeći računa o memoriji, flašsort izbegava dodatne potrebe za smeštanjem klasa na veoma sličan način [[segmentno sortiranje|segmentnom sortiranju]] (bucketsort). Za '''''m = 0.1n''''' sa ravnomernim slučajnim podacima, flešsort je brži od hipsorta za svako '''''n''''' i brži od kviksorta za '''''n>80'''''. On postaje oko dva puta brži od kviksorta za '''''n = 10000'''''.

Zbog procesa klasifikacije, flešsort nije stabilan.

== Reference ==
{{reflist}}

== Spoljašnje veze ==
* [https://web.archive.org/web/20071018034000/http://elliottback.com/wp/archives/2006/01/07/sorting-in-linear-time/ -{Sorting in Linear Time}-]

{{normativna kontrola}}

[[Категорија:Алгоритми сортирања]]