Back

ⓘ Flešsort




                                     

ⓘ Flešsort

Flešsort je distributivni algoritam sortiranja, koji ima linearnu složenost O, za ravnomerno rasporedene skupove podataka i zahteva relativno malo dodatne memorije. Originalni rad objavio je Karl-Dietrich Neubert, 1998. godine.

                                     

1. 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 + INT m − 1 A i − A min A max − A min) {\displaystyle KA_{i}=1+{\textrm {INT}}\leftm-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 maksimume. Klasifikacija osigurava da je svaki element klase veći od bilo kog elementa niže klase. Ovo delimično rasporeduje podatke i smanjuje broj inverzija. Zatim se na klasifikovani skup primenjuje sortiranje umetanjem. Dokle god su podaci ravnomerno rasporedeni, veličina klase će biti stalna i sortiranje umetanjem će biti efikasno.

                                     

2. 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 voda ciklusa uzet iz ulaznog niza A i njegova klasa je izračunata. Pokazivači u vektoru L su korišćeni da umetnu vodu 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 vode ciklusa.

Jedan element je validni voda 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 obraduje. Neka je taj indeks i. Elementi od A 0 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. Takode, ako je element već klasifikovan, pokazivač klase bi bio umanjen ispod novog indeksa elementa.

                                     

3. 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 O1. Ako je broj klasa m, proporcionalan veličini ulaznog skupa n, vreme izvršavanja konačnog sortiranja umetanjem je m * O1 = Om = On. 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 On 2. 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.

Users also searched:

...