Целобројно сортирање

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

Класични алгоритам целобројног сегментног сортирања, цоунтинг сортирања и радиx сортирања су најчешће коришћени и најпрактичнији. Много касније истраживања о алгоритму целобројног сортирања усмерена су више на практичност него на теоријска побољшања у најгорем случају , и алгоритми који долазе из ове претраге нису практични на 64-битној архитектури рачунара, такође експерименти су показали да неке од ових метода могу бити побољшања на радиx сортирању за податке који садрже 128 или више бита по кључу. Поред тога, за велике податке,модели приближно слуцајаног приступс меморији многих алгоритма целобројног сортирања могу их спутати за разлику од сортирања поређењем које је дизајнирано са хијарархијом меморије на уму. Целобројно сортирање пружа једну од шест тестова у ДАРПА Хигх Продуцтивитy Цомпутинг Сyстем Дисцрете Матхематицс бенцхмарк суите . I један од 11 тестова у НАС Параллел Бенцхмаркс.

Модел рачунања

Време израчунавања целобројног сортирања зависи од три параметра: да број н буде сортиран, да величина К највећег кључа буде сортиран, а број битова w може бити представљен на машинском језику рачунара на алгоритму који се користи. Типично, претпоставља се да је w ≥ лог₂(маx(н, К)); то јест, да је машински језик довољно велики да представи индекс у низу улазних података и да је довољно велики да представи самосталан кључ. Алгоритам целобројног сортирања је обично дизајниран да ради било у моделима рачунања било показивачким или аутоматима случајног приступа, главнна разлика између ова два модела је у томе што са случајним приступом машина омогућава да свака вредност која се чува у регистрима који ће се користити као адреса меморије, чита и пише операције, са ценом по јединици рада, што омогућава одређене комплексне операције над подацима који се брзо налазе коришћењем лоокуп табела. Насупрот томе, показивачки модел омогућава приступ меморији само преко показивача на меморију која се не може користити користећи аритметичке операције. У оба модела, додатак, боолеан операције и бинарне операције померања обично се могу остварити у једници времена по операцији. Различити алгоритми сортирања имају различите претпоставке, како год било, целобројно множење се такође обавља у јединици времена по операцији. Други специјализовани модели рачунања као паралелан приступ меморији ће такође бити разматрани.

Андерссон, Милтерсен & Тхоруп 1999 су показали да у неким случајевима код множења или лоокуп табеле је потребно да неки алгоритми целобројног сортирања могу бити замењени појединим операцијама које би биле много лакше да би се лакше реализовале у хардверу, али обично нису доступни на рачунарима опсте намене. Тхоруп 2003, доказао је како се могу заменити ове операције битовским пољима манипулишући инструкцијама које су доступне на Пентиум процесорима.

Сортирање у односу на примарни ред

Могуће је да основа алгоритма сортирања селекцијом било ког низа структуираних података, која омогућава један од главних скупова од н елемената са кључем у интервалу од 0 то К − 1, у зависности од операције, да пронађе и уклони ставку са минималним кључем. Једноставно се креира приоритетни низ који садржи све елементе, затим се више пута примењује минимално брисање док се низ не испразни. Део низа чији је елемент избрисан, сада је сортиран део низа. Време за стварање овог алгоритма је време за креирање низа, плус време за н минималних операција брисања. На пример, код алгоритма сортирања поређењем, хеап сортирање има ову форму. Како год било, такође постоје алгоритми овог типа који су бржи за целобројне кључеве, на основу приоритетних редова структуираних података који су специјализовани за целе бројеве.

Конкретно, ван Емде Боас стабло може да се користи као приопитетни ред да сортира низ од н кљуцева, где је сваки у опсегу од 0 то К − 1, у временској сложености О(н лог лог К). То је теоретско побољшање у односу на радиx сортирање када је К довољно велико. Међутим, да би се користило ван Емде Боас-ово стабло, један или треба директно адресибилну меморију К речи, или мора да се симулира помоћу Хеш табела, смањујући тако линеарни простор, правећи алгоритам случајним. Други приоритетни ред са сличним перформансама (укључујући потребу рандомизације путем Хеш табела) је Y –брзо стабло које је осмислио Wиллард 1982. Тхоруп 2007 је показао како једнакост између приоритетних редова иде у другом смеру: ако је могуће извшити целобројно сортирање у времену Т(н) по кључу, онда је исто време потребно за убацивање или брисање операције у примарном реду. Тхроуп - ова редукција је компликована и подразумева доступност било брзих операција множења или лоокуп табеле, али такође пружа алтернативни приоритетни ред користећи само сабирање и логичке операције са временом Т(н) + Т(лог н) + Т(лог лог н) + ... по операцији, највише множењем времена од стране итеративног алгоритма.

Алгоритам за мале кључеве

Одавно је познато да сегментно сортирање или цоунтинг сортирање могу да сортирају низ од н кључева, сваки у опсегу од 0 до К − 1, у времену О(н + К). У сегментном сортирању, показивачи на податке дистрибуирани су у табелу "буцкет" (представљена као врста повезаних листи) користећи кључеве као показиваче у табели. Онда, су сви подаци спојени тако да формирају излазну листу. У цоунтинг сортирању, буцкет је замењен бројачем који одређује број података који имају исту вредност, а затим префиx сума се користи да се одреди подниз, у излазном низу, где би требало да се налазе подаци са истом вредношћу. Радиx сортирање је алгоритамска техника у којој се неки други алгоритам који је одговарајућ само за мале кључеве понавља, правећи алгоритам који се може употребити на веће кључеве. Кључ који је употребљен за и –ти корак другог алгоритма за сортирање, је и –та цифра позиције целог кључа, према радиx сортирању, почев од цифре најмање тежине и напредује у најзначајније. Да би овај алгоритам радио, основа алгоритма мора бити стабилна, подаци са истим кључем не би требали да мењају позиције међу собом. Користећи радиx сортирање, радиxом да се изабере пропорционално н, са сегментним сортирањем и цоунтинг сортирањем у основи , могуће је сортирати низ од н кључева, сваки у опсегу од 0 то К − 1, у времену О(н лог_{н К)}. Користећи 2^н радиx омогућава да кључ основног алгоритма буде направјен користећи само бинарно померање и маскирање. Софистицираније технике са сличним укусом и бољим перформансама теоријски је развио Киркпатрицк & Реисцх 1984. Они су приметили да сваки пролазак кроз радиx сортирање може да се тумачи као „смањење опсега“ технике која, у линеарном времену, смањује максималне величине кључева за фактор н, уместо тога, њихова техника смањује величину кључа у квадратном корену на квадратни корен своје раније вредности (преполови број битова потребних за представљање кључа), такође у линеарном времену. Као и у радиx сортирању, они представљају кључеве као двоцифрене бројеве у основи б, где је основа б приближно корен из √К. Онда се ставке групишу и сортирају се буцкет сортирањем у складу са својим цифрама највеће тежине, у линеарном времену, користећи велику али неиницијализовану директну адресну меморију или хеш табеле. Свако сегментно сортирање има свог представника: ставка са највећим кључем, они затим сортирају листу података користећи као кључ цифре највеће тежине као представнике и цифре најмање тежине као не представнике.

Груписањем ставки са листе сегментним сортирањем, сваки део сегментног сортирања се може поставити у сортираном редоследу, а издвајањем представника из сортиране листе сегменти се могу спојити у сортираном редоследу. Тако, у линеарном времену, проблем сортирања се своди на други проблем рекурзивног сортирања у ком су кључеви много мањи, квадратни корен своје претходне величине. Овај поступак се понавља све док кључ не постане довољно мали да сегментно сортирање доводи до времена извршавања О(н лог лог_н К).

Компликовани случајно алгоритам Хан & Тхоруп 2002 омогућавада ова ограничења буду умањена још више, од О(н лог лог_н К).

Алгоритми за неколико ставки

Алгоритам целобројног сортирања је неумерен ако се захтева реч која је величине w која је знатно већа лог маx(н, К). Као екстремни пример, ако је w ≥ К, и сви кључеви су различити, онда кључеви могу бити сортирани представљајући их као битовски низ, са једним битом на позицији и где је и један од улазних кључева, а затим се више пута укљања бит најмање тежине. Неумерено пацкед сортирање које је осмислио Алберс & Хагеруп 1997 користи подпрограм, који је базиран на Кен Батцхер - овом паралелном сортирању мреже, за спајање две сортиране секвенце кључа где је сваки од њих довољно кратак да се пакује у једној машинској речи. Улаз у сложени сортирајући алгоритам, низ предмета сложених један по један речи, трансформише се у сабијену форму, сваки низ речи држи више предмета у сложеном реду, користећи овај потпрограм удвостручвава број јединица пакованих у свакој речи. Када је низ у запакованој форми, Алберс анд Хагеруп користе форму сортирања спајањем да их сортира, када се две секвенце споје у једну дужу секвенцу, истим паралелним сортирањем потпрограм може да се користи више пута за издвајање пакованих речи састављених од најмењих преосталих елемената од две секвенце. Овај алгоритам добија довољну брзину од своје репрезентације да сортира улаз у линеарном времену кад год је то могуће за једну реч која садржи Ω(лог н лог лог н) кључева; тј, где је лог К лог н лог лог н ≤ цw за неку константу ц > 0.

Алгоритам за велике речи

сегментно сортирање, цоунтинг сортирање, радиx сортирање иван Емде Боас - ово стабло најбоље ради за кључеве мале величине, јер са довољно великим кључевима, они постају спорији од алгоритма за сортирање поређењем. Међутим, када је величина кључа или величина речи веома велика у односу на број јединица (или еквивалентна када је број јединица мали), могуће је сортирати алгоритмом qуицк сортирања, користећи различите алгоритме који користе предности урођеног паралелизма са могућношћу да обављају аритметичке операције на великим речима.

Рани резултат у том правцу дали су Ајтаи, Фредман & Комлóс 1984) користећи јединицу узорка модела израчунавања(вештачки модел у коме се сложеност алгоритма мери само по броју приступа меморији које обави). Ослањајући се на свој рад, Фредман & Wиллард 1994 описали су две структуре, Q-хеап и аутоматски хеап, које су применљиве на аутомате са слуцајним приступом. Q-хеап је паралелна верзија бинарног стабла, и омогућава операције приоритетних низова као и да одабирање наследника и претка буде обављено непрекидно за сетове О((лог Н)^1/4) предмета, где је Н ≤ 2^w величина табеле пре израчунавања потребна за имплементирање структуре података. Атомски хеап је Б-стабло у коме је сваки чвор дрвета представљен као Q-хеап; дозвољава операције приоритетних редова у константном времену за (лог Н)^О(1) ставки. Андерссон ет ал. 1998 предвидели су алгоритам под називом сортирање обележавањем које омогућава линеарно време сортирања од 2^{О((лог w)1/2 − ε)}, за било које ε > 0. Као и у алгоритму Киркпатрицк и Реисцх, они обаваљају смањење опсега користећи приказ кључа као бројеве у основи б са пажљивим избором б. Смањен опсег алгоритма замењује сваку цифру „потписом“, хешираном вредношћу са О(лог н) бита који имају различите вредности цифара различитих потписа. Ако је н довољно мало, бројеви који су формирани процесом замене биће значајно мањи од оригиналног кључа, укључујући неумерени алгоритам сортирања паковањем креираних од стране Алберс & Хагеруп 1997 да сортира замењене бројеве у линеарном времену. Из сортиране листе замењених бројева, могуће је формирати компресовано дигитално стабло од кључева у линеарном времену, а деца сваког чвора дигиталног стабла могу се сортирати рекурзивно користећи само кључеве величине б, након чега стабло прави попречан сортиран низ ставки.

Транс-Дихотомни алгоритми

Фредман & Wиллард 1993 су увели транс-дихотомни модел анализе за алгоритам целобројног сортирања, у коме се ништа не претпоставља о распону целобројних кључева и мора се гарантовати перформанса алгоритма само функцијом броја вредности податка. Алтернативно, у овом моделу, потребно време за један алгоритам на групи н ставки претпоставља се да је најгори случај потребног времена за било коју могућу комбинацију К и w. На пример, Фредман анд Wилардов алгоритам сортирања фузионим стаблом ради у времену О(н лог н / лог лог н), побољшање у односу на сортирање поређењем за било који избор Ки w. Алтернативна верзија њиховог алгоритма која укљућује коришћење насумице изабраних бројева и дељење целине унапређује ово у О(н√лог н).

Од њихових проналазака, јос бољи алгоритми су развијени. На пример, брзо примењивање Киркпатрицк–Реисцх технике сманивања распона док кључеви не постану довољно мали да се примени Алберс–Хагеруп алгоритам сортирања сабијањем, могуће је сортирати у времену О(н лог лог н), ипак, део смањења распона овог алгоритма захтева или велику меморију (пропорционалну са √К) или бирање слућајног елемента у виду хеш табела. Хан & Тхоруп 2002 показали су како сортирати у случајном времену О(н√лог лог н). Њихова техника укључује коришћење идеја повезаних са обележавајућим сортирањем за раздвајање података у много малих подлиста, величине довољно мале да сортирање обележавањем може ефикасно сложити сваку од њих. Могуће је користити сличне идеале за сортирање целих бројева у времену О(н лог лог н))и линеарни простор. Користећи само просте аритметицке операције (без множења или табеларних проналажења) могуће је сортирати у случајном очекиваном времену О(н лог лог н) или детерминистичком времену О(н (лог лог н)^{1 + ε}) за било коју непромењиву ε > 0..

Референце

• Ајтаи, M.; Фредман, M.; Комлóс, Ј. (1984), „Хасх фунцтионс фор приоритy qуеуес”, Информатион анд Цонтрол, 63 (3): 217—225, МР 837087, дои:10.1016/С0019-9958(84)80015-7 .
• Алберс, Сусанне; Хагеруп, Торбен (1997), „Импровед параллел интегер сортинг wитхоут цонцуррент wритинг”, Информатион анд Цомпутатион, 136 (1): 25—51, МР 1457693, С2ЦИД 1284673, дои:10.1006/инцо.1997.2632 .
• Андерссон, Арне; Хагеруп, Торбен; Нилссон, Стефан; Раман, Рајеев (1998), „Сортинг ин линеар тиме?”, Јоурнал оф Цомпутер анд Сyстем Сциенцес, 57 (1): 74—93, МР 1649809, дои:10.1006/јцсс.1998.1580 .
• Андерссон, Арне; Нилссон, Стефан (1998), „Имплементинг радиxсорт”, Тхе АЦМ Јоурнал оф Еxпериментал Алгоритхмицс, 3: 7, МР 1717389, С2ЦИД 2125652, дои:10.1145/297096.297136 .
• Андерссон, Арне; Милтерсен, Петер Бро; Тхоруп, Миккел (1999), „Фусион треес цан бе имплементед wитх АЦ⁰ инструцтионс онлy”, Тхеоретицал Цомпутер Сциенце, 215 (1–2): 337—344, МР 1678804, дои:10.1016/С0304-3975(98)00172-8 .
• Бхатт, П. C. П.; Дикс, К.; Хагеруп, Т.; Прасад, V. C.; Радзик, Т.; Саxена, С. (1991), „Импровед детерминистиц параллел интегер сортинг”, Информатион анд Цомпутатион, 94 (1): 29—47, МР 1123154, дои:10.1016/0890-5401(91)90031-V .
• Цоле, Р.; Висхкин, у. (1986), „Детерминистиц цоин тоссинг wитх апплицатионс то оптимал параллел лист ранкинг”, Информатион анд Цонтрол, 70 (1): 32—53, дои:10.1016/С0019-9958(86)80023-7 .
• Цомрие, L. Ј. (1929—1930), „Тхе Холлеритх анд Поwерс табулатинг мацхинес”, Транс. Офfiце Мацх. Усерс' Ассоц., ЛТД.: 25—37 . Цитед бy Тхоруп 2007 ас ан еарлy соурце фор радиx сорт.
• Цормен, Тхомас Х.; Леисерсон, Цхарлес Е.; Ривест, Роналд L.; Стеин, Цлиффорд (2001), Интродуцтион то Алгоритхмс (2нд изд.), МИТ Пресс анд МцГраw-Хилл, ИСБН 978-0-262-03293-3 .
• Фредман, Мицхаел L.; Wиллард, Дан Е. (1993), „Сурпассинг тхе информатион-тхеоретиц боунд wитх фусион треес”, Јоурнал оф Цомпутер анд Сyстем Сциенцес, 47 (3): 424—436, МР 1248864, дои:10.1016/0022-0000(93)90040-4 .
• Фредман, Мицхаел L.; Wиллард, Дан Е. (1994), „Транс-дицхотомоус алгоритхмс фор минимум спаннинг треес анд схортест патхс”, Јоурнал оф Цомпутер анд Сyстем Сциенцес, 48 (3): 533—551, МР 1279413, дои:10.1016/С0022-0000(05)80064-9 .
• Гоодрицх, Мицхаел Т.; Тамассиа, Роберто (2002), „4.5 Буцкет-Сорт анд Радиx-Сорт”, Алгоритхм Десигн: Фоундатионс, Аналyсис, анд Интернет Еxамплес, Јохн Wилеy & Сонс, стр. 241—243 .
• Хагеруп, Торбен (1987), „Тоwардс оптимал параллел буцкет сортинг”, Информатион анд Цомпутатион, 75 (1): 39—51, МР 910976, дои:10.1016/0890-5401(87)90062-9 .
• Хан, Yијие (2004), „Детерминистиц сортинг ин О(н лог лог н) тиме анд линеар спаце”, Јоурнал оф Алгоритхмс. Цогнитион, Информатицс анд Логиц, 50 (1): 96—105, МР 2028585, дои:10.1016/ј.јалгор.2003.09.001 .
• Хан, Yијие; Тхоруп, M. (2002), „Интегер сортинг ин О(н√лог лог н) еxпецтед тиме анд линеар спаце”, Проц. 43рд Аннуал Сyмпосиум он Фоундатионс оф Цомпутер Сциенце (ФОЦС 2002), стр. 135—144, С2ЦИД 5245628, дои:10.1109/СФЦС.2002.1181890 .
• Киркпатрицк, Давид; Реисцх, Стефан (1984), „Уппер боундс фор сортинг интегерс он рандом аццесс мацхинес”, Тхеоретицал Цомпутер Сциенце, 28 (3): 263—276, МР 742289, дои:10.1016/0304-3975(83)90023-3 .
• МцИлроy, Петер M.; Бостиц, Кеитх; МцИлроy, M. Доуглас (1993), „Енгинееринг Радиx Сорт” (ПДФ), Цомпутинг Сyстемс, 6 (1): 5—27 .
• Педерсен, Мортен Ницолај (1999), А студy оф тхе працтицал сигнифицанце оф wорд РАМ алгоритхмс фор интернал интегер сортинг, Мастерс тхесис, Департмент оф Цомпутер Сциенце, Университy оф Цопенхаген, Денмарк, Архивирано из оригинала 16. 03. 2012. г., Приступљено 30. 05. 2013 .
• Рахман, Наила; Раман, Рајеев (1998), „Ан еxпериментал студy оф wорд-левел параллелисм ин соме сортинг алгоритхмс”, Алгоритхм Енгинееринг, 2нд Интернатионал Wорксхоп, WАЕ '92, Саарбрüцкен, Германy, Аугуст 20–22, 1998, Процеедингс (ПДФ), Маx Планцк Институте фор Цомпутер Сциенце, стр. 193—203 .
• Реиф, Јохн Х. (1985), „Ан оптимал параллел алгоритхм фор интегер сортинг”, Проц. 26тх Аннуал Сyмпосиум он Фоундатионс оф Цомпутер Сциенце (ФОЦС 1985), стр. 496—504, С2ЦИД 5694693, дои:10.1109/СФЦС.1985.9 .
• Тхоруп, Миккел (2002), „Рандомизед сортинг ин О(н лог лог н) тиме анд линеар спаце усинг аддитион, схифт, анд бит-wисе Боолеан оператионс”, Јоурнал оф Алгоритхмс, 42 (2): 205—230, МР 1895974, С2ЦИД 9700543, дои:10.1006/јагм.2002.1211 .
• Тхоруп, Миккел (2003), „Он АЦ⁰ имплементатионс оф фусион треес анд атомиц хеапс”, Процеедингс оф тхе Фоуртеентх Аннуал АЦМ-СИАМ Сyмпосиум он Дисцрете Алгоритхмс (Балтиморе, MD, 2003), Неw Yорк: АЦМ, стр. 699—707, ИСБН 9780898715385, МР 1974982 .
• Тхоруп, Миккел (2007), „Еqуиваленце бетwеен приоритy qуеуес анд сортинг”, Јоурнал оф тхе АЦМ, 54 (6): Арт. 28, МР 2374029, дои:10.1145/1314690.1314692 .
• Wиллард, Дан Е. (1983), „Лог-логаритхмиц wорст-цасе ранге qуериес аре поссибле ин спаце Θ(Н)”, Информатион Процессинг Леттерс, 17 (2): 81—84, МР 731126, дои:10.1016/0020-0190(83)90075-3 .