Цифровая сортировка(Radix Sort)

Сортировки   23 марта 2012  Автор статьи:  

Цифровая сортировка работает за k фаз, где k — число цифр в сортируемых числах. Фазы нумеруются от одного до k. На i-ой фазе производится устойчивая сортировка массива по i-ой с конца цифре. Таким образом верно: после i-ой фазы если от каждого числа оставить последние i цифр, получится корректный отсортированный массив. Каждая фаза может быть выполнена за O(n) с помощью модифицированной сортировки подсчетом. Таким образом, сортировка работает за O(k\cdot n), где k — количество цифр в максимальном числе. На практике используются не цифры десятичного представления, а байты — цифры в системе счисления с основанием 256, или даже пары байт — цифры в системе счисления с основанием 65536. Рассмотрим модифицированную устойчивую сортировку подсчетом элементов a_0,a_1,..a_{n-1} по целочисленному ключу 0\le{k(a_i)}\le{K}. Понятно, что в связи с спецификой цифровой сортировки в ответе элементы будут располагаться блоками. Нулевой блок — блок элементов с ключом, равным 0, и т.д. Любой из блоков может быть пустым. Функция {k(a_i)} возвращает k — ый байт.
Алгоритм:

  1. Подсчитываем размер блоков, создав массив c[i], содержащий количество вхождений элементов с ключом, равным i.
  2. Модифицируем массив c так, чтобы c[i] указывал на индекс элемента, первого после k-го блока. Очевидно, что c_0= количество элементов равных 0, а c_{k-1} = n . Такое преобразование массива с получается суммированием всех c_i c индексом либо меньших, либо равных данного (c_i'=c_i+c_{i-1}')
  3. Рассмотрим последний элемент a_{n-1}, так как сортировка устойчивая, он будет находится в конце блока k(a_{n-1}), а значит занимает позицию c[k(a_{n-1})]-1. Следующий с таким же ключом займет позицию c[k(a_{n-1})]-2, но чтобы формула сохранилась без изменений , нужно на каждом шаге уменьшать c[k(a_{n-1})] на единицу.
  4. Повторить шаги 1-3 для следующих разрядов.

На практике такая сортировках данных по целочисленному ключу работает намного быстрее, чем qsort.

Научиться программировать

  • на Delphi

  • на Java

  • на C++