Lexikografické třídění

#include <iostream>
using namespace std;
 
const int D = 20;  // delka retezce
const int K = 256; // pocet prihradek
 
struct Item
{
    char key [D+1]; // retezce ukoncene 0
    Item* next;
};
 
struct List // prihradka
{
    Item * first;
    Item * last;
};
 
void clear (List & p)
{
    p.first = nullptr;
    p.last = nullptr;
}
 
void insertLast (List & p, Item * t)
{
    if (p.first == nullptr)
        p.first = t;
    else
        p.last->next = t;
    p.last = t;
    t->next = nullptr;
}
 
/*
void join (List & target, List & source)
{
    Item* t = source.first;
    while (t != nullptr)
    {
        Item* nxt = t->next;
        insertLast (target, t);
        t = nxt;
    }
}
*/
 
void join (List & target, List & source)
{
    if (source.first != nullptr)
    {
        if (target.first == nullptr)
        {
            target.first = source.first;
            target.last = source.last;
        }
        else
        {
            target.last->next = source.first;
            target.last = source.last;
        }
    }
}
 
List tab [K]; // pole prihradek
 
List queue; // vstupni a vystupni posloupnost
 
void sort (int r) // trideni podle r-teho znaku
{
    // vymazat prihradky
    for (int i = 0; i < K; i++) clear (tab [i]);
 
    // rozhazet do prihradek
    Item* t = queue.first;
    while (t != nullptr)
    {
        int inx = t->key [r]; // cislo prihradky
        Item* nxt = t->next; // uschovat, t->next buze zmeneno
        insertLast (tab [inx], t); // pridat na konec prihradky
        t = nxt;
    }
 
    // vymazat queue, bude slouzit pro vystup
    clear (queue);
 
    // sloucit 
    for (int i = 0; i < K; i++)
        join (queue, tab [i]);
}
 
void lexiSort ()
{
    for (int r = D-1; r >= 0; r--)
        sort (r);
}
 
void add (const char* s)
{
    Item* t = new Item;
    int len = strlen (s);
    for (int i = 0; i < D; i++)
    {
        if (i < len)
            t->key [i] = s [i];
        else
            t->key [i] = 0;
    }
    t->key [D] = 0;
    insertLast (queue, t);
}
 
void tisk ()
{
    Item* t = queue.first;
    while (t != nullptr)
    {
        cout << t->key << endl;
        t = t->next;
    }
}
 
int main()
{
    clear (queue);
 
    /*
    add ("751");
    add ("123");
    add ("111");
    */
 
    srand (time (nullptr));
    const int N = 1000;
    for (int i = 1; i <= N; i++)
    {
        int v = (rand () % 1000) + 1000 * (rand () % 1000);
        string s = to_string (v);
        while (s.length () < D) s = '0' + s;
        add (s.c_str ());
    }
 
    lexiSort ();
    tisk ();
 
    cout << "O.K." << endl;
}