StoneHaos

2

Nov 28th, 2021
755
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. using namespace std;
  6.  
  7. void bucketSort(int sarray[], const int array_size) {
  8.     const int max = array_size;
  9.     // Создание временного массива "карманов" в количестве,
  10.     // достаточном для хранения всех возможных элементов
  11.     int **bucket = new int * [10];
  12.     for (int i = 0; i < 10; i++) {
  13.         bucket[i] = new int [max+1];
  14.     }
  15.     // инициализация массива bucket
  16.     for(int x=0;x<10;x++) bucket[x][max] = 0;
  17.     // основной цикл для каждого разряда
  18.     for(int digit = 1; digit <= 1000000000; digit *= 10) {
  19.         // запись в массив bucket
  20.         for(int i = 0; i < max; i++) {
  21.             // получение цифр 0-9
  22.             int dig = (sarray[i] / digit) % 10;
  23.             // добавить число в массив bucket и увеличить счетчик
  24.             bucket[dig][bucket[dig][max]++] = sarray[i];
  25.         }
  26.         // запись карманов в массив
  27.         int idx = 0;
  28.         for(int x = 0; x < 10; x++) {
  29.             for(int y = 0; y < bucket[x][max]; y++) {
  30.                 sarray[idx++] = bucket[x][y];
  31.             }
  32.             // обнуление массива bucket
  33.             bucket[x][max] = 0;
  34.         }
  35.     }
  36.     //высвобождение памяти
  37.     for (int i = 0; i < 10; i++) {
  38.         delete [] bucket[i];
  39.     }
  40.     delete [] bucket;
  41. }
  42.  
  43. int main() {
  44.     srand(time(NULL));
  45.  
  46.     int n;
  47.     cin >> n;
  48.     int *data = new int[n];
  49.     for (int i = 0; i < n; i++) data[i] = rand() % 50;
  50.     for (int i = 0; i < n; i++) cout << data[i] << " ";
  51.     cout << endl;
  52.     bucketSort(data, n);
  53.     for (int i = 0; i < n; i++) cout << data[i] << " ";
  54.     cout << endl;
  55.     delete [] data;
  56.     return 0;
  57. }
RAW Paste Data