====== Lexikografické třídění ======
Příhrádkové třídění - skripta 5.4.1
Lexikografické třídění - skripta 5.4.2
* Budeme třídit řetězce dlouhé **D** znaků
* Každý znak může nabývat **K** hodnot, vytvoříme **K** příhrádek
* V našem programu budeme třídit jen řetězce složené z číslic, stačilo by 10 příhrádek
* Pro třídění řetězců obsahující libolovné znaky použijeme 256 příhrádek
* Budeme třídit **N** řetězců, v našem programu N použijeme jen při generování náhodných vstupních řetězců
===== Jednotlivé řetězce =====
Jednotlivé řetězce budeme ukládat do datové struktury **Item**. \\
V poli **key** budou uloženo **D** osmibitových znaků a na konec přidáme nulový znak (jen kvůli tisku řetězců).
Řetězce propojíme ukazatelem **next** do jednosměrného seznamu.
const int D = 20; // pocet pismen ve slove
struct Item
{
char key [D+1]; // znak 0 na konci
Item * next;
};
===== Jedna příhrádka =====
Jednu příhrádku budeme reprezentovat strukturou **List**.
Příhrádka bude skladovat posloupnost řetězců.
Bude obsahovat ukazatele **first** a **last** na první a poslední řetězec.
Díky **last** bude přidávání na konec seznamu jednoduchou operací ... O(1).
struct List
{
Item * first;
Item * last;
};
===== Pole příhrádek =====
**K** příhrádek budeme mít uloženo v poli **tab**.
Přístup i-té příhrádkce bude opět jednoduchá operace.
List tab [K];
=== Vstupní posloupnost řetězců ===
Pro vstupní posloupnost řetězců použijeme stený typ **List** jako pro jednotlivé příhrádky.
Proměnná **inp** bude obsahovat řetězce které máme třídit.
* Řetězce rozházíme podle r-tého znaku do příhrádek.
* A z příhrádek sesypeme zpět do proměnné **inp**.
* To budeme opakovat pro r = D-1, D-2, ...., 2, 1, 0. (znaky v poli **key** indexujeme od nuly)
Nakonec v proměnné **inp** bude výsledná setříděná posloupnost řetězců
List inp;
===== Vyprázdnění příhrádky =====
Funkce **init** má parametr předávaný odkazem (**&**), skutešný parametr se bude měnit. \\
Nastavíme ukazatele **first** a **last** na nulov0 ukazatele, to odpovídá prázdné příhrádce.
void init (List & a)
{
a.first = nullptr;
a.last = nullptr;
}
===== Přidání prvku do příhrádky =====
Funkce **add** přidá nový řetězec zadaný ukazatelem **p** na konec seznamu **a**.
//Stabilita třídění:// pokud na vstupu budou dva řetězce, které padnou do stejné příhrádky, \\
zachovají si svoje pořadí i v příhrádce a nakonec i ve výstupní posloupnosti.
void add (List & a, Item * p)
{
p->next = nullptr;
if (a.first == nullptr)
a.first = p;
else
a.last->next = p;
a.last = p;
}
===== Příhrádkové třídění podle r-tého znaku =====
Nejprve všechny příhrádky vyprázdníme (vynulujeme **first** a **last**, tím zapomeneme ukazatele na staré hodnoty).
Potom procházíme vstupní posloupnost. \\
Do proměnné **p** dáme ukazatel na první řetězec. \\
Vyzvedneme hodnotu r-tého znaku v našem řetězci a uložíme do proměnné **inx**. \\
Tím jsem získali číslo příhrádky, do které řetězec patří. \\
// Zde používáme pro číslo příhrádky ascii hodnotu znaku//, \\
// pokud bychom měli jen deset příhrádek pro číslice, museli bychom do inx uložit číslo od nuly do devíti.//
Přidáme prvek **p** do příhrádky číslo **inx**. \\
To ale nastaví p->next na nulový ukazatel (Prvek **p** bude na konci seznamu/příhrádky). \\
Ukazatel na následníka si uložíme do proměnná **t**, dříve než o něj přideme.
Cyklus **while** opakujeme pro všechny řetězce.
void sort (int r) // tridime podle r-teho pismene
{
for (int inx = 0; inx < K; inx++)
init (tab[inx]);
Item * p = inp.first;
while (p != nullptr)
{
Item * t = p->next; // zapamatovat naslednika pred odpojenim
int inx = p->key[r]; // cislo prihradky
add (tab[inx], p);
p = t;
}
Seznam vstupních hodnot již nepotřebujeme. \\
V proměnné **inp** nastavíme first i last na nulové uzazatele \\
a **inp** budete skladovat výstupní posloupnost.
Ve **for** cyklu projdeme všechny příhrádky a jejich obsah připojíme na konec **inp**.
Jako komentář je zde naznačen postupné procházení příhrádky a přidávání na konec **inp**. \\
Proměnné **p** a **t** by v tomto případě existolaly jen vrámci **{ }**, kde byly deklarovány.
Funkce **link** připojí obsah příhrádky k **inp** rychleji. \\
//Ale složitost to stejně neovlivní.//
init (inp);
for (int inx = 0; inx < K; inx++)
{
link (inp, tab[inx]);
/*
Item * p = tab[inx].first;
while (p != nullptr)
{
Item * t = p->next;
add (inp, p);
p = t;
}
*/
}
===== Celá funkce sort =====
void sort (int r) // tridime podle r-teho pismene
{
for (int inx = 0; inx < K; inx++)
init (tab[inx]);
Item * p = inp.first;
while (p != nullptr)
{
Item * t = p->next; // zapamatovat naslednika pred odpojenim
int inx = p->key[r]; // cislo prihradky
add (tab[inx], p);
p = t;
}
init (inp);
for (int inx = 0; inx < K; inx++)
{
link (inp, tab[inx]);
/*
Item * p = tab[inx].first;
while (p != nullptr)
{
Item * t = p->next;
add (inp, p);
p = t;
}
*/
}
}
===== Spojování seznamů =====
Funkce **link (a, b)** připojí na konec seznamu **a** seznam **b**.
Pokud je **b** prázdný nemáme co dělat.
Pokud je **a** prázdný stavá se **b.first** prvním prvkem seznamu **a**. \\
V opačném případě propojíme poslední prvek původního seznamu **a** se prvním prvek **b**.
Poslední prvek **b** se stává poslední prvkem **a**.
void link (List & a, List & b)
{
if (b.first != nullptr)
{
if (a.first == nullptr)
a.first = b.first;
else
a.last->next = b.first;
a.last = b.last;
}
}
===== Lexikografické třídění =====
Celé lexikografické třídění je pouze několik příhrádkových třídění.
Funkce **sort** vstup získává ze seznamu **inp** a do stejné proměné uloží svůj výstup, //
který je vstupem pro další **sort**, //
nakonec v **inp** nalezneme setříděný výsledek.
Třídíme postupně podle posledního písmene (s indexem **D-1**) \\
až nakonec podle podle prvního písmene (s indexem **0**).
//Pokud třídíme řetězce tvořené číslicemi.// \\
Tříděním podle posledního písmene na začátek dostaneme řětězce končící **0**, na konci budou řětězce končící **9**.
Závěrečné třídění podle prvního písmene (s indexem 0, v případě čísel: číslice s největší váhou) \\
umístí na zacčátek posloupnosti řětězce začínající **0**, na konci budou řětězce začínající **9**. \\
Stabilita třídění zajistí, že řetězce zůstanou setříděné podle nižžších řádů.
int main ()
{
/* ... */
for (int r = D-1; r >= 0; r--)
sort (r);
/* ... */
}
===== Složitost =====
Pokud třídíme **N** řetězců musíme **D**-krát rozházet prvky do **K** příhrádek, \\
Práce s jedním prvkem je **O(1)**, neboť nic nehledáme a provádíme stále stejný počet instrukcí. \\
**K** a **D** jsou konstanty, tak výsledná složitost je **O(N)**.
Ale je to za cenu, že jsem si pevně stanovili počet příhrádek a délku řetězců.
===== Vyváření řetězců =====
Funkce **create (int c)** uloží celé číslo **c** do nově vytvořeného prvku typu **Item**.
S index **i** postupujeme od konce řetězce (**D-1**). \\
Zbytek po dělení čísla **c** deseti přičteme k ascii kódu číslice nula ( nula v jednoducých uvozovkách pro znakové konstanty, **'0'** ) \\
A číslici uložíme jako i-té písmeno. \\
Číslo **c** vydělíme deseti (celočíselné dělění zbytek zahodí) a pokračujeme s vyššími řády.
Na konec řetězce přidáme nulový znakem (znak s vniřním kódem nula, **0** bez uvozovek, tj. číslo nula ).
Typ **int** bývá 32-bitový, tak získáme jen deset číslic a ve vyšších řádech budou jen nuly.
Item * create (int c)
{
Item * p = new Item;
for (int i = D - 1; i >= 0; i--)
{
p->key[i] = '0' + c % 10;
c = c / 10;
}
p->key[D] = 0; // znak nula na konci
return p;
}
===== Funkce main ====
* Vygenerujeme N řetězců
* Spustíme třídění
* Zkontrolujeme pořadí
Při tisku a porovnávání pomocí **strcmp** musí být řetězce ukončeny nulovým znakem.
int main ()
{
init (inp);
srand (time(NULL));
for (int i = 0; i < N; i++)
add (inp, create (rand() % 10000));
for (int r = D-1; r >= 0; r--)
sort(r);
bool ok = true;
Item * p = inp.first;
while (p != nullptr)
{
cout << p->key;
Item * t = p->next;
if (t != nullptr && strcmp (t->key , p->key) < 0)
{ ok = false; cout << " CHYBA"; }
cout << endl;
p = t;
}
if (ok)
cout << "O.K." << endl;
}
===== Celý program =====
#include
#include
#include
using namespace std;
const int N = 20;
const int D = 20; // pocet pismen ve slove
const int K = 256; // pocet prihradek
struct Item
{
char key [D+1]; // znak 0 na konci
Item * next;
};
struct List
{
Item * first;
Item * last;
};
List inp; // vstup a vystup
List tab [K]; // pole prihradek
void init (List & a)
{
a.first = nullptr;
a.last = nullptr;
}
void add (List & a, Item * p)
{
p->next = nullptr;
if (a.first == nullptr)
a.first = p;
else
a.last->next = p;
a.last = p;
}
void link (List & a, List & b) // pridat b na konec a
{
if (b.first != nullptr)
{
if (a.first == nullptr)
a.first = b.first;
else
a.last->next = b.first;
a.last = b.last;
}
}
Item * create (int c)
{
Item * p = new Item;
for (int i = D - 1; i >= 0; i--)
{
p->key[i] = '0' + c % 10;
c = c / 10;
}
p->key[D] = 0; // znak nula na konci
return p;
}
void sort (int r) // tridime podle r-teho pismene
{
for (int inx = 0; inx < K; inx++)
init (tab[inx]);
Item * p = inp.first;
while (p != nullptr)
{
Item * t = p->next; // zapamatovat naslednika pred odpojenim
int inx = p->key[r]; // cislo prihradky
add (tab[inx], p);
p = t;
}
init (inp);
for (int inx = 0; inx < K; inx++)
{
link (inp, tab[inx]);
/*
Item * p = tab[inx].first;
while (p != nullptr)
{
Item * t = p->next;
add(inp, p);
p = t;
}
*/
}
}
int main ()
{
init (inp);
srand (time (nullptr));
for (int i = 0; i < N; i++)
add (inp, create (rand() % 10000));
for (int r = D-1; r >= 0; r--)
sort(r);
bool ok = true;
Item * p = inp.first;
while (p != nullptr)
{
cout << p->key;
Item * t = p->next;
if (t != nullptr && strcmp (t->key , p->key) < 0)
{ ok = false; cout << " CHYBA"; }
cout << endl;
p = t;
}
if (ok)
cout << "O.K." << endl;
}