Advertisement
TheMagnusRex

Count sort (сортировка подсчётом)

Jan 24th, 2017
1,303
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. #include <iostream>
  2. #include "random"
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     int n;//размер массива
  9.     int r;//радиус в котором будут браться числа для заполнения массива(0-r)
  10.     int k=0;//вспомогательная величина, чтобы заполнить массив
  11.     cin>>n;
  12.     cin>>r;
  13.     int a[n];//сортируемый массив
  14.     for (int i=0;i<n;i++){//заполняем массив случайными числами
  15.         a[i]=rand()%r;
  16.     }
  17.     for (int i =0;i<n;i++){//вывод изначального массива
  18.         cout<<a[i]<<" ";
  19.     }
  20.     cout<<endl;
  21.     //теперь нужно считать массив
  22.     int c[r];//вспомогательный массив размером r(так как числа в интервале от 0 до r)
  23.     for(int u=0;u<r;u++){
  24.         c[u]=0;//обнуляем вспомогательный массив, иначе там значения всё ломают
  25.     }
  26.     for (int i=0;i<n;i++){//считывание массива
  27.         c[a[i]]++;
  28.     }
  29.     int b[n];//отсортированный массив
  30.     for (int i=0;i<r;i++){
  31.         while(c[i]!=0){
  32.             b[k]=i;
  33.             k++;
  34.             c[i]--;
  35.         }
  36.     }
  37.     for(int w=0;w<n;w++){//вывод отсортированного массива для проверки
  38.         cout<<b[w]<<" ";
  39.     }
  40.     return 0;
  41.     }
  42. /*Замечания:
  43.  * 1-Размер массива в данной реализации задаётся пользователем, если нужно обрабатывать массив
  44.  * с неизвестными параметрами, придётся сначала искать размер этого массива
  45.  * 2-Диапазон значений в массиве также задаётся, в других случаях нужно искать минимально и максимальные значения
  46.  * в этом массиве
  47.  * 3-Даже при условии того, что диапазон задаётся, так как заполнение происходит случайно, там может не быть
  48.  * каких-то значений (скажем, он начинается не с нуля, а с пяти).*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement