Флешсорт

Флешсорт (енгл. Flashsort) је дистрибутивни алгоритам сортирања, који има линеарну сложеност О(н), за равномерно распоређене скупове података и захтева релативно мало додатне меморије. Оригинални рад објавио је Карл-Диетрицх Неуберт^[1], 1998. године.

Концепт

Основна идеја која стоји иза флешсорт алгоритма је да ако имамо скуп података са познатом расподелом, можемо одмах да проценимо где ће елемент бити смештен након сортирања, уколико је опсег скупа познат. На пример, ако имамо равномеран скуп података, где је најмањи елемент 1, највећи 100, а 50 се налази у скупу, разумно је претпоставити да ће 50 бити близу средине скупа након сортирања. Ова приближна позиција се назива класа. Ако имамо бројеве од 1 до м, класа елемента Аи се рачуна као:

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

где је А улаз скупа. Опсег покривен сваком од класа је једнак, изузев последње класе која укључује само максимум(е). Класификација осигурава да је сваки елемент класе већи од било ког елемента ниже класе. Ово делимично распоређује податке и смањује број инверзија. Затим се на класификовани скуп примењује сортирање уметањем. Докле год су подаци равномерно распоређени, величина класе ће бити стална и сортирање уметањем ће бити ефикасно.

Меморијски ефикасна имплементација

Како би се флашсорт извршавао са својим малим меморијским издацима, алгоритам не користи додатне структуре података како би сместио класе. Уместо тога, смешта горње границе сваке класе улазног низ А у помоћни вектор L. Ове горње границе су направљене рачунањем броја елемената у свакој класи и горња граница класе је број елемената у тој класи и свакој класи пре ње. Ове границе служе као показивачи на класе.

Класификација се имплементира кроз серију циклуса, где је вођа циклуса узет из улазног низа А и његова класа је израчуната. Показивачи у вектору L су коришћени да уметну вођу циклуса у праву класу, а показивач класе у L се умањује након сваког уметања. Убацивање лидера циклуса ће избацити још један елемент из низа А, који ће бити класификован и убачен на другу локацију и тако даље. Циклус се завршава када се елемент убаци на почетну позицију вође циклуса.

Један елемент је валидни вођа циклуса ако још увек није био класификован. Како алгоритам итерира кроз низ А, претходно класификовани елементи се прескачу, а некласификовани се користе да иницирају нове циклусе. Могуће је разликовати да ли је елемент био класификован или не без коришћења додатних ознака: један елемент је класификован ако и само ако је његов индекс већи од вредности показивача класе у L. Да бисмо ово доказали, разматрамо текући индекс низа А који алгоритам обрађује. Нека је тај индекс и. Елементи од А₀ до А_и-1 су већ класификовани и уметнути у одогварајућу класу. Претпоставимо да је и веће од трентуног показивача на класу А_и. Сада претпоставимо да је А_и некласификован и да би могао легално бити убачен на позицију идентификовану његовим показивачем класе, који би заменио класификовани елемент у другој класи. Ово је немогуће, јер су почетни показивачи у свакој класи њихове горње границе, што осигурава да је тачна величина простора алоцирана за сваку класу у низу А. Због тога, сваки елемент у класи А_и, укључујуи и А_и, већ је класификован. Такође, ако је елемент већ класификован, показивач класе би био умањен испод новог индекса елемента.^[1]^[2]

Карактеристике

Једини додатни меморијски захтеви су помоћни вектор L за смештање граница класа и константан број других променљивих које се користе.

У иделаном случају балансираног скупа података, свака класа би била приближно исте величине, а сортирање појединачне класе има сложеност О(1). Ако је број класа м, пропорционалан величини улазног скупа н, време извршавања коначног сортирања уметањем је м * О(1) = О(м) = О(н). У најгорем случају, када су сви елементи у неколико или једној класи, сложеност алгоритма као целине је ограничена перформансама последњег корака методе сортирања. За сортирање уметањем, она је О(н₂). Разне варијанте алгоритма побољшавају перформансе најгорег случаја користећи сортирања са бољим перформансама, као што је квиксорт или рекурзивни флешсорт, на класама које превазилазе извесну границу величине.^[2]^[3]

Избор вредности за м, броја класа, трампи време које се троши на класификовање елемената и време које се троши у последњем кораку сортирања уметањем. На основу овог истраживања, Неуберт је пронашао да је м = 0.42н оптимално.

Водећи рачуна о меморији, флашсорт избегава додатне потребе за смештањем класа на веома сличан начин сегментном сортирању (буцкетсорт). За м = 0.1н са равномерним случајним подацима, флешсорт је бржи од хипсорта за свако н и бржи од квиксорта за н>80. Он постаје око два пута бржи од квиксорта за н = 10000.

Због процеса класификације, флешсорт није стабилан.

Референце

^ ^а ^б Неуберт, Карл-Диетрицх (1998). „Тхе Фласхсорт Алгоритхм”. Др. Добб'с Јоурнал: 123. Приступљено 6. 11. 2007.
^ ^а ^б Карл-Диетрицх Неуберт (1998). „Тхе ФласхСорт Алгоритхм”. Приступљено 6. 11. 2007.
^ Ли Xиао; Xиаодонг Зханг; Стефан А. Кубрицхт. „Цацхе-Еффецтиве Qуицксорт”. Импровинг Меморy Перформанце оф Сортинг Алгоритхмс. Департмент оф Цомпутер Сциенце, Цоллеге оф Wиллиам анд Марy, Wиллиамсбург, ВА 23187-8795. Архивирано из оригинала 2. 11. 2007. г. Приступљено 6. 11. 2007.

Спољашње везе

Sorting in Linear Time

[neubert_journal-1] а ^б Неуберт, Карл-Диетрицх (1998). „Тхе Фласхсорт Алгоритхм”. Др. Добб'с Јоурнал: 123. Приступљено 6. 11. 2007.

[neubert_code-2] а ^б Карл-Диетрицх Неуберт (1998). „Тхе ФласхСорт Алгоритхм”. Приступљено 6. 11. 2007.

[3] Ли Xиао; Xиаодонг Зханг; Стефан А. Кубрицхт. „Цацхе-Еффецтиве Qуицксорт”. Импровинг Меморy Перформанце оф Сортинг Алгоритхмс. Департмент оф Цомпутер Сциенце, Цоллеге оф Wиллиам анд Марy, Wиллиамсбург, ВА 23187-8795. Архивирано из оригинала 2. 11. 2007. г. Приступљено 6. 11. 2007.

[1]

[2]

[3]