Advertisement
smatskevich

PocketSort of ints by last digit

Nov 18th, 2017
303
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. // Сортировка по последней цифре.
  6. void PocketSort( std::vector<int>& arr )
  7. {
  8.     if( arr.empty() ) {
  9.         return;
  10.     }
  11.     // Количества элементов.
  12.     std::vector<int> pocketsIndexes( 10, 0 );
  13.     for( const int& value : arr ) {
  14.         ++pocketsIndexes[value % 10];
  15.     }
  16.     // Преобразовываем в индексы концов групп.
  17.     for( int i = 1; i < 10; ++i ) {
  18.         pocketsIndexes[i] += pocketsIndexes[i - 1];
  19.     }
  20.  
  21.     // Выделяем результирующий массив.
  22.     std::vector<int> result( arr.size() );
  23.     // Копируем в него все элементы arr сразу на нужное место каждый.
  24.     for( int i = arr.size() - 1; i >= 0; --i ) {
  25.         result[--pocketsIndexes[arr[i] % 10]] = arr[i];
  26.     }
  27.     arr = std::move( result );
  28. }
  29.  
  30. int main()
  31. {
  32.     int n = 0;
  33.     std::cin >> n;
  34.     std::vector<int> arr( n );
  35.     for( int i = 0; i < n; ++i ) {
  36.         std::cin >> arr[i];
  37.     }
  38.  
  39.     PocketSort( arr );
  40.  
  41.     for( const int& value : arr ) {
  42.         std::cout << value << " ";
  43.     }
  44.     return 0;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement