Příklady naleznete v GIT repository http://gitlab.fjfi.cvut.cz/culikzde/zalg
Nejjednodušší přístup k zdrojovým souborům na zmíněné webové stránce je tlačítko "Download", schované vedle tlačítka "Clone". (A nemusíte se zabývat následujícím odkazem popisujícím přistup k GIT.)
Stručný návod pro přístup k GIT git
Přehled některých vývojových prostředí ide
Videa o algoritmech video
QuickSort http://www.youtube.com/watch?v=7h1s2SojIRw
QuickSort Analysis http://www.youtube.com/watch?v=-qOVVRIZzao
Jenny's lectures, QuickSort https://www.youtube.com/watch?v=QN9hnmAgmOc
AVL tree http://www.youtube.com/watch?v=jDM6_TnYIqE
Jenny's lectures, AVL tree http://www.youtube.com/watch?v=YWqla0UX-38
Příhrádkové třídění - skripta 5.4.1
Lexikografické třídění - skripta 5.4.2
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; };
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; };
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];
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.
Nakonec v proměnné inp bude výsledná setříděná posloupnost řetězců
List inp;
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; }
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; }
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; } */ }
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; } */ } }
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; } }
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); /* ... */ }
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ů.
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; }
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; }
#include <iostream> #include <time.h> #include <string.h> 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; }