Bibliotečko sortiranje

Bibliotečko sortiranje je algoritam sortiranja baziran na sortiranju umetanjem, koji koristi razmake unutar niza kako bi ubrzao uzastopna umetanja. Ovaj algoritam se još naziva i sortiranje umetanjem sa razmakom, a bibliotečkim sortiranjem se naziva zbog sledeće analogije: Pretpostavimo da bibliotekar ređa knjige po azbučnom redu na dugačkoj polici, počevši od A-ova na levom kraju i nastavljajući nadesno duž police bez razmaka između knjiga sve do kraja Š-ova. Ako bibliotekar dobije novu knjigu koja pripada B sekciji, kada joj pronađe odgovarajuće mesto, moraće da premesti sve knjige od tog mesta unutar B-ova pa sve do poslednjeg Š-a, kako bi napravio mesto za novu knjigu. Ovo je sortiranje umetanjem. Međutim, ako bi ostavio razmak posle svakog slova, dokle god ima mesta posle B-a, on će morati da premesti samo par knjiga na B da bi napravio mesta za novu. Ovo je osnovni princip bibliotečkog sortiranja.

Algoritam su predložili Majkl A. Bender, Martin Farak-Kolton i Migel Mosteiro 2004. godine, a objavili 2006.

Kao i sortiranje umetanjem na kom je baziran, ovaj algoritam je jedan stabilan algoritam sortiranja poređenjem. Pokazalo se da postoji velika verovatnoća da vremenska složenost bude O(nlogn), što je blisko kviksortu, za razliku od sortiranja umetanjem koje ima O(n^2) vremensku složenost. Mehanizam koji je korišćen je veoma sličan mehanizmu propuštajuće liste. Nema potpune implementacije u radu, niti tačno određenih algoritama bitnih delova, kao što su umetanje i rebalansiranje. Dalje informacije bi bile neophodne za poređenje efikasnosti bibliotečkog sortiranja sa drugim sortiranjima u praksi.

U poređenju sa osnovnim sortiranjem umetanja, mana bibliotečkog sortiranja je to što zahteva dodatni prostor za razmake. Količina i raspored tog prostora bi zavisili od implementacije. U radu se navodi da je potrebna veličina niza (1+ε)n, ali bez daljih naznaka o tome kako odabrati. Jedna od slabosti sortiranja umetanjem je to što bi moglo zahtevati visok broj operacija zamene i što bi moglo biti skupo u zavisnosti od skupoće pisanja memorije. Bibliotečko sortiranje može poboljšati ove stvari u koraku umetanja, ali i povećava cenu u koraku rebalansiranja.

Implementacija

Algoritam

Uzmimo niz od n elemenata. Biramo razmak koji nameravamo da obezbedimo. Onda imamo konačni niz od (1+ε)n elemenata. Algoritam radi u logn krugova. U svakom krugu umećemo onoliko elemenata koliko u konačnom nizu već ima, pre nego što rebalansiramo niz. Za pronalaženje pozicije umetanja, primenjujemo binarnu pretragu u konačnom nizu i onda zamenjujemo prateće elementedok ne naiđemo na prazno mesto. Na kraju kruga vršimo rebalansiranje konačnog niza, tako što unosimo prazna mesta između svaka dva elementa.

Slede tri važna koraka u algoritmu: 1. Binarna Pretraga: Pronalaženje pozicije za umetanja primenom binarne pretrage na već umetnute elemente. Ovo se može odraditi tako što bi se pomerali ulevo ili udesno ukoliko bi pogodili prazno mesto u središnjem elementu. 2. Umetanje: Umetanje elementa na pronađenu poziciju i zamena pratećih elemenata za 1 poziciju dok se ne pogodi prazno mesto. 3. Rebalansiranje: Umetanje praznih mesta između svaka dva elementa u nizu. Ovo zahteva linearno vreme, i pošto ima logn krugova, potpuno rebalansiranje zahteva samo O(nlogn) vremena.

Pseudo-kod

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]

Ovde binarysearch(A, k) obavlja binarnu pretragu u prvih k elemenata od A, preskačući praznine. Umetanje bi trebalo da preferira razmake u odnosu na popunjene elemente.