Сортировки распределением

ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА. Алгоритм требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов сортировка равно максимальному числу значащих цифр в числе - D. В каждом проходе анализируется значащая цифра в очередном разряде ключа, начиная с младшего разряда. Все ключи с одинаковым значением этой цифры объединяются в одну группу. Ключи в группе располагаются в порядке их поступления. После того, как вся исходная последовательность распределена по группам, группы располагаются в порядке возрастания связанных с группами цифр. Процесс повторяется для второй цифры и т.д., пока не будут исчерпаны значащие цифры в ключе. Основание системы счисления P может быть любым, в частном случае 2 или 10. Для системы счисления с основанием P требуется P групп.

Порядок алгоритма качественно линейный - O(N), для сортировки требуется D*N операций анализа цифры. Однако, в такой оценке порядка не учитывается ряд обстоятельств.

Во-первых, операция выделения значащей цифры будет простой и быстрой только при P=2, для других систем счисления эта операция может оказаться значительно более времяемкой, чем операция сравнения.

Во-вторых, в оценке алгоритма не учитываются расходы времени и памяти на создание и ведение групп. Размещение групп в статической рабочей памяти потребует памяти для P*N элементов, так как в предельном случае все элементы могут попасть в какую-то одну группу. Если же формировать группы внутри той же последовательности по принципу обменных алгоритмов, то возникает необходимость перераспределения последовательности между группами и все проблемы и недостатки, присущие алгоритмам включения. Наиболее рациональным является формирование групп в виде связных списков с динамическим выделением памяти.

В программном примере 3.16 применена поразрядная сортировка к статической структуре данных и формируются группы на том же месте, где расположена исходная последовательность. Пример требует некоторых пояснений.

Область памяти, занимаемая массивом, перераспределяется между входным и выходным множествами, как это делалось и в ряде предыдущих примеров. Выходное множество (оно размещается в начале массива) разбивается на группы. Разбиение отслеживается в массиве b.

Элемент массива b[i] содержит индекс в массиве a, с которого начинается i+1-ая группа. Номер группы определяется значением анализируемой цифры числа, поэтому индексация в массиве b начинается с 0. Когда очередное число выбирается из входного множества и должно быть занесено в i-ую группу выходного множества, оно будет записано в позицию, определяемую значением b[i]. Но предварительно эта позиция должна быть освобождена: участок массива от b[i] до конца выходного множества включительно сдвигается вправо. После записи числа в i-ую группу i-ое и все последующие значения в массиве b корректируются - увеличиваются на 1.

{===== Программный пример 3.16 =====}

{ Цифровая сортировка (распределение) }

const D=...; { максимальное количество цифр в числе }

P=...; { основание системы счисления }

Function Digit(v, n: integer): integer;

begin { возвращает значение n-ой цифры в числе v }

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];

a[b[k]]:=x; { запись в конец k-ой группы}

{ модификация k-го индекса и всех больших }

for j:=k to P-2 do b[j]:=b[j]+1;

end;

end; end;

Результаты трассировки программного примера 3.16 при P=10 и D=4 представлены в таблице 3.9.

БЫСТРАЯ СОРТИРОВКА ХОАРА. Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log2(N)) даже при наихудшем исходном распределении.

Используются два индекса - i и j - с начальными значениями 1 и N соответственно. Ключ K[i] сравнивается с ключом K[j]. Если ключи удовлетворяют критерию упорядоченности, то индекс j уменьшается на 1 и производится следующее сравнение. Если ключи не удовлетворяют критерию, то записи R[i] и R[j] меняются местами.

Таблица 3.9

Цифра	содержимое массивов а и b
исх.	220 8390 9524 9510 462 2124 7970 4572 4418 12383
	220 8390 9510 7970 462 4572 1283 9524 2124 4418 b=(5,5,7,8,10,10,10,10,11,11)
	9510 4418 220 9524 2124 462 7970 4572 1283 8390 b=(1,3,6,6,6,6,7,9,10,11)
	2124 220 1283 8390 4418 462 9510 9524 4572 7970 b=(1,2,4,5,7,10,10,10,10,11)
	220 462 1283 2124 4418 4572 7970 8390 9510 9524 b=(3,4,5,5,7,7,7,8,9,11)

При этом индекс j фиксируется и начинает меняться индекс i (увеличиваться на 1 после каждого сравнения). После следующей перестановки фиксируется i и начинает изменяться j и т.д. Проход заканчивается, когда индексы i и j становятся равными. Запись, находящаяся на позиции встречи индексов, стоит на своем месте в последовательности. Эта запись делит последовательность на два подмножества. Все записи, расположенные слева от нее имеют ключи, меньшие чем ключ этой записи, все записи справа - большие. Тот же самый алгоритм применяется к левому подмножеству, а затем к правому. Записи подмножества распределяются по двум еще меньшим подмножествам и т.д., и т.д. Распределение заканчивается, когда полученное подмножество будет состоять из единственного элемента - такое подмножество уже является упорядоченным.

Процедура сортировки в примере 3.17 рекурсивная. При ее вызове должны быть заданы значения границ сортируемого участка от 1 до N

{===== Программный пример 3.17 =====}

{Быстрая сортировка Хоара; i0, j0 - границы сортируемого участка}

Procedure Sort(var a: Seq; i0,j0: integer);

Var i, j: integer; { текущие индексы в массиве }

flag: boolean; { признак меняющегося индекса: если

flag=true - уменьшается j, иначе - увеличивается i }

x: integer;

begin if j0<=i0 Exit; { подмножество пустое или из 1 эл-та }

i:=i0; j:=j0; flag:=true; { вначале будет изменяться j }

while i<j do

begin if a[i]>a[j] then

begin x:=a[i]; a[i]:=a[j]; a[j]:=x; { перестановка }

flag:= not flag; { после перестановки меняется индекс }

end; { реально изменяется только один индекс }

if flag then j:=j-1 else i:=i+1;

end;

Sort(a,i0,i-1); { сортировка левого подмассива }

Sort(a,i+1,j0); { сортировка правого подмассива }

end;

Таблица 3.10

Результаты трассировки примера приведены в таблице 3.10. В каждой строке таблицы показаны текущие положения индексов i и j, звездочками отмечены элементы, ставшие на свои места. Для каждого прохода показаны границы подмножества, в котором ведется сортировка.

СОРТИРОВКА СЛИЯНИЕМ. Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внешней сортировки. Здесь же для понимания принципа слияния приведен простейший алгоритм слияния в оперативной памяти.