Реализация Поразрядной сортировки на C++

Прикладное программирование Программирование на С++ Решение задач на С++ Реализация Поразрядной сортировки на C++

Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #5793
      @admin

      Алгоритм описан по ссылке: Алгоритм поразрядной сортировки, а тут описана одна из возможных реализаций.

      Наша функция должна скрывать весь ужас реализации (Блоки, Наборы и т.п. от пользователя), использовать ее можно так:

      
      void block_sort(std::vector<unsigned int> &numbers); // прототип функции
      // ... 
      std::vector<unsigned int> numbers = {100,97,3,28,15,17,6,127};
      block_sort(numbers);
      // теперь numbers отсортирован
      

      В ходе сортировки нам нужно выделять цифры числа, начиная с конца. Можно написать для этого нехитрую функцию, выполняющую последовательность делений на 10 и взятия остатка, однако, т.к. эта операция выполняется многократно я решил завести струтуру (наверняка это «преждевременная оптимизация»):

      struct SortedNumber {
        unsigned int source;
        unsigned int sorted;
      
        SortedNumber(int number)
          : source(number), sorted(number) {
        }
      
        unsigned int nextDigit() {
          auto digit = sorted%10;
          sorted /= 10;
          return digit;
        }
      };

      Поле source хранит исходное число, а sorted — «обрубаемое» в процессе сортировки значение. Очередную цифру можно получить вызовом функции nextDigit.

      Я использовал библиотеку Qt, поэтому для вывода векторов таких чисел на экран в процессе отладки я описал соответствующий оператор:

      QDebug &operator<< (QDebug dbg, const SortedNumber& number) {
        dbg.nospace() << number.source;
        return dbg.maybeSpace();
      }

      Блоки являются контейнерами для чисел, а наборы (BlockSet) — контейнерами Блоков, опишем соответствующие типы:

      typedef std::vector<SortedNumber> Block;
      typedef std::vector<Block> BlockSet;

      Реализация функции может выглядеть следующим образом:

      void block_sort(std::vector<unsigned int> &numbers) {
        BlockSet cur_blocks(10), next_blocks(10);
        size_t nElements = numbers.size();
        
        // начальное заполнение Текущего Набора
        for (auto source : numbers) {
          SortedNumber number(source);
          auto position = number.nextDigit();
      
          cur_blocks[position].push_back(number);
        }
        //qDebug() << cur_blocks;
      
        // основная часть
        do {
          for (auto block : cur_blocks) {
            for (auto number : block) {
              auto position = number.nextDigit();
      
              next_blocks[position].push_back(number);
            }
          }
          std::swap(cur_blocks, next_blocks);
          //qDebug() << cur_blocks;
      
          for (auto& blockRef : next_blocks) {
            blockRef.clear();
          }
        } while (cur_blocks[0].size() != nElements);
      
        // конец - переписываем числа из нулевого Блока в массив
        size_t position = 0;
        for (auto number : block[0]) {
          numbers[position++] = number.source;
        }
      }

      Отличия от алгоритма приведенного по ссылке:

      • в конце числа из нулевого блока должны оказаться в исходном массиве.
      • вместо присваивания выполняется
        std::swap(cur_blocks, next_blocks);
        это эффективнее, т.к. выполнится за O(1).
Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×