ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА.Алгоритм требует представ-
ления ключей сортируемой последовательности в виде чисел в неко-
торой системе счисления 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 │
└─────────┴─────────────────────────────────┘