Библиотечко сортирање

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

Алгоритам су предложили Мајкл А. Бендер, Мартин Фарак-Колтон и Мигел Мостеиро 2004. године, а објавили 2006.

Као и сортирање уметањем на ком је базиран, овај алгоритам је један стабилан алгоритам сортирања поређењем. Показало се да постоји велика вероватноћа да временска сложеност буде О(nlogn), што је блиско квиксорту, за разлику од сортирања уметањем које има О(n^2) временску сложеност. Механизам који је коришћен је веома сличан механизму пропуштајуће листе. Нема потпуне имплементације у раду, нити тачно одређених алгоритама битних делова, као што су уметање и ребалансирање. Даље информације би биле неопходне за поређење ефикасности библиотечког сортирања са другим сортирањима у пракси.

У поређењу са основним сортирањем уметања, мана библиотечког сортирања је то што захтева додатни простор за размаке. Количина и распоред тог простора би зависили од имплементације. У раду се наводи да је потребна величина низа (1+ε)n, али без даљих назнака о томе како одабрати. Једна од слабости сортирања уметањем је то што би могло захтевати висок број операција замене и што би могло бити скупо у зависности од скупоће писања меморије. Библиотечко сортирање може побољшати ове ствари у кораку уметања, али и повећава цену у кораку ребалансирања.

Имплементација

Алгоритам

Узмимо низ од n елемената. Бирамо размак који намеравамо да обезбедимо. Онда имамо коначни низ од (1+ε)n елемената. Алгоритам ради у logn кругова. У сваком кругу умећемо онолико елемената колико у коначном низу већ има, пре него што ребалансирамо низ. За проналажење позиције уметања, примењујемо бинарну претрагу у коначном низу и онда замењујемо пратеће елементедок не наиђемо на празно место. На крају круга вршимо ребалансирање коначног низа, тако што уносимо празна места између свака два елемента.

Следе три важна корака у алгоритму: 1. Бинарна Претрага: Проналажење позиције за уметања применом бинарне претраге на већ уметнуте елементе. Ово се може одрадити тако што би се померали улево или удесно уколико би погодили празно место у средишњем елементу. 2. Уметање: Уметање елемента на пронађену позицију и замена пратећих елемената за 1 позицију док се не погоди празно место. 3. Ребалансирање: Уметање празних места између свака два елемента у низу. Ово захтева линеарно време, и пошто има logn кругова, потпуно ребалансирање захтева само О(nlogn) времена.

Псеудо-код

proc rebalance(A, begin, end)

   r ← end
   w ← end * 2
   while r >= begin
       A[w+1] ← gap
       A[w] ← A[r]
       r ← r - 1
       w ← w - 2

proc sort(A)
   n ← length(A)
   S ← new array of n gaps
   for i ← 1 to floor(log2(n) + 1)
       for j ← 2^i to 2^(i+1)
           ins ← binarysearch(S, 2^(i-1))
           insert A[j] at S[ins]

Овде binarysearch(A, k) обавља бинарну претрагу у првих k елемената од A, прескачући празнине. Уметање би требало да преферира размаке у односу на попуњене елементе.