Advertisement
awsmpshk

Untitled

Mar 14th, 2020
141
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. struct radixSortedNumber {
  7. unsigned int source_number;
  8. unsigned int sorted_number;
  9.  
  10. radixSortedNumber(int number) : source_number(number), sorted_number(number) {
  11. }
  12.  
  13. unsigned int nextDigit() {
  14. auto digit = sorted_number % 10;
  15. sorted_number /= 10;
  16. return (digit > 0 ? digit : (-1) * digit);
  17. }
  18. };
  19.  
  20. typedef vector<radixSortedNumber> Block;
  21. typedef vector<Block> Blockset;
  22.  
  23. void radix_sort(vector<unsigned int>& numbers) {
  24. Blockset current_blocks(10), next_blocks(10);
  25. size_t numbersSize = numbers.size();
  26.  
  27. for (auto source : numbers) {
  28. radixSortedNumber number(source);
  29. auto position = number.nextDigit();
  30.  
  31. current_blocks[position].push_back(number);
  32. }
  33.  
  34. do {
  35. for (auto block : current_blocks) {
  36. for (auto number : block) {
  37. auto position = number.nextDigit();
  38.  
  39. next_blocks[position].push_back(number);
  40. }
  41. }
  42.  
  43. swap(current_blocks, next_blocks);
  44.  
  45. for (auto& blockRef : next_blocks) {
  46. blockRef.clear();
  47. }
  48. } while (current_blocks[0].size() != numbersSize);
  49.  
  50. int position = 0;
  51. for (auto number : current_blocks[0]) {
  52. numbers[position++] = number.source_number;
  53. }
  54. }
  55.  
  56. int main(int argc, char* argv[]) {
  57. int count;
  58.  
  59. ifstream in("radix_input.txt");
  60. ofstream out("radix_output.txt");
  61.  
  62. in >> count;
  63.  
  64. vector<unsigned int> numbers(count);
  65.  
  66. for (int pos = 0; pos < count; ++pos) {
  67. in >> numbers[pos];
  68. }
  69.  
  70. radix_sort(numbers);
  71.  
  72. for (int pos = 0; pos < count; ++pos) {
  73. out << numbers[pos] << " ";
  74. }
  75. out << endl;
  76.  
  77. in.close();
  78. out.close();
  79.  
  80. return 0;
  81. }
Advertisement
RAW Paste Data Copied
Advertisement