ალგ. – ლაბ. N7 – 2;

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

template <typename iterator>
void countingSort(iterator aFirst, iterator aLast, iterator bFirst, iterator bLast)
{
    int k = *max_element(aFirst, aLast);
    k++;

    vector<int> c(k);

    for (iterator i = aFirst; i < aLast; i++)
        c[ *i ]++;
    for (int i = 1; i < k; i++)
        c[i] += c[i - 1];

    for (iterator i = aLast - 1; i >= aFirst; i--)
    {
        bFirst[ c[ *i ] - 1 ] = *i;
        c[ *i ]--;
    };
};

int main()
{
    system("COLOR F0");
    srand( time(NULL) );

    vector<int> a;
    for (int i = 0; i < 15; i++)
    {
        int num = rand()% 30 + 1;
        a.push_back(num);
    };

    vector<int> b(a.size());

    for (int i = 0; i < a.size(); i++)
        cout << " a [ " << i << " ]\t= " << a[i] << endl;
    cout << endl;

    countingSort(a.begin(), a.end(), b.begin(), b.end());

    for (int i = 0; i < b.size(); i++)
        cout << " b [ " << i << " ]\t= " << b[i] << endl;
    cout << endl;

    system("PAUSE");
    return (0);
};