CountingSortByModule

#include <algorithm>
#include <assert.h>
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::vector;

void CountingSort( vector<int>& arr, int module )
{
    assert( module >= 1 );
    vector<int> c( module, 0 );
    // Заполняем массив количеств.
    for( int& x: arr ) {
        ++c[x % module];
    }
    // Преобразуем его в массив позиций групп.
    int summ = 0;
    for( int i = 1; i < module; ++i ) {
        int temp = c[i];
        c[i] = summ;
        summ += temp;
    }

    // Выводим.
    vector<int> result( arr.size(), 0xCECECECE );
    for( int& x: arr ) {
        // Получаем индекс группы, текущую позицию в группе, записываем в эту позицию.
        // Инкрементируем текущую позицию в группе.
        result[c[x % module]++] = x;
    }

    std::swap( arr, result );
}

int main()
{
    int n = 0;
    cin >> n;
    vector<int> arr( n );
    for( int i = 0; i < n; ++i ) {
        cin >> arr[i];
    }

    CountingSort( arr, 4 );

    for( int i = 0; i < n; ++i ) {
        cout << arr[i] << " ";
    }
    return 0;
}