

#include "stdafx.h"
#include 
#include 
#include 
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;
}