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

Обменную поразрядную сортировку открыли П.Хильдебрандт, Г.Исбитц Х.Райзинг и Ж.Шварц, примерно за год до открытия быстрой сортировки.

Этот метод отличен от всех, рассмотренных выше. В нем используются двоичные представления ключей и сравниваются не сами ключи, а отдельные биты. Метод обладает характеристиками обменной сортировки и очень напоминает быструю сортировку.

Массив сортируется сначала по старшему значащему биту, так что вначале идут элементы, начинающиеся с 0, а затем с 1. Будем просматривать массив с двух сторон, и как только слева встретится элемент со старшим битом равным 1, а справа – со старшим битом равным 0, поменяем их местами. После чего продолжим просмотр, до тех пор пока не встретимся в каком-то месте массива.

Таким образом, мы разделили массив на две части F0 (элементы со старшим битом равным 0) и F1 (элементы со старшим битом равным 1). Теперь применим к F0 алгоритм поразрядной сортировки, начиная уже со второго бита слева, и т.д. пока полностью не отсортируем массив F0, затем то же проделаем с F1.

Рассмотрим массив из 10 чисел:

75 81 76 90 69 32 85 66 11 90

1001011 1010001 1001100 1011010 1000101 0100000 1010101 1000010 0001011 1011010

Старший значащий бит у 75 равен 1, а у 11 – 0, следовательно, поменяем их местами.

11 81 76 90 69 32 85 66 75 90

0001011 1010001 1001100 1011010 1000101 0100000 1010101 1000010 1001011 1011010

Далее меняем местами 81 и 32.

11 32 76 90 69 81 85 66 75 90

0001011 0100000 1001100 1011010 1000101 1010001 1010101 1000010 1001011 1011010

Первый проход закончен. Теперь будут сортироваться массивы:

11 32 и 76 90 69 81 85 66 75 90

Рассмотрим рекурсивный алгоритм поразрядной сортировки. Для выделения k-го бита будем использовать операции битовой арифметики Shr и and.. Например, старший бит десятибитового числа извлекаются посредством сдвига числа на 9 позиций вправо и его побитового "and" с 0000000001. Cтаршие два бита десятибитового числа извлекаются посредством сдвига числа на 8 позиций вправо и его побитового "and" с 0000000011. Далее мы будем считать, что у нас есть такая функция bits(x, b, k:integer) для извлечения k бит с позиции b из числа х.

Type

vector= array[1..n] of word;

function Bits(x,b,k: integer): integer;

begin

Bits:=(x shr b) and (2^k-1);

end;

procedure Radix (var x: vector);

procedure Sort(l,r,b: integer);

var i,j,t : integer;

begin

If (r>1) and (b>=0) then

begin

I:=l; j:=r;

Repeat

While (bits(x[i], b,1)=0) and (i<j) do i:=i+1;

While (bits(x[j], b,1)=1)and (i<j) do j:=j-1;

T:=x[i]; x[i]:=x[j];

x[j]:=t;

Until i=j;

if (bit(x[r], b, 1)=0

then j:=j+1;

Sort (l, j-1, b-1);

Sort(j, r, b-1);

End;

End;

Begin

Sort(1,n, Sizeof(x[1])*8)

End;

Поразрядная сортировка использует в среднем около N lg N битовых сравнений. Заметим, что поразрядная сортировка занимает почти столько же времени, сколько и быстрая сортировка, а ряде случаев является даже более эффективной.

Исключение рекурсии выполним как обычно, используя стек:

Procedure Radix (var x: vector);

Var i,j.l,r,b,t : integer;

S:Stack;

Begin

Push(s, l); Push(S,n);

Push(S,16);

Repeat

B:=pop(S);R:=pop(s);L:=pop(s);

repeat

I:=l; j:=r;

Repeat

While (bits(x[i],b,1)=0) and (i<j) do i:=i+1;

While (bits(x[j],b,1)=1)and (i<j) do j:=j-1;

T:=x[i];x[i]:=x[j]; x[j]:=t;

Until i=j;

if (bit(x[r],b,1)=0

then j:=j+1;

if j<r then

begin

Push(S,j); Push(s,r);

Push(s, b-1);

end;

R:=j-1;

B:=b-1;

Until (l>=r) or (b<0);

Until Empty(S);

End;

Другой метод поразрядной сортировки исследует биты справа налево. Этот метод использовался старыми машинами для сортировки карт: колода карт проходила сквозь машину 80 раз, по разу для каждой колонки, исследуя их справа налево.

Поверить в то, что этот метод на самом деле работает - нелегко. На самом же деле его легко проиллюстрировать на примере сортировки колоды карт. Предположим, что нам нужно отсортировать колоду из 52 карт в порядке:

T<2<…<K<T<2<… <T<…<K

Эту задачу можно решить двумя способами. Естественно отсортировать колоду сначала по масти, разложив на четыре стопки. А затем внутри каждой колоды отсортировать карты по достоинству. Этот способ является аналогом обменной поразрядной сортировки.

Второй способ не так очевиден, но более быстр. Он заключается в следующем: разложим карты на 13 стопок по достоинству (тузы, двойки, тройки и т.д.). Соберем стопки так, чтобы внизу были тузы, затем двойки и т.д. Перевернем колоду (тузы окажутся сверху) и разложим на четыре стопки по мастям (трефы, бубны, черви, пики). При втором раскладе в каждой стопке карты окажутся уже отсортированными по достоинству. Сложим все вместе и получим отсортированную колоду карт.

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

Для чисел поразрядную сортировку можно выполнить следующим образом: произвести сортировку по младшим цифрам (в системе счисления M), затем по следующей цифре и т.д., то есть, двигаясь справа-налево. Например, при M=10 имеем:

X 503 087 512 061 908 170 897 271

Y 170 061 271 512 503 087 897 908

X 503 908 512 061 170 271 087 897

Y 061 087 170 271 503 512 897 908

При реализации этого метода на компьютерах необходимо решить, как хранить стопки. Очевидно, для них нужно выделять память. Допустим, мы ожидаем, что должно быть M стопок, в каждой из них могут оказаться все N элементов. Поэтому необходимо выделить дополнительную память M*N элементов, что слишком расточительно. Такая потребность в памяти заставляла программистов отказываться от метода поразрядной сортировки, до тех пор пока Х.Стьюворд в своей работе не показал, что проблему можно решить, выделив дополнительно лишь N элементов памяти и M счетчиков.

Для большого числа ситуаций мы знаем, что значения ключей в файле лежат в каких либо пределах. В этих ситуациях применим алгоритм, именуемый подсчетом распределения. Впервые подсчет распределения разработал Х.Стьюворд в 1954 году и использовал его в поразрядной сортировке.

Проиллюстрируем суть метода распределения на конкретном примере. Пусть значения массива X лежат в интервале от 0 до 9. Подсчитаем, сколько раз в массиве встречается каждое значение, а затем распределим соответствующим образом память под элементы массивы с учетом их частоты.

X 4 6 3 8 4 6 4 1 0 9

Счетчик 0 1 2 3 4 5 6 7 8 9

1 1 0 1 3 0 2 0 1 1

Распределение

Памяти 1 2 2 3 6 6 8 8 9 10

Y 0 1 3 4 4 4 6 6 8 9

Ниже приведена программа для этого простого алгоритма.

Procedure Sort(var x: vector);

Const M=10;

Var

y: vector;

I, j: integer;

Count: array[0..M] of integer;

begin

for j:=0 to M-1 do count[j]:=0;

for i:=1 to N do inc(count[x[i]] );

for j:=1 to M-1 do

count[j]:=count[j-1] + count[j];

for i:=N downto 1 do

begin

y[count[x[i]]]:= x[i];

dec(count[x[i]]);

end;

x := y;

end;

Применим теперь эту идею распределения к поразрядной сортировке для двоичного основания ключей. Тогда цифры имеют только два значения, и метод подсчета распределения полностью здесь подходит. Если мы предположим М=2, то в программе подсчета распределения мы заменим x[i] на bits(x[i],b,1). На самом же деле, нет никакой необходимости в том, чтобы М было равно 2. Нам наоборот необходимо брать М=2^m настолько большое, насколько это возможно. Таким образом, прямая поразрядная сортировка становится улучшенной сортировкой подсчетом распределения для w правых бит:

procedure StrightRadix (var x: vector);

Const m=4; Mp=16; W=16;

var

i, pass : integer;

count: array [0..Mp] of integer;

y: vector;

begin

for pass := 0 to (w div m)-1 do

begin

for i:=0 to Mp-1 do count[i]:=0;

for i:=1 to N do inc(count[bits(x[i],pass*m,m)]);

for i:=1 to Mp-1 do inc(count[i],count[i-1]);

for i:=N downto 1 do

begin

y[count[bits(x[i],pass*m,m)]] := x[i];

dec(count[bits(x[i],pass*m,m)]);

end;

x := y;

end;

end;