Flešsort

Flešsort (engl. 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, 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:

  $K(A_{i})=1+{\textrm {INT}}\left((m-1){\frac {A_{i}-A_{\textrm {min}}}{A_{\textrm {max}}-A_{\textrm {min}}}}\right)$

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₀ do A_i-1 su već klasifikovani i umetnuti u odogvarajuću klasu. Pretpostavimo da je i veće od trentunog pokazivača na klasu A_i. Sada pretpostavimo da je A_i 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_i, uključujui i A_i, već je klasifikovan. Takođe, ako je element već klasifikovan, pokazivač klase bi bio umanjen ispod novog indeksa elementa.

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₂). 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.

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 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.

Spoljašnje veze

• Sorting in Linear Time