Поразрядная сортировка

Материал из Википедии — свободной энциклопедии

Обменная поразрядная сортировка — алгоритм сортировки за линейное время.

[править] Алгоритм

Каждый ключ представляется в двоичном виде. Вместо того чтобы сравнивать 2 ключа, проверяются равны ли 0 или 1 отдельные разряды ключа. Очень напоминает быструю сортировку. Последовательность сортируется по старшему значемому двоичному разряду так, чтобы все ключи начинающиеся с 0 оказались перед всеми ключами начинающимися с 1. Для этого необходимо найти крайний слева ключ Ki начиющийся с 1 и крайний справа ключ Kj начиющийся с 0. После чего Ki и Kj меняются местами и процесс будет повторятся пока не получится i > j. Пусть F0 множество элементов начинающихся с 0, F1 множество всех остальных элементов. Будем к F0 применять поразрядную сортировку(начав теперь со второго бита слева, а не со старшего) до тех пор пока множество F0 полностью не рассортируется. Затем проделаем тоже самое с F1.

[править] Примеры реализации

Применение поразрядной сортировки имеет одно ограничение: перед началом сортировки необходимо знать

• length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове),
• range - количество возможных значений одного разряда (при сортировке слов - количество букв в алфавите).

Количество проходов равно числу length.

[править] C++

int bit (int a, int i)
{
   return (a >> i) & 1;
}
void radix_sort (int a[], int l, int r, int b)
{
   int i, j;
   if (r <= l || b < 0) return;
   i = l;
   j = r;
   while (i < j)
   {
      while (i < j && bit (a[i], b) == 0) ++ i;
      while (i < j && bit (a[j], b) == 1) -- j;
      swap (a[i], a[j]);
   }
   if (bit (a[r], b) == 0) ++ j;
   radix_sort (a, l, j - 1, b - 1);
   radix_sort (a, j, r, b - 1);
}

[править] Литература

• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0