Advertisement
AmidamaruZXC

Untitled

Dec 1st, 2020
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3.  
  4. void countingSort(int* numbers, int array_size)
  5. {
  6.     int max = 1;
  7.     int min = 0;
  8.     int k = max - min + 1;
  9.     int* c = new int[k];
  10.     int* b = new int[array_size];
  11.     for (int i = 0; i < k; ++i)
  12.         c[i] = 0;
  13.  
  14.     for (int i = 0; i < array_size; ++i)
  15.         c[numbers[i] - min]++;
  16.  
  17.     for (int j = 1; j < k; ++j)
  18.         c[j] = c[j] + c[j - 1];
  19.  
  20.     for (int i = array_size - 1; i >= 0; --i)
  21.     {
  22.         c[numbers[i] - min]--;
  23.         b[c[numbers[i] - min]] = numbers[i];
  24.     }
  25.     delete[] c;
  26.  
  27.     for (int i = 0; i < array_size; i++)
  28.         numbers[i] = b[i];
  29.     delete[] b;
  30. }
  31.  
  32. int main()
  33. {
  34.     int n, x;
  35.     std::string numbers;
  36.     std::cin >> n;
  37.     int* arr = new int[n];
  38.     std::cin >> numbers;
  39.     for (int i = 0; i < n; ++i)
  40.         arr[i] = numbers[i] - 48;
  41.  
  42.     countingSort(arr, n);
  43.     for (int i = 0; i < n; ++i)
  44.         std::cout << arr[i];
  45.  
  46.     delete[] arr;
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement