Алгоритм поразрядной сортировки (radix sort)

Технология и методы программирования Алгоритмы и структуры данных Алгоритм поразрядной сортировки (radix sort)

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

      Тем, кто интересовался алгоритмами, наверняка известно, что отсортировать произвольный массив быстрее чем за O(n*log(n)) невозможно. Однако, есть более хорошие алгоритмы для случаев, когда о числах кое что известно. Наиболее известный такой алгоритм — сортировка подсчетом, работающая за O(n) по времени и работающая только для целых чисел, значения которых лежат в заранее известном диапазоне. Не будем вдаваться в подробности, но этот алгоритм требует создания вспомогательного массива размера M, где M — ширина диапазона сортируемых чисел, т.е. если в сортируемом массиве могут оказаться числа из диапазона unsigned int — то вспомогательный массив будет содержать 4 миллиарда чисел. В этой связи сортировка подсчетом применяется только если исходные числа лежат в небольшом диапазоне.

      Поразрядная сортировка также работает для целых чисел, но ее также можно применить для сортировки строк небольшой длины (и других объектов, которые можно поделить на «разряды»). В наихудшем случае она отрабатывает за O(N*M), где M — максимальное количество разрядов в числе, т.е. при сортировке чисел типа unsigned int M равно 9 (столько цифр в миллиарде), а значит сортировка займет линейное время. При сортировке строк M соответствует максимальной длине строки. Для обоих случаев это чертовски быстрый алгоритм. Требует O(n) дополнительной памяти. Числа в ходе сортировки друг с другом не сравниваются.

      Описание алгоритма

      В ходе алгоритма, у каждого числа массива последовательно обрабатываются отдельные разряды справа-налево. Так, например, для числа 246 будут обработаны цифры 6, 4 и 2. Число будет перемещаться между пронумерованными Блоками в соответствии со значением своих разрядов. Далее будем полагать, что у нас уже есть функция Разряд(N, I), возвращающая I-тую цифру числа N справа, т.е. Разряд(246, 1) = 6, Разряд(246, 2) = 4, Разряд(246, 3) = 2, Разряд(246, 4) = 0. В последнем примере возвращается «ведущий ноль», т.е. от 0246.

      Перед сортировкой нам необходимо создать два Набора из 10 Блоков. Десять потому, что в десятичной системе счисления все цифры чисел лежат в диапазоне от нуля до 9. При сортировке строк, состоящих из однобайтных символов блоков должно быть 256. Первый набор назовем Текущим, а второй — Следующим.

      Псевдокод алгоритма:
      1. начальное заполнение Текущего Набора:
      1.1 для каждого Числа исходного массива выполняем:
      1.1.1 i = Разряд(Число, 1)
      1.1.2 добавить в конец i-того Блока Текущего Набора Число.
      2. основная часть:
      2.1 r = 2 (продолжаем обработку со второго разряда)
      2.2 пока все числа массива не окажутся в нулевом Блоке выполнять:
      2.2.1 Для всех Блоков Текущего Набора выполнять:
      2.2.1.1 Для всех Чисел Блока выполнять:
      2.2.1.1.1 j = Разряд(Число, r)
      2.2.1.1.2 добавить в конец j-того Блока Следующего Набора Число.
      2.2.2 ТекущийНабор = СледующийНабор
      2.2.3 очистить блоки Следующего Набора
      2.2.4 r = r+1.
      3. конец - все числа упорядочены в нулевом Блоке Текущего Набора.
      

      Почему это работает? — пусть у нас есть числа 245, 236 и 356. Если мы вручную будем их сортировать, то начнем мы со старшего разряда (356 больше всех чисел), затем сравним вторые разряды у того, что осталось. Примерно эту идею пытается реализовать поразрядная сортировка, однако, — от младших разрядов к старшим.

      Первое, что нужно понять — этот алгоритм обязательно завершится, т.к. у любого числа впереди находятся незначащие (ведущие нули) — именно поэтому в конце концов все числа окажутся в нулевом Блоке. Случится это тогда, когда значение переменной r сравняется с количеством десятичных разрядов в наибольшем числе.

      Второе — числа упорядочиваются. Происходит это потому, что добавление чисел выполняется в конец блока, а Блоки перебираются от нулевого до девятого. На каждом шаге мы добавляем чуть-чуть порядка, сортируя числа по одному из разрядов. Окончательно понять алгоритм поможет пример и визуализация.

      Более детальное описание можно найти в книгах по алгоритмам, вплоть до формального доказательства корректности. Наша же цель — почувствовать алгоритм, понять почему он работает, за счет этого мы сможем:

      • быстро оценивать — подойдет он в нашей конкретной ситуации или нет;
      • использовать идеи алгоритма в других задачах — возможно, не связанных с сортировкой.

      Пример и визуализация

      Допустим, нам надо отсортировать следующий массив: 100,97,3,28,15,17,6,127. В соответствии с первым шагом алгоритма, мы поместим числа в Блоки Начального Набора в соответствии со значением самого правого разряда (число 100 в нулевой Блок, а 127 — в седьмой):


      (тут и далее текущий разряд выделен красным цветом, перемещение чисел — стрелками).

      Теперь (второй шаг), будем просматривать не исходный массив чисел, а Текущий Набор. При этом в каждом числе выделим второй разряд, сформируем Новый Набор (который на шаге 2.2.2 станет текущим):

      Увеличим значение r до трех и повторим процесс:

      На четвертом шаге алгоритма все числа окажутся в нулевом Блоке, сортировка закончена:

      Максимальное число имело 3 разряда, поэтому на четвертом шаге (r = 4) для этих чисел функция Разряд вернула ноль и оно было добавлено в конец нулевого набора. При этом, число 100 оказалось левее 127, т.к. Блоки просматривались слева направо.

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×