#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";
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIGNvdXRpbmdfc29ydCh2ZWN0b3I8aW50PiYgYXJyYXkpCnsKICAgIGlmIChhcnJheS5zaXplKCkgPT0gMCkgcmV0dXJuOwogICAgYXV0byBwID0gbWlubWF4X2VsZW1lbnQoYXJyYXkuYmVnaW4oKSxhcnJheS5lbmQoKSk7CiAgICBpbnQgbWluID0gKnAuZmlyc3Q7CiAgICBpbnQgZGlzdCA9ICpwLnNlY29uZCAtIG1pbiArIDE7CiAgICB2ZWN0b3I8aW50PiB0KGRpc3QsMCk7CgogICAgZm9yKGF1dG8gaTogYXJyYXkpIHRbaS1taW5dKys7CgogICAgZm9yKGludCBpID0gMCwgaWR4ID0gMDsgaSA8IHQuc2l6ZSgpOyArK2kpCiAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IHRbaV07ICsraikKICAgICAgICAgICAgYXJyYXlbaWR4KytdID0gaSttaW47Cgp9OwoKdm9pZCBjb3V0aW5nX3NvcnRfcmV2KHZlY3RvcjxpbnQ+JiBhcnJheSkKewogICAgaWYgKGFycmF5LnNpemUoKSA9PSAwKSByZXR1cm47CiAgICBhdXRvIHAgPSBtaW5tYXhfZWxlbWVudChhcnJheS5iZWdpbigpLGFycmF5LmVuZCgpKTsKICAgIGludCBtaW4gPSAqcC5maXJzdDsKICAgIGludCBkaXN0ID0gKnAuc2Vjb25kIC0gbWluICsgMTsKICAgIHZlY3RvcjxpbnQ+IHQoZGlzdCwwKTsKCiAgICBmb3IoYXV0byBpOiBhcnJheSkgdFtpLW1pbl0rKzsKCiAgICBmb3IoaW50IGkgPSB0LnNpemUoKS0xLCBpZHggPSAwOyBpID49IDA7IC0taSkKICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgdFtpXTsgKytqKQogICAgICAgICAgICBhcnJheVtpZHgrK10gPSBpK21pbjsKCn07CgoKaW50IG1haW4oaW50IGFyZ2MsIGNvbnN0IGNoYXIgKiBhcmd2W10pCnsKICAgIHZlY3RvcjxpbnQ+IGE7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgNDA7ICsraSkKICAgIHsKICAgICAgICBpbnQgdiA9IHJhbmQoKSUyMC0xMDsKICAgICAgICBhLnB1c2hfYmFjayh2KTsKICAgIH0KICAgIGZvcihpbnQgaTogYSkgY291dCA8PCBpIDw8ICIgIjsgY291dCA8PCAiXG4iOwogICAgY291dCA8PCAiXG5cbiI7CgogICAgY291dGluZ19zb3J0KGEpOwoKICAgIGZvcihpbnQgaTogYSkgY291dCA8PCBpIDw8ICIgIjsgY291dCA8PCAiXG4iOwoKICAgIGNvdXRpbmdfc29ydF9yZXYoYSk7CgogICAgZm9yKGludCBpOiBhKSBjb3V0IDw8IGkgPDwgIiAiOyBjb3V0IDw8ICJcbiI7Cgp9Cgo=