#include <iostream>
#include <vector>
#include <algorithm>
#include  <cmath>
#include <iomanip>

using namespace std;

template <typename T> 
vector<T> CountSort(const vector<T> & ary){
    vector<T> result(ary.size());

    auto big = *max_element(begin(ary), end(ary));
    auto small = *min_element(begin(ary), end(ary));

    vector<int> counts(big.Key() - small.Key()+ 1);
    
    for(size_t i =0; i < ary.size(); ++i) {
       size_t pos =  ary[i].Key() - small.Key();
       ++counts[pos];
    }

    for(size_t i = 1; i < counts.size(); ++i) {
       counts[i] += counts[i-1];
    }

    for(int i = ary.size()-1; i >= 0; --i) {
       int pos = ary[i].Key() - small.Key() ;
       result[counts[pos]-1] = ary[i];
       --counts[pos];
    }

    return result;
};

class ItemT {
    public:
        ItemT() = default;
        ItemT(int newValue) : value{newValue}{};

        int Data(void) const {
           return value; 
        }

        static void SetPos(int newPos) {
             pos = newPos; 
             divValue = pow(10,newPos);
        }

        int Key(void) const {
           return value/divValue % 10;
        }

        bool operator <(const ItemT  & other) const {
           int me = value/divValue % 10;
           int you = other.value/divValue % 10;
           return me < you;
        }

        bool operator >(const ItemT  & other) const {
           int me = value/divValue % 10;
           int you = other.value/divValue % 10;
           return me > you;
        }

    private:
        int value{0};
        inline static int divValue{0};
        inline static int pos{1};
};

using ItemLT = vector<ItemT>;

ostream & operator << (ostream  & s, const ItemT & data) ;
void PrintItems(const ItemLT & ary);


const int MOD_VALUE{10000};
int main() {
     ItemLT ary;

     srand(time(nullptr));
     char letter{'a'};

     for(int i = 0; i < 20; ++i) {
         ItemT newItem(rand() % MOD_VALUE);
         ary.push_back(newItem);
     }

     PrintItems(ary);
     cout << endl;

     int nums = ceil(log10(MOD_VALUE));

     for(int i = 0; i < nums; ++i) {
          cout << " position = " << i << endl;
         ItemT::SetPos(i);

         ary  = CountSort(ary);

          cout << endl;
          PrintItems(ary);
     } 

     PrintItems(ary);

     return 0;
}

ostream & operator << (ostream  & s, const ItemT & data) {
    s  << setw(2) << setw(5) << data.Data();
    return s;
}

void PrintItems(const ItemLT & ary){
    int items{0};
    for(auto i: ary) {
        cout << i;
        if (items >= 9) {
           cout << endl;
           items = -1;
        }  else {
           cout << ", "; }

        ++items;
    }
    cout << endl;
}