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 = x1...xk a y = y1...yl jsou slova nad A, t.j. xi, yi jsou prvky A. Potom x je mensi nez y v algebraickem usporadani (x < y), pokud existuje i, 0<=i<=k, takove, ze xj = yj pro vsechna 1<=j<=i a bud i = k nebo i < k, i < l a zaroven xi+1 < yi+1.
V teto sekci se zabyvame nasledujicim problemem: Mame dano n slov x1, x2, ..., xn 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 xi do xi-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 xi musime vzit K[xi] a vlozit xi do prislusneho seznamu. To zvladneme v case O(1), pokud vkladame xi 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 xi na zacatek nebo na konec xi-teho seznamu? Pokud pridavame na konec, poradi prvku xi, xj, kde xi=xj, zustane zachovano (bucketsort je stabilni). To bude hrat dale vyznamnou roli.
Postoupime k mirne slozitejsimu pripadu. Slova xi, 1<=i<=n,
maji stejnou delku
|xi|=k.
xi = xi1xi2...xik,
xij 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:
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 sj kyblicku neprazdnych. Kdybychom mohly vynechat prazdne kyblicky, j-ty pruchod by stal O(n+sj), protoze sj<=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,xkj); 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. xi = xi1...xili, 1<=i<=n; li je delka xi. Postupujeme jako v predchozim pripade, musime se pouze ujistit, ze xi je poprve posuzovano teprve, kdyz tridime podle li-teho pismene. Nejprve tedy setridime slova podle delky. Toto vede k nasledujicimu algoritmu. L=Suma li >= n.
(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.