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 = 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:

Vstupni sekvence pro druhy pruchod tedy je 321, 123, 223, 124, 324. Po druhem pruchodu je situace nasledujici: Vstupni sekvence pro treti pruchod je 321, 123, 223, 124, 324 a situace po tretim pruchodu vypada nasledovne: Vysledna sekvence je 123, 124, 223, 321, 324.

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. Zjistete delku slov xi, 1<=i<=n, a utvorte dvojice (li, ukazatel na xi). To zabere cas O(L).
  2. Setridte dvojice (li, ukazatel na xi) 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, xij), 1<=i<=n, 1<=j<=li, a setridte je podle druhe a pote podle prvni komponenty. Nonempty[j], 1<=j<=lmax = max(l1, ..., ln 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+lmax) = O(L+m).
  4. Popiseme konecne trideni slov xi. Vsechny seznamy v nasledujicim jsou fronty, hlava kazdeho seznamu obsahuje i ukazatel na posledni prvek. x je retezcova promenna a xj 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.
    


Zdrojem pro muj referat byla kniha profesora Kurta Mehlhorna Data Structures and Algorithms, konkretne jeji prvni cast Sorting and Searching, kapitola 2 - Sorting.

Ohlasy uvitam na adrese mpta7488@kolej.mff.cuni.cz.