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

using namespace std;

void couting_sort(vector<int>& array)
{
    if (array.size() == 0) return;
    auto p = minmax_element(array.begin(),array.end());
    int min = *p.first;
    int dist = *p.second - min + 1;
    vector<int> t(dist,0);

    for(auto i: array) t[i-min]++;

    for(int i = 0, idx = 0; i < t.size(); ++i)
        for(int j = 0; j < t[i]; ++j)
            array[idx++] = i+min;

};

void couting_sort_rev(vector<int>& array)
{
    if (array.size() == 0) return;
    auto p = minmax_element(array.begin(),array.end());
    int min = *p.first;
    int dist = *p.second - min + 1;
    vector<int> t(dist,0);

    for(auto i: array) t[i-min]++;

    for(int i = t.size()-1, idx = 0; i >= 0; --i)
        for(int j = 0; j < t[i]; ++j)
            array[idx++] = i+min;

};


int main(int argc, const char * argv[])
{
    vector<int> a;
    for(int i = 0; i < 40; ++i)
    {
        int v = rand()%20-10;
        a.push_back(v);
    }
    for(int i: a) cout << i << " "; cout << "\n";
    cout << "\n\n";

    couting_sort(a);

    for(int i: a) cout << i << " "; cout << "\n";

    couting_sort_rev(a);

    for(int i: a) cout << i << " "; cout << "\n";

}