No v podstate to neco takoveho je
... jde o normalni lexikograficke trideni, ktere ale na zmateni nepritele:
1. si slova nejdriv roztridi podle jejich delek
2. vytvori dvojice [poradi ve slove;pismeno] (napr. pro slovo ahoj vznikne [1,a], [2,h], [3,o], [4,j]) a ty setridi podle abecedy podle pismen
3. pak uz takto setrideny seznam jeste jednou setridi podle poradi (oboji je bucket-sortem, takze je to stabilni)
4. takto setridene dvojice rozdelim do mnozin (nazveme je S
i) podle stejneho poradi pismene ve slove (napr. [1,a] a [1,d] jdou do stejne mnoziny, ale [2,a] do dalsi; de facto se jen odstrani duplicity)
5. zacne hlavni cyklus -- postupuju podle poradi pismenek ve slove, od konce (tj. kdyz nejdelsi tridene slovo ma delku 20, jdu od 20 k 1), kde v kazdem (i-tem) kroku:
I. rozdelim vsechna slova delky >= i do mnozin T
x podle i-teho pismena (tj. vsechna slova, ktera maji na i-tem miste stejne pismenko, padnou do stejne mnoziny), slova kratsi nez i pismen zatim neuvazuji
II. vyberu vsechny neprazdne mnoziny T
x (podle obsahu S
i vim, ktere to jsou), a seradim je za sebe.
III. k vysledku pridam slova delky i-1 a jdu na dalsi krok (opet pouzivam k deleni podle i-teho pismena bucket-sort, takze je operace stabilni a zachovava poradi podle uz projitych kroku)
6. na konci vsechno setridim i podle prvniho pismene a dostanu spravne setridena slova
Takhle jsem to chapal ja, pred zkouskou koncem prosince ... tak ale nevim, jestli a jak moc to bylo spravne (k praktickemu overeni nedoslo
). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.
No v podstate to neco takoveho je :P ... jde o normalni lexikograficke trideni, ktere ale na zmateni nepritele:
1. si slova nejdriv roztridi podle jejich delek
2. vytvori dvojice [poradi ve slove;pismeno] (napr. pro slovo ahoj vznikne [1,a], [2,h], [3,o], [4,j]) a ty setridi podle abecedy podle pismen
3. pak uz takto setrideny seznam jeste jednou setridi podle poradi (oboji je bucket-sortem, takze je to stabilni)
4. takto setridene dvojice rozdelim do mnozin (nazveme je S[sub]i[/sub]) podle stejneho poradi pismene ve slove (napr. [1,a] a [1,d] jdou do stejne mnoziny, ale [2,a] do dalsi; de facto se jen odstrani duplicity)
5. zacne hlavni cyklus -- postupuju podle poradi pismenek ve slove, od konce (tj. kdyz nejdelsi tridene slovo ma delku 20, jdu od 20 k 1), kde v kazdem (i-tem) kroku:
I. rozdelim vsechna slova delky >= i do mnozin T[sub]x[/sub] podle i-teho pismena (tj. vsechna slova, ktera maji na i-tem miste stejne pismenko, padnou do stejne mnoziny), slova kratsi nez i pismen zatim neuvazuji
II. vyberu vsechny neprazdne mnoziny T[sub]x[/sub] (podle obsahu S[sub]i[/sub] vim, ktere to jsou), a seradim je za sebe.
III. k vysledku pridam slova delky i-1 a jdu na dalsi krok (opet pouzivam k deleni podle i-teho pismena bucket-sort, takze je operace stabilni a zachovava poradi podle uz projitych kroku)
6. na konci vsechno setridim i podle prvniho pismene a dostanu spravne setridena slova
Takhle jsem to chapal ja, pred zkouskou koncem prosince ... tak ale nevim, jestli a jak moc to bylo spravne (k praktickemu overeni nedoslo :-P). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.