Сортирајућа мрежа

У рачунарским наукама, компаративне мреже су абстрактни уредјаји сачињени од одређеног броја „жица“, које садрже неке вредности, и компаративних модула који повезују парове жица и мењају вредности на њима ако се не налазе у жељеном односу. Такве мреже се најчешће конструишу да би се извело сортирање одредјеног броја вредности и тада се називају сортирајуће мреже.

Сортирајуће мреже се разликују од сортирања методом поредјења у томе што оне нису способне да раде са произвољно великим уносима и у томе што се њихова секвенца поређења одређује унапред, без обзира на исход прошлих поређења. Та независнот од секвенце поређења је корисна при паралелном извршавању и у хардверској имплементацији. Без обзира на једноставност сортирајућих мрежа, теорија иза њих је изненађујуће комплексна. Њих су први пут проучавали Арсмстронг, Нелсон и О'Конор око 1954. године, који су тада и ставили патент на ту идеју.^[1]

Сортирајуће мреже се могу имплементирати преко хардвера и софтвера. Доналд Кнут је описао како се поредјења бинарних целих бројева могу имплементирати као једноставни уредјаји са три стања. Бечер је 1968, предложио да се сортирајуће мреже користе за израду прекидачких мрежа за рачунарски хардвер, и да тиме замене све елекронске компоненте и скупље цроссбар прекидаче. У последњих 15 година сортирајуће мреже, а нарочито битоник сорт се користе од стране ГПГПУ удружења за израду сортирајућих алгоритама који би радили на графичким процесорским јединицама.^[2]

Увод уреди

Демонстрациј акомпаратора у сортирајућој мрежи

Сортирајућа мрежа се састоји од два типа елемената: компаратори и жице. Жице су представљене да иду са лева на десно, носећи вредности (једна вредност по жици) које се крећу мрежом у сваком тренутку. Сваки компаратор повезује две жице. Када пар вредности који путује кроз пар жица наиђе на компаратор, компаратор мења места вредностима ако и само ако је вредност горње жице већа од вредности доње.

По формули, ако горња жица преноси x, а доња y, онда ће пошто налете на компаратор жице носе x’ = мин(x,y) и

y’ = маx(x, y), тако да је пар вредности сортиран. Мрежа која ће садржи одредјен број жица и компаратор који су заједно способни да сортирају вредности се назива сортирајућа мрежа.

Потпуна операција једноставне сортирајуће мреже је приказана испод. Јасно се види зашто ће ова мрежа исправно сортирати улазе.

Дубина и ефикасност уреди

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

Убацивање у мрежу и селекција уреди

Сваку мрежу можемо конструисати рекурзивно на основу принципа убацивања и селекције. Ако претпоставимо да имамо сортирајућу мрежу величине н, можемо направити мрећу величине н+1 убацујући додатни број у већ сортирану подмрежу (користећи медоте сортирања уметањем). Исто то можемо постићи и селекцијом најниже вредности од улаза и онда сортирати остатака вредности рекурзивно (користећи методе сортирања мехуром).

Сортирајућа мрежа која је направљена рекурзивно где највећи елемент иде на дно, а онда се сортирају остале жице. Засновано на сортирању мехуром

Сортирајућа мрежа констрисана рекурзивно тако да се прво сортирају н жица па се онда додаје преостала вредност Засновано на сортирању уметањем

Структура ове две сортирајуће мреже је веома слична. Ако спојимо ове две методе, видимо преко компарација које могу да се изврше истовремено да су чак и идентичне.^[3]

Мрежа сортирања мехуром

Мрежа сортирања уметањем

Кад су дозвољена паралелна поређења, сортирања мехуром и уметањем су идентична

Овакве мреже имају велику дубину од 2н -3, што је чини непрактичном.

Принцип нула-један

Иако је лако доказати исправност неких мрежа као у горе наведеним примерима то није увек тако. Постоји н! Пермутација у мрежи са н жица, и тестирање свих њих траје врло дуго, нарочито ако је н велики број. Тај број може значајно да се смањи до 2н , користећи метод који се зове нула-један.

Овај принцип каже да ако сортирајућа мрежа може да сортира 2н низа нула и јединица, онда може да сортира и произвољне бројеве у истом времену. Ово не само да смањује тестирање исправности саме мреже већ је врло користан про креирању многих оваквих конструкција.

Принцип се може доказати тако што се прво примети чињеница о компараторима: када се монотоно растућа функција ф примени на улазне врености, x и з су замењени ф(x) и ф(y), онда компаратори праве мин(ф(x), ф(y)) = ф(мин(x,y)) и маx(ф(x), ф(y)) = ф(маx(x,y)). Уз помоћ индукције резултат се може превести у лему која каже да ако мрежа преноси секвенцу а1, ..., ан инто б1, ..., бн, она ће трансформирати (а1), ..., ф(ан) у ф(б1), ..., ф(бн). Доказ даље иде доказивањем супротног: претпостављамо да је неки улаз а1, ..., ан садржи два елемента аи < ај , и да мрежа исправно замени места овим улазима. Онда ће то такодје исправно сортирати и ф(а1), ..., ф(ан) за функцију:

f(x)={\begin{cases}1\ &{\mbox{if }}x>a_{i}\\0\ &{\mbox{otherwise.}}\end{cases}}

Ова фунцкија је монотона, зато користимо нула-један принцип као контрапозитив.

Конструкција сортирајућих мрежа уреди

Разни алгоритим постоје за настајање једноставних али ефикасних мрежа дубине О(лог2 н). Често се користе у пракси. Теоријски је могуће конструисати ове мреже са логаритамском дубином, користећи АКС мрежу. Иако је битно теоријско откриће, АСК мрежа има малу или никакву примену због линеарне константе иза О нотације која је величине много, много хиљада. Постоји I поједностављена верзија АКС-а, која наглашава да су константе које су добијене за границу дубине неодговарајуће I да немају практични значај. Још једна метода конструкције сортирајуће мреже је откривена за О(н лог н) али иако има мању константу од АКС-а, баш због О(н лог н) сложености не може да ефикасно има паралелну имплементацију.

Оптималне сортирајуће мреже уреди

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

н	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Дубина	0	1	3	3	5	5	6	6	7	7	8	8	9	9	9	9
Величина, горња граница	0	1	3	5	9	12	16	19	25	29	35	39	45	51	56	60
Величина, доња граница, ако је различита	33	37	41	45	49	53

Првих шеснаест дубински- оптималних мрежа су наведене у Арт оф Цомпутер Программинг, коју је написао Кнут. Иако је оптималност првих осам доказана још 60-их година, оптималност последњих шест је показана тек 2014. године (девети I дести случај су доказани 1991.) .

За израду оптималних сортирајућих мрежа су се чак користили I генетски алгоритми. Кнут каже да су случајеви за н=9 и н=11 засновани на тој методи.

Референце уреди

^ УС 3029413, О'Цоннор, Даниел Г. & Нелсон, "Сортинг сyстем wитх $н$ -лине сортинг сwитцх", публисхед 10. 4. 1962
^ Оwенс, Ј. D.; Хоустон, M.; Луебке, D.; Греен, С.; Стоне, Ј. Е.; Пхиллипс, Ј. C. (2008). „ГПУ Цомпутинг”. Процеедингс оф тхе ИЕЕЕ. 96 (5): 879. дои:10.1109/ЈПРОЦ.2008.917757.
^ Кнутх, D. Е. (1997). Тхе Арт оф Цомпутер Программинг, Волуме 3: Сортинг анд Сеарцхинг (Сецонд изд.). Аддисон–Wеслеy. стр. 219—247. ИСБН 978-0-201-89685-5.

[1] УС 3029413, О'Цоннор, Даниел Г. & Нелсон, "Сортинг сyстем wитх $н$ -лине сортинг сwитцх", публисхед 10. 4. 1962

[2] Оwенс, Ј. D.; Хоустон, M.; Луебке, D.; Греен, С.; Стоне, Ј. Е.; Пхиллипс, Ј. C. (2008). „ГПУ Цомпутинг”. Процеедингс оф тхе ИЕЕЕ. 96 (5): 879. дои:10.1109/ЈПРОЦ.2008.917757.

[knuth-3] Кнутх, D. Е. (1997). Тхе Арт оф Цомпутер Программинг, Волуме 3: Сортинг анд Сеарцхинг (Сецонд изд.). Аддисон–Wеслеy. стр. 219—247. ИСБН 978-0-201-89685-5.

[1]

[2]

[3]