Bucketsort

Necht A je konecna abeceda velikosti m s linearnim usporadanim. Bez ujmy na obecnosti muzeme predpokladat, ze mnozina A={1, 2, ..., m} je usporadana obvyklym zpusobem. Usporadani na A je obvyklym zpusobem rozsireno na usporadani na slovech nad abecedou A.

Definice: Necht x = x₁...x_k a y = y₁...y_l jsou slova nad A, t.j. x_i, y_i jsou prvky A. Potom x je mensi nez y v algebraickem usporadani (x < y), pokud existuje i, 0<=i<=k, takove, ze x_j = y_j pro vsechna 1<=j<=i a bud i = k nebo i < k, i < l a zaroven x_i+1 < y_i+1.

V teto sekci se zabyvame nasledujicim problemem: Mame dano n slov x¹, x², ..., xⁿ nad abecedou A={1, ..., m} a mame je setridit (podle abecedniho usporadani).

Existuje mnoho ruznych zpusobu uchovavani slov. Jedna oblibena metoda skladuje vsechna slova v obecnem prostoru zvanem prostor retezcu. Kazda retezcova promenna se sklada z ukazatele do prostoru retezcu a mista obsahujiciho aktualni delku daneho retezce.

Zakladni myslenka bucketsortu se nejlepe vysvetluje na specialnim pripade, kdy vsechna slova maji delku 1, t.j. vstup se sklada z n cisel mezi 1 a m. Bucketsort zacina s m prazdnymi kbelicky. Pote zpracovavame cislo za cislem a hazime xⁱ do xⁱ-teho kbelicku. Nakonec projdeme po rade vsechny kbelicky a posbirame setridene prvky.

Vysvetleme nyni nektere implementacni detaily. Kbelicky jsou linearni seznamy, hlavy techto seznamu jsou ulozeny v poli K[1..m]. Na pocatku vytvorime m prazdnych seznamu. To zvladneme jednoduse v case O(m). Pri zpracovani xⁱ musime vzit K[xⁱ] a vlozit xⁱ do prislusneho seznamu. To zvladneme v case O(1), pokud vkladame xⁱ na zacatek seznamu nebo na jeho konec. V druhem pripade si musime navic udrzovat ukazatel na konec seznamu. Takto muzeme rozdelit n slov v case O(n). Nakonec musime vybrat kbelicky. Projdeme pole K a konec j-teho seznamu napojime na hlavu nasledujiciho. To zabere cas O(m), pokud pole K obsahuje ukazatele take na konce seznamu, O(n+m) jinak. Celkova delka vsech m seznamu je n. V obou pripadech vyzaduje operace cas O(m+n). Nez pokrocime dale, probereme jeste jeden detail. Mame vkladat xⁱ na zacatek nebo na konec xⁱ-teho seznamu? Pokud pridavame na konec, poradi prvku xⁱ, x^j, kde xⁱ=x^j, zustane zachovano (bucketsort je stabilni). To bude hrat dale vyznamnou roli.

Postoupime k mirne slozitejsimu pripadu. Slova xⁱ, 1<=i<=n, maji stejnou delku |xⁱ|=k.
xⁱ = xⁱ₁xⁱ₂...xⁱ_k,  xⁱ_j je prvkem A
Existuji dva zpusoby, jak zobecnit nas zakladni algoritmus.

V prvnim z nich tridime nejprve podle prvniho pismene. To rozdeli slova do m skupin, nektere mohou byt prazdne. Kazdou ze skupin pote setridime podle druheho pismene, ..., dokud nejsou skupiny jednoprvkove. Tento pristup ma znacnou nevyhodu. Skupiny se sice stale zmensuji, ale slozitost bucketsortu je vzdy alespon velikost abecedy, takze pro male skupiny je overhead velky. Celkovy cas muze byt az O(n.k.m).

Druhym zpusobem tridime nejprve podle posledniho (k-teho) pismene. Pote tridime vsech n slov podle predposledniho pismene. Zasadni poznatek je, ze nyni jsou slova setridena podle poslednich dvou pismen, protoze bucketsort je stabilni. Tridime podle (k-2)-heho pismene, ... Druhy pristup vyzaduje k pruchodu pres mnozinu n slov. Kazdy pruchod stoji O(n+m), takze celkem vyzaduje tento pristup cas O(k.(n+m)).

Lze toto jeste zlepsit? Uvazme priklad pro m=4, n=5 a k=3 a pet slov 123, 124, 223, 324, 321. Po prvnim pruchodu bude nasledujici situace:

• kyblicek 1: 321
• kyblicek 2:
• kyblicek 3: 123, 223
• kyblicek 4: 124, 324

• kyblicek 1:
• kyblicek 2: 321, 123, 223, 124, 324
• kyblicek 3:
• kyblicek 4:

• kyblicek 1: 123, 124
• kyblicek 2: 223
• kyblicek 3: 321, 324
• kyblicek 4:

Povsimneme si, ze jsme posbirali celkem 12 kyblicku, ackoliv pouze 7 nich bylo neprazdnych. Celkovy cas by se zlepsil, pokud bychom dopredu vedeli, ktere kyblicky vybrat v kterem pruchodu. Predpokladejme, ze v j-tem pruchodu je s_j kyblicku neprazdnych. Kdybychom mohly vynechat prazdne kyblicky, j-ty pruchod by stal O(n+s_j), protoze s_j<=n, cena pruchodu by byla jen O(n) misto O(n+m).

Existuje jednoduchy zpusob jak, zjistit, ktere kyblicky jsou neprazdne v j-tem pruchodu (tim se mysli pri trideni podle j-teho pismene, tedy vlastne (k-j+1)-ty pruchod), t.j. ktera pismena se vyskytuji na j-tem miste. Vytvorte mnozinu {(j,x^k_j); 1<=j<=k, 1<=i<=n} velikosti n.k a setridte bucketsortem podle druhe a pote podle prvni slozky. j-ty kyblicek ted obsahuje (usporadane) vsechny znaky, ktere se vyskytuji na j-te miste. Cena prvniho pruchodu je O(n.k+m), cena druheho O(n.k+k). Celkova cena je tak O(n.k+m).

Nez podame uplny popis algoritmu, podivame se na rozsireni na slova libovolne delky. xⁱ = xⁱ₁...xⁱ_li, 1<=i<=n; l_i je delka x_i. Postupujeme jako v predchozim pripade, musime se pouze ujistit, ze x_i je poprve posuzovano teprve, kdyz tridime podle l_i-teho pismene. Nejprve tedy setridime slova podle delky. Toto vede k nasledujicimu algoritmu. L=Suma l_i >= n.

1. Zjistete delku slov x_i, 1<=i<=n, a utvorte dvojice (l_i, ukazatel na x_i). To zabere cas O(L).
2. Setridte dvojice (l_i, ukazatel na x_i) bucketsortem podle prvni komponenty. Potom k-ty kyblicek obsahuje vsechna slova delky k (v linearnim seznamu). Tento seznam oznacme length[k]. Cena kroku 2 je O(n+L), protoze L kyblicku jiste postaci.
3. Utvorte L dvojic (j, xⁱ_j), 1<=i<=n, 1<=j<=l_i, a setridte je podle druhe a pote podle prvni komponenty. Nonempty[j], 1<=j<=l_max = max(l₁, ..., l_n budiz j-ty kyblicek po druhem pruchodu. Nonempty[j] obsahuje (setridena) vsechna pismena, ktera se objevi na j-te pozici. Odstrante duplikaty z Nonempty[j]. Cena kroku 3 je O(L+m) + O(L+l_max) = O(L+m).
4. Popiseme konecne trideni slov xⁱ. Vsechny seznamy v nasledujicim jsou fronty, hlava kazdeho seznamu obsahuje i ukazatel na posledni prvek. x je retezcova promenna a x_j je j-te pismeno retezce x.
   

   (1)  W <- empty queue;
   (2)  for k from 1 to m do S[k] <- empty queue od;
   (3)  for j from lmax to 1
   (4)  do add length[j] to the front of W and call the new queue W;
   (5)     while W != 0
   (6)     do let x be the first element of W, delete x from W;
   (7)        add x to the end of S[xj]
   (8)     od;
   (9)     while Nonempty[j] != 0
   (10)    do let k be the first element of Nonempty[j];
   (11)       delete k from Nonempty[j];
   (12)       add S[k] to the end of W;
   (13)       set S[k] to the empty queue;
   (14)    od
   (15) od.