2

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

void bucketSort(int sarray[], const int array_size) {
    const int max = array_size;
    // Создание временного массива "карманов" в количестве,
    // достаточном для хранения всех возможных элементов
    int **bucket = new int * [10];
    for (int i = 0; i < 10; i++) {
        bucket[i] = new int [max+1];
    }
    // инициализация массива bucket
    for(int x=0;x<10;x++) bucket[x][max] = 0;
    // основной цикл для каждого разряда
    for(int digit = 1; digit <= 1000000000; digit *= 10) {
        // запись в массив bucket
        for(int i = 0; i < max; i++) {
            // получение цифр 0-9
            int dig = (sarray[i] / digit) % 10;
            // добавить число в массив bucket и увеличить счетчик
            bucket[dig][bucket[dig][max]++] = sarray[i];
        }
        // запись карманов в массив
        int idx = 0;
        for(int x = 0; x < 10; x++) {
            for(int y = 0; y < bucket[x][max]; y++) {
                sarray[idx++] = bucket[x][y];
            }
            // обнуление массива bucket
            bucket[x][max] = 0;
        }
    }
    //высвобождение памяти
    for (int i = 0; i < 10; i++) {
        delete [] bucket[i];
    }
    delete [] bucket;
}

int main() {
    srand(time(NULL));

    int n;
    cin >> n;
    int *data = new int[n];
    for (int i = 0; i < n; i++) data[i] = rand() % 50;
    for (int i = 0; i < n; i++) cout << data[i] << " ";
    cout << endl;
    bucketSort(data, n);
    for (int i = 0; i < n; i++) cout << data[i] << " ";
    cout << endl;
    delete [] data;
    return 0;
}