Поразрядная цифровая сортировка.
Алгоритм требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов сортировка равно максимальному числу значащих цифр в числе - D. В каждом проходе анализируется значащая цифра в очередном разряде ключа, начиная с младшего разряда. Все ключи с одинаковым значением этой цифры объединяются в одну группу. Ключи в группе располагаются в порядке их поступления. После того, как вся исходная последовательность распределена по группам, группы располагаются в порядке возрастания связанных с группами цифр. Процесс повторяется для второй цифры и т.д., пока не будут исчерпаны значащие цифры в ключе. Основание системы счисления P может быть любым, в частном случае 2 или 10. Для системы счисления с основанием P требуется P групп.
Порядок алгоритма качественно линейный - O(N), для сортировки требуется D*N операций анализа цифры. Однако, в такой оценке порядка не учитывается ряд обстоятельств.
Во-первых, операция выделения значащей цифры будет простой и быстрой только при P=2, для других систем счисления эта операция может оказаться значительно более времяемкой, чем операция сравнения.
Во-вторых, в оценке алгоритма не учитываются расходы времени и памяти на создание и ведение групп. Размещение групп в статической рабочей памяти потребует памяти для P*N элементов, так как в предельном случае все элементы могут попасть в какую-то одну группу. Если же формировать группы внутри той же последовательности по принципу обменных алгоритмов, то возникает необходимость перераспределения последовательности между группами и все проблемы и недостатки, присущие алгоритмам включения. Наиболее рациональным является формирование групп в виде связных списков с динамическим выделением памяти.
В программном примере 3.15 мы, однако, применяем поразрядную сортировку к статической структуре данных и формируем группы на том же месте, где расположена исходная последовательность. Пример требует некоторых пояснений.
Область памяти, занимаемая массивом перераспределяется между входным и выходным множествами, как это делалось и в ряде предыдущих примеров. Выходное множество (оно размещается в начале массива) разбивается на группы. Разбиение отслеживается в массиве b. Элемент массива b[i] содержит индекс в массиве a,с которого начинается i+1-ая группа. Номер группы определяется значением анали- зируемой цифры числа, поэтому индексация в массиве b начинается с 0. Когда очередное число выбирается из входного множества и должно быть занесено в i-ую группу выходного множества, оно будет записано в позицию, определяемую значением b[i]. Но предварительно эта позиция должна быть освобождена: участок массива от b[i] до конца выходного множества включительно сдвигается вправо. После записи числа в i-ую группу i-ое и все последующие значения в массиве b корректируются - увеличиваются на 1.
{===== Программный пример 3.15 =====}
{ Цифровая сортировка (распределение) }
const D=...; { максимальное количество цифр в числе }
P=...; { основание системы счисления }
Function Digit(v, n : integer) : integer;
{ возвращает значение n-ой цифры в числе v }
begin
for n:=n downto 2 do v:=v div P;
Digit:=v mod P;
end;
Procedure Sort(var a : Seq);
Var b : array[0..P-2] of integer; { индекс элемента,
следующего за последним в i-ой группе }
i, j, k, m, x : integer;
begin
for m:=1 to D do begin { перебор цифр, начиная с младшей }
for i:=0 to P-2 do b[i]:=1; { нач. значения индексов }
for i:=1 to N do begin { перебор массива }
k:=Digit(a[i],m); { определение m-ой цифры }
x:=a[i];
{ сдвиг - освобождение места в конце k-ой группы }
for j:=i downto b[k]+1 do a[j]:=a[j-1];
{ запись в конец k-ой группы }
a[b[k]]:=x;
{ модификация k-го индекса и всех больших }
for j:=k to P-2 do b[j]:=b[j]+1;
end;
end;
Результаты трассировки программного примера 3.15 при P=10 и D=4 представлены в таблице 3.9.
Таблица 3.9
Дата добавления: 2016-07-22; просмотров: 1905;