Back

ⓘ Блоксорт




Блоксорт
                                     

ⓘ Блоксорт

Блоксорт, је алгоритам сортирања који спада у групу стабилних алгоритама сортирања, и састоји се од најмање две операције спајања и од сортирања уметањем у О времену у месту. Назив је добио из закључка да спајање две сортиране листе, А и Б, је еквивалентно дељењу А у блокове једнаких величина, и убацивање сваког блока А у листу Б под специјалним условима, и спајање АБ пара.

Један практичан алгоритам за блоксорт су предложили Pok-Son Kim и Arne Kutzner 2008. године.

                                     

1. Преглед

Спољашња петља блоксорта је идентична алгоритму сортирања спајањем са имплементацијом одоздо-нагоре, где сваки ниво сортирања спаја парове поднизова, А и Б, у величинама од 1, затим 2, па 4, 8, 16, и тако даље, све док оба подниза не буду постали један низ.

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

Једном кад се сваки А и Б блок сваког А и Б подниза споје за тај ниво сортирања спајањем, онда се вредности у том баферу могу сортирати да би повратили своје првобитно уредјење поредак, па се сортирање уметањем мора искористити. Вредности у баферима се расподељују према њиховим првим сортираним позицијама у низу. Овај процес се понавља за сваки ниво сортирања спајањем спољашња одоздо нагоре имплементација, и у том тренутку низ ће бити стабилно сортиран.

                                     

2. Алгоритам

Следећи оператори се користе у примеру кода:

Такође, блоксорт користи следеће операције као део алгоритма:

  • Линеарна претрага: тражи одређену вредност у низу проверавајући сваки елемент у поретку, све док га не нађе.
  • Блок замена: мења распон вредности у низу са вредностима у другом распону низа.
  • Ротирање низа: померање елемената низа улево или десно неким бројем размака, вредностима са крајева низа. Ротацја може бити имплементирана као окретање стабла.
  • Бинарна претрага: претпостављамо да је низ сортиран, проверава средњу вредност тренутног опсега, затим ако је вредност мања проверава доњи распон, а ако је већа проверава горњи распон. Блоксорт користи две варијанте: једна која проналази прву позицију за убацивање у сортирани низ, и другу варијанту која проналази последњу позицију.
  • Замена: мења позиције две вредности у низу.
  • Сортирање уметањем: за сваки елемент у низу, пролази кроз петљу од позади и тражи где треба да се убаци елемент, а затим га и стави на ту позицију.
Rotiraj Obrni niz, raspon Obrni niz, minA = nadjiA

Преостали А блокови настављају ролање кроз низ а они се избацују у убацују тамо где они треба да буду. Овај процес се одвија све док сви А блокови не буду избачени и ротираниу претходни Б блок.

Када се једном избаци последњи преостали А блок и убаци у Б блок где одговара, онда треба да се споји са преосталим Б вредностима. Овим се завршава процес спајања за одређени пар поднизова А и Б. Међутим, онда се мора поновити процес за преостале поднизове А и Б за тренутни ниво сортирања спајањем.

Приметите да се унутрашњи бафери могу искористити за сваки скуп поднизова А и Б за овај ниво сортирања спајањем, и не мора се поново избацивати или модификовати у било ком смислу.

                                     

2.1. Алгоритам Прерасподела

Након што се споје низови А и Б, један од спољашњих бафера и даље преостане. Први спољашњи бафер је коришћен за ознаку А блокова, и његов садржај је и даље остао у истом поретку, док је други бафер преуредио свој поредак онда када је био коришћен за замену због спајања. Ово значи да се садржаји другог бафера морају сортирати другим алгоритмом, као што је сортирање уметањем. Затим, та два баера се морају прерасподелити назад у низ али са обрнутим процесом обрнут процес у односу на његов настанак. Алгоритам блоксорт је готов после понављања ових корака на сваком нивоу имплементације одоздо нагоре алгоритма-сортирање спајањем.

                                     

3. Варијанте

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

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

Добри избори за величину бафера укључују:

Уместо означавања А блокова преко садржаја једног од унутрашњих бафера, може се користити индиректни покретни-имитациони-бафер.Ово је унутрашњи бафер дефинисан као s1 t s2, где су s1 i s2 исте величине као број А и Б блокова, и t садржи било коју вредност која прати s1 и једнака је последњој вредности s1 што потврђује да ни једна вредност у s2 се не појављује у s1. Други унутрашњи бафер садржи √ A јединствених вредности које се и даље користе. Првих √ A вредности из s1 и s2 su zamenjene jedna drugom da bi šifrovale informacije u baferu o tome koji blokovi su A blokovi a koji B blokovi. Kada se A blok sa indeksom i замени Б са блокм индекса j где је први А блок иницијално индекса 0, s1. Ово имитира покрете А блокова кроз Б. Јединствене вредности у другом баферу се користе да се одреди првобитан оригиналан поредак А блокова пошто се ролају кроз Б блокове. Када се једанпут избаце А блокови, покретни-имитациони бафер се користи да дешифрује да ли је дати блок у низу А блок или Б блок, сваки А блок се ротира у Б блоку, и други унутрашњи бафер секористи као простор за замену илокално спајање.

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

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



                                     

4.1. Анализа Сложеност

Блоксорт започиње уметањем групе од 16-31 елемената у низ. Сортирање уметањем је On² операција, па то доводи од O16² * n/16 до O31² * n/31, што је On када се константне вредности занемаре. Такође мора се применити сортирање уметањем на други унутрашњи бафер после сваког завршеног нивоа спајања. Међутим, пошто је овај бафер ограничен на √ A величине, O√ n ² операција такође се завршава са On.

Затим се мора извадити два унутрашња бафера за сваки ниво сортирања спајањем. То ради тако што итерира кроз елементе у А и Б поднизовима и повећава бројач увек када се промени вредност, и на налажењу довољно вредности да их ротира на почетак А или на крају Б. У најгорем случају ће се претражити цео низ пре проналажена √ A nesusednih jedinstvenih vrednosti, što zahteva On poredenja i √ A ротација за √ A Вредности. Ово се решава у On + √ n * √ n, или On.

Када ни А ни Б поднизови не садрже √ A јединствене вредности да направе унутрашње бафере, операција спајања се одвија у месту где се понаваљано бинарно претражује и ротира А у Б. Међутим, познати недостатак јединствених вредности у било ком поднизу, је ограничење броја бинарних претрага и ротација које ће се десити током овог корака, што опет даје √ A елемената ротираних у √ A времени, ули On. Veličina svakog bloka je takode podešena da bude manja-u ovom slučaju kada pronalazi √ A јединствених вредности али не 2 √ A, што даље ограничава број јединствених вредности који се налазе у било ком А или Б блоку.

Означавање А блока се одвија √ A пута за сваки А подниз, затим се А блокови ролају и убацују у Б блолове у √ A пута. Локално спајање такође захтева Оn сложеност за стандардно спајање, мада са више задатака пошто вредности морају замењене уместо копиране. Линеарна претрага за проналажење новог минимума у блоку А итерира кроз √ A блокова у √ A времену. И процес прерасподеле бафера је идентичан вађењу бафера али од позади, и зати има исту временску сложеност од Оn.

После изостављања свих осим највеће сложености и сматрањем да постоји log n нивоу у спољашњој петљи спајања, а то води до крејње асимптотичке сложености од On log n за најгоре случајеве. Zа најбољи случај, где су подаци већ уређени у поретку, корак спајања се изводи у n/16 поређења за први ниво, онда n/32, затим n/64, n/128, итд. Ово је добро познат математички низ ред који се решава у Оn времену.

                                     

4.2. Анализа Меморија

Пошто блоксорт није рекурзиван и не захтева употребу динамичке алокације меморије, онда то доводи до константног стека и коришћења простора гомиле. Користи О1 помоћну меморију, која прихвата Оlоg n битова и прати интервал од А до Б који не може бити већи од 32 или 64 на 32-битним и 64-битним системима, и зато упрошћава на О1 простор за било који низ који се може алоцирати.

                                     

4.3. Анализа Стабилност

Иако су се елементи током блоксорта испомерали, свака операција и првобитно уређење се може вратити по завршетку.

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

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

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



                                     

4.4. Анализа Адаптивност

Блоксорт је адаптивно сортирање са два нивоу: први, прескаче А и Б поднизове који су већ у сортираном поретку. Затим, када А и Б треба да се споје и поделе на блокове једнаких величина, А блокови се само ролају кроз Б све док је то неопходно, и одмах после је сваки блок спојен са вредностима Б. Што су више првобитно били уређени подаци, толико ће мање бити Б вредности које треба спојити са А.

                                     

5. Предности

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

                                     

6. Мане

Блок сорт не користи сортиране интервале података на нивоу тако добро као неки други алгоритми, попут Тимсорт. Само проверава за сортиране интервале на два предефинисана нивоу: А Б поднизови и А и Б блокови. Такође теже га је имплементирати у односу на алгоритам сортирања спајањем.

Users also searched:

...