

#include "pch.h"
#include 
#include  /* srand, rand */
#include    /* time */

using namespace std;

const int P = 256; // pocet prihradek 
const int Z = 16;  // pocet pismen v retezci

struct Item
{
    char key [Z+1];
    Item * next;
};

struct List
{
    Item * first;
    Item * last;
};

List inp; // vstupni posloupnost
List tab [P]; // pole prihradek

inline void init (List & a)
{
    a.first = nullptr;
    a.last = nullptr;
}

inline 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;
    }
}
void sort(int i) // setridit inp podle i-teho znaku
{
    for (int j = 0; j < P; j++) {
        init(tab[j]);
    }
    Item* p = inp.first;
    while (p != NULL) {
        int k = p->key[i];
        Item* pom = p->next;
        add(tab[k], p);
        p = pom;
    }
    init(inp);
    for (int j = 0; j < P; j++) {
        link (inp, tab[j]);
        /*
        Item* p = tab[j].first;
        while (p != NULL) {
            Item* pom = p->next;
            add(inp ,p);
            p = pom;
        }
        */
    }
}

int main()
{
    const int N = 1000;
    srand (time (NULL));
    for (int i = 0; i < N; i++)
    {
        int c = rand() % 50000;
        Item * p = new Item;
        for (int i = Z-1; i >=0; i--)
        {
            p->key[i] = '0' + c % 10;
            c /= 10;
        }
        p->key[Z] = 0; // ukonceni retezce
        add (inp, p);
    }


    for (int i = Z-1; i >= 0; i--) {
        sort(i);
    }

    bool ok = true;
    Item * p = inp.first;
    while (p != nullptr)
    {
        cout << p->key;
        Item * nxt = p->next;
        if (nxt != nullptr && strcmp (nxt->key , p->key) < 0) { ok = false; cout << " CHYBA"; }
        cout << endl;
        p = nxt;
    }
    if (ok)  cout << "O.K." << endl; 


}