#include "stdafx.h"
#include <iostream>
#include <string>
#include <ctime>
using namespace std;
 
const int length = 4;
 
struct Item
{
    char key [length+1];
    Item * next;
};
 
struct List
{
    Item * first;
    Item * last;
};
 
List queue; // vstup (a pozdeji vystup)
 
const int buckets = 10;
List arr [buckets]; // prihradky
 
void clear (List &L)
{
    L.first = nullptr;
    L.last = nullptr;
}
 
void add (char * value)
{
    Item * p = new Item;
 
    for (int i = 0; i < length; i++)
        p->key[i] = value[i];
 
    p->key[length] = 0;
 
    if (queue.first == nullptr)
        queue.first = p;
    else
        queue.last->next = p;
 
    queue.last = p;
    p->next = nullptr;
}
 
void insert (List &L, Item * p)
{
 
    if (L.first == nullptr)
        L.first = p;
    else
        L.last->next = p;
 
    L.last = p;
    p->next = nullptr;
}
 
void print ()
{
    Item * p = queue.first;
    while (p != nullptr)
    {
        cout << p->key << endl;
        p = p->next;
    }
}
 
void join (List &T, List &S)
{
    if (S.first != nullptr)
    {
        if (T.first == nullptr)
            T.first = S.first;
        else 
            T.last->next = S.first;
        T.last = S.last;
    }
 
}
 
void select (int d)
{
    for (int i = 0; i < buckets; i++)
        clear (arr[i]);
 
    Item * p = queue.first;
    while (p != nullptr)
    {
        char c;
        c = p->key[d];
        int k = c - '0';
        Item *  n = p->next; // zapamatovat
        insert (arr[k] , p);
        p = n;
 
    }
    clear (queue);
    for (int i = 0; i < buckets; i++)
        join (queue, arr[i]);
 
}
 
void sort ()
{
    for (int d = length - 1; d >= 0; d--)
        select (d);
}
 
int main()
{
    clear (queue);
    add ("1234");
    add ("4111");
    add ("4244");
    add ("4233");
    add ("1222");
    sort ();
    print ();
 
    cout << "Konec programu" << endl;
    system ("pause");
    return 0;
}