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

ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА.Алгоритм требует представ-

ления ключей сортируемой последовательности в виде чисел в неко-

торой системе счисления 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.

Таблица 3.9

┌─────┬───────────────────────────────────────────────────┐

│цифра│ содержимое массивов a и b │

├─────┼───────────────────────────────────────────────────┤

│исх. │ 220 8390 9524 9510 462 2124 7970 4572 4418 1283 │

│ 1 │ 220 8390 9510 7970 462 4572 1283 9524 2124 4418 │

│ │ └────────0────────┘ └───2───┘ └─3┘ └───4───┘ └─8┘ │

│ │ b=(5,5,7,8,10,10,10,10,11,11) │

├─────┼───────────────────────────────────────────────────┤

│ 2 │ 9510 4418 220 9524 2124 462 7970 4572 1283 8390 │

│ │ └───1───┘ └──────2─────┘ └─6┘ └───7───┘ └─8┘ └─9┘ │

│ │ b=(1,3,6,6,6,6,7,9,10,11) │

├─────┼───────────────────────────────────────────────────┤

│ 3 │ 2124 220 1283 8390 4418 462 9510 9524 4572 7970 │

│ │ └─1┘ └───2───┘ └─3┘ └───4───┘ └──────5─────┘ └─9┘ │

│ │ b=(1,2,4,5,7,10,10,10,10,11) │

├─────┼───────────────────────────────────────────────────┤

│ 4 │ 220 462 1283 2124 4418 4572 7970 8390 9510 9524 │

│ │ └───0───┘ └─1┘ └─2┘ └───4───┘ └─7┘ └─8┘ └───9───┘ │

│ │ b=(3,4,5,5,7,7,7,8,9,11) │

└─────┴───────────────────────────────────────────────────┘

БЫСТРАЯ СОРТИРОВКА ХОАРА. Данный алгоритм относится к расп-

ределительным и обеспечивает показатели эффективности

O(N*log2(N)) даже при наихудшем исходном распределении.

Используются два индекса - i и j - с начальными значениями 1

и N соответственно. Ключ K[i] сравнивается с ключом K[j]. Если

ключи удовлетворяют критерию упорядоченности, то индекс j умень-

шается на 1 и производится следующее сравнение. Если ключи не

удовлетворяют критерию, то записи R[i] и R[j] меняются местами.

При этом индекс j фиксируется и начинает меняться индекс i(увели-

чиваться на 1 после каждого сравнения). После следующей переста-

новки фиксируется i и начинает изменяться j и т.д. Проход закан-

чивается, когда индексы i и j становятся равными. Запись, находя-

щаяся на позиции встречи индексов, стоит на своем месте в после-

довательности. Эта запись делит последовательность на два подмно-

жества. Все записи, расположенные слева от нее имеют ключи, мень-

шие чем ключ этой записи, все записи справа - большие. Тот же са-

мый алгоритм применяется к левому подмножеству, а затем к право-

му. Записи подмножества распределяются по двум еще меньшим подм-

ножествам и т.д., и т.д. Распределение заканчивается, когда полу-

ченное подмножество будет состоять из единственного элемента -

такое подмножество уже является упорядоченным.

Процедура сортировки в примере 3.17 рекурсивная. При ее вы-

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

до N.

Таблица 3.10

┌──────┬──────────────────────────────────────────────────┐

│проход│ содержимое массива a │

├──────┼──────────────────────────────────────────────────┤

│ │ ┌─────────────────────────────────────────────┐ │

│ 1 │ 42i 79 39 65 60 29 86 95 25 37j │

│ │ 37 79i 39 65 60 29 86 95 25 42j │

│ │ 37 42i 39 65 60 29 86 95 25j 79 │

│ │ 37 25 39i 65 60 29 86 95 42j 79 │

│ │ 37 25 39 65i 60 29 86 95 42j 79 │

│ │ 37 25 39 42i 60 29 86 95j 65 79 │

│ │ 37 25 39 42i 60 29 86j 95 65 79 │

│ │ 37 25 39 42i 60 29j 86 95 65 79 │

│ │ 37 25 39 29 60i 42j 86 95 65 79 │

│ │ ┌───────────────┐ │

│ 2 │ 29i 25 39 37j 42* 60 86 95 65 79 │

│ │ 29 25i 39 37j 42 60 86 95 65 79 │

│ │ 29 25 37i 39j 42 60 86 95 65 79 │

│ │ ┌─────┐ │

│ 3 │ 25i 29j 37* 39 42 60 86 95 65 79 │

│ │ ┌┐ │

│ 4 │ 25* 29 37* 39 42 60 86 95 65 79 │

│ │ ┌┐ │

│ 5 │ 25* 29* 37* 39 42 60 86 95 65 79 │

│ │ ┌────────────────────┐ │

│ 6 │ 25* 29* 37* 39* 42* 60i 86 95 65 79j │

│ │ 25* 29* 37* 39* 42* 60i 86 95 65i 79 │

│ │ 25* 29* 37* 39* 42* 60i 86 95j 65 79 │

│ │ 25* 29* 37* 39* 42* 60i 86j 95 65 79 │

│ │ ┌───────────────┐ │

│ 7 │ 25* 29* 37* 39* 42* 60* 79i 95 65 86j │

│ │ 25* 29* 37* 39* 42* 60* 79i 86 65j 95 │

│ │ 25* 29* 37* 39* 42* 60* 65 86i 79j 95 │

│ │ ┌┐ │

│ 8 │ 25* 29* 37* 39* 42* 60* 65 79* 86 95 │

│ │ ┌─────┐ │

│ 9 │ 25* 29* 37* 39* 42* 60* 65* 79* 86i 95j │

│ │ ┌┐ │

│ 10 │ 25* 29* 37* 39* 42* 60* 65* 79* 86* 95 │

└──────┴──────────────────────────────────────────────────┘

{===== Программный пример 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. В

каждой строке таблицы показаны текущие положения индексов i и j,

звездочками отмечены элементы, ставшие на свои места. Для каждого

прохода показаны границы подмножества, в котором ведется сорти-

ровка.

СОРТИРОВКА СЛИЯНИЕМ. Алгоритмы сортировки слиянием, как пра-

вило, имеют порядок O(N*log2(N)), но отличаются от других алго-

ритмов большей сложностью и требуют большого числа пересылок. Ал-

горитмы слияния применяются в основном, как составная часть внеш-

ней сортировки. Здесь же для понимания принципа слияния приведен

простейший алгоритм слияния в оперативной памяти.

СОРТИРОВКА ПОПАРНЫМ СЛИЯНИЕМ. Входное множество рассматрива-

ется, как последовательность подмножеств, каждое из которых сос-

тоит из единственного элемента и, следовательно, является уже

упорядоченным. На первом проходе каждые два соседних одно-эле-

ментных множества сливаются в одно двух-элементное упорядоченное

множество. На втором проходе двух-элементные множества сливаются

в 4-элементные упорядоченные множества и т.д. В конце концов по-

лучается одно большое упорядоченное множество.

Программный пример 3.18 иллюстрирует сортировку попарным

слиянием в ее обменном варианте - выходные множества формируются

на месте входных. {===== Программный пример 3.18 =====}

Procedure Sort(var a :Seq);

Var i0,j0,i,j,si,sj,k,ke,t,m : integer;

begin si:=1; { начальный размер одного множества }

while si<N do{цикл пока одно множество не составит весь массив}

begin i0:=1; { нач. индекс 1-го множества пары }

while i0<N do { цикл пока не пересмотрим весь массив }

begin j0:=i0+si; { нач. индекс 2-го множества пары }

i:=i0; j:=j0;

{размер 2-го множества пары может ограничиваться концом массива }

if si>N-j0+1 then sj:=N-j0+1 else sj:=si;

if sj>0 then

begin k:=i0; { нач. индекс слитого множества }

while (i<i0+si+sj) and (j<j0+sj) do

{ цикл пока не исчерпаются оба входные множества }

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

{ если эл-т 1-го <= элемента 2-го, он остается на своем месте, но

вых.множество расширяется иначе - освобождается место в вых.мно-

жестве и туда заносится эл-т из 2-го множества }

begin t:=a[j];

for m:=j-1 downto k do a[m+1]:=a[m];

a[k]:=t; j:=j+1; {к след. эл-ту во 2-м множестве}

end; { if a[i]>a[j] }

k:=k+1; { вых. множество увеличилось }

i:=i+1; { если был перенос - за счет сдвига, если не

было - за счет перехода эл-та в вых. }

end; { while } end; { if sj>0 }

i0:=i0+si*2; { начало следующей пары }

end; { while i0<N }

si:=si*2; { размер эл-тов пары увеличивается вдвое }

end; { while si<N }

end;

Результаты трассировки примера приведены в таблице 3.11. Для

каждого прохода показаны множества, которые на этом проходе сли-

ваются. Обратите внимание на обработку последнего множества, ос-

тавшегося без пары.

Таблица 3.11

┌─────────┬─────────────────────────────────┐

│ проход │ содержимое массива a │

├─────────┼─────────────────────────────────┤

│ 1 │ 40 5 76 86 90 25 29 96 54 15 │

│ │ └───┘ └───┘ └───┘ └───┘ └───┘ │

│ 2 │ 5 40 76 86 25 90 29 96 15 54 │

│ │ └───┘ └───┘ └───┘ └───┘ └───┘ │

│ │ └─────┘ └─────┘ │

│ 3 │ 5 40 76 86 25 29 90 96 15 54 │

│ │ └─────────┘ └─────────┘ └───┘ │

│ │ └───────────┘ │

│ 4 │ 5 25 29 40 76 86 90 96 15 54 │

│ │ └─────────────────────┘ └───┘ │

│ │ └──────────────┘ │

│результат│ 5 15 25 29 40 54 76 86 90 96 │

└─────────┴─────────────────────────────────┘