2.4.4. Многофазная сортировка
Мы обсудили необходимые приемы и приобрели достаточно опыта, чтобы иссле%
довать и запрограммировать еще один алгоритм сортировки, который по произ%
водительности превосходит сбалансированную сортировку. Мы видели, что сба%
лансированные слияния устраняют операции простого копирования, которые нужны, когда операции распределения и слияния объединены в одной фазе. Воз%
никает вопрос: можно ли еще эффективней обработать последовательности. Ока%
зывается, можно. Ключом к очередному усовершенствованию является отказ от жесткого понятия проходов, то есть более изощренная работа с последователь%
ностями, нежели использование проходов с
N
источниками и с таким же числом приемников, которые в конце каждого прохода меняются местами. При этом по%
нятие прохода размывается. Этот метод был изобретен Гильстадом [2.3] и называ%
ется многофазной сортировкой.
Проиллюстрируем ее сначала примером с тремя последовательностями. В лю%
бой момент времени элементы сливаются из двух источников в третью последо%
вательность. Как только исчерпывается одна из последовательностей%источни%
ков, она немедленно становится приемником для операций слияния данных из еще не исчерпанного источника и последовательности, которая только что была принимающей.
Так как при наличии n
серий в каждом источнике получается n
серий в прием%
нике, достаточно указать только число серий в каждой последовательности (вме%
Сортировка последовательностей
Сортировка
114
сто того чтобы указывать конкретные ключи). На рис. 2.14 предполагается, что сначала есть 13 и 8 серий в последовательностях%источниках f0
и f1
соответ%
ственно. Поэтому на первом проходе 8 серий сливается из f0
и f1
в f2
, на втором проходе остальные 5 серий сливаются из f2
и f0
в f1
и т. д. В конце концов, f0
содержит отсортированную последовательность.
Рис. 2.14. Многофазная сортировка с тремя последовательностями, содержащими 21 серию
Рис. 2.15. Многофазная сортировка слиянием 65 серий с использованием 6 последовательностей
Второй пример показывает многофазный метод с 6 последовательностями.
Пусть вначале имеются 16 серий в последовательности f0
, 15 в f1
, 14 в f2
, 12 в f3
и
8 в f4
. В первом частичном проходе 8 серий сливаются на f5
. В конце концов,
f1
содержит отсортированный набор элементов (см. рис. 2.15).
115
Многофазная сортировка более эффективна, чем сбалансированная, так как при наличии
N
последовательностей она всегда реализует
N–1
%путевое слияние вместо
N/2
%путевого. Поскольку число требуемых проходов примерно равно l
og
N n
, где n
– число сортируемых элементов, а
N
– количество сливаемых серий в одной операции слияния, то идея многофазной сортировки обещает существен%
ное улучшение по сравнению со сбалансированной.
Разумеется, в приведенных примерах на%
чальное распределение серий было тщательно подобрано. Чтобы понять, как серии должны быть распределены в начале сортировки для ее правильного функционирования, будем рассуж%
дать в обратном порядке, начиная с окончатель%
ного распределения (последняя строка на рис. 2.15). Ненулевые числа серий в каждой строке рисунка (2 и 5 таких чисел на рис. 2.14 и
2.15 соответственно) запишем в виде строки таблицы, располагая по убыванию (порядок чи%
сел в строке таблицы не важен). Для рис. 2.14 и
2.15 получатся табл. 2.13 и 2.14 соответственно.
Количество строк таблицы соответствует числу проходов.
L
a
0
(L)
a
1
(L)
Sum a i
(L)
0 1
0 1
1 1
1 2
2 2
1 3
3 3
2 5
4 5
3 8
5 8
5 13 6
13 8
21
Таблица 2.13.
Таблица 2.13.
Таблица 2.13.
Таблица 2.13.
Таблица 2.13. Идеальные распределения серий в двух последовательностях
Таблица 2.14.
Таблица 2.14.
Таблица 2.14.
Таблица 2.14.
Таблица 2.14. Идеальные распределения серий в пяти последовательностях
L
a
0
(L)
a
1
(L)
a
2
(L)
a
3
(L)
a
4
(L) Sum a i
(L)
0 1
0 0
0 0
1 1
1 1
1 1
1 5
2 2
2 2
2 1
9 3
4 4
4 3
2 17 4
8 8
7 6
4 33 5
16 15 14 12 8
65
Для табл. 2.13 получаем следующие соотношения для
L > 0
:
a
1
(L+1) = a
0
(L)
a
0
(L+1) = a
0
(L) + a
1
(L)
вместе с a
0
(0) = 1
, a
1
(0) = 0
. Определяя f
i+1
= a
0
(i)
, получаем для i > 0
:
f i+1
= f i
+ f i–1
, f
1
= 1, f
0
= 0
Это в точности рекуррентное определение чисел Фибоначчи:
f = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Сортировка последовательностей
Сортировка
116
Каждое число Фибоначчи равно сумме двух своих предшественников. Следова%
тельно, начальные числа серий в двух последовательностях%источниках должны быть двумя последовательными числами Фибоначчи, чтобы многофазная сорти%
ровка правильно работала с тремя последовательностями.
А как насчет второго примера (табл. 2.14) с шестью последовательностями?
Нетрудно вывести определяющие правила в следующем виде:
a
4
(L+1) = a
0
(L)
a
3
(L+1) = a
0
(L) + a
4
(L) = a
0
(L) + a
0
(L–1)
a
2
(L+1) = a
0
(L) + a
3
(L) = a
0
(L) + a
0
(L–1) + a
0
(L–2)
a
1
(L+1) = a
0
(L) + a
2
(L) = a
0
(L) + a
0
(L–1) + a
0
(L–2) + a
0
(L–3)
a
0
(L+1) = a
0
(L) + a
1
(L) = a
0
(L) + a
0
(L–1) + a
0
(L–2) + a
0
(L–3) + a
0
(L–4)
Подставляя f
i вместо a
0
(i)
, получаем f
i+1
= f i
+ f i–1
+ f i–2
+ f i–3
+ f i–4
для i > 4
f
4
= 1
f i
= 0 для i < 4
Это числа Фибоначчи порядка 4. В общем случае числа Фибоначчи порядка p
определяются так:
f i+1
(p) = f i
(p) + f i–1
(p) + ... + f i–p
(p) для i > p f
p
(p)
= 1
f i
(p)
= 0 для
0
≤ i < p
Заметим, что обычные числа Фибоначчи получаются для p = 1
Видим, что идеальные начальные числа серий для многофазной сортировки с
N
последовательностями суть суммы любого числа –
N–1, N–2, ... , 1
– после%
довательных чисел Фибоначчи порядка
N–2
(см. табл. 2.15).
Таблица 2.15.
Таблица 2.15.
Таблица 2.15.
Таблица 2.15.
Таблица 2.15. Числа серий, допускающие идеальное распределение
L \ N:
3 4
5 6
7 8
1 2
3 4
5 6
7 2
3 5
7 9
11 13 3
5 9
13 17 21 25 4
8 17 25 33 41 49 5
13 31 49 65 81 97 6
21 57 94 129 161 193 7
34 105 181 253 321 385 8
55 193 349 497 636 769 9
89 355 673 977 1261 1531 10 144 653 1297 1921 2501 3049 11 233 1201 2500 3777 4961 6073 12 377 2209 4819 7425 9841 12097 13 610 4063 9289 14597 19521 24097 14 987 7473 17905 28697 38721 48001
117
Казалось бы, такой
метод применим только ко входным данным, в которых число серий равно сумме
N–1
таких чисел Фибоначчи. Поэтому возникает важ%
ный вопрос: что же делать, когда число серий вначале не равно такой идеальной сумме? Ответ прост (и типичен для подобных ситуаций): будем имитировать существование воображаемых пустых серий, так чтобы сумма реальных и вообра%
жаемых серий была равна идеальной сумме. Такие серии будем называть
фиктив ными (dummy).
Но этого на самом деле недостаточно, так как немедленно встает другой, более сложный вопрос: как распознавать фиктивные серии во время слияния? Прежде чем отвечать на него, нужно исследовать возникающую еще раньше проблему распределения начальных серий и решить, каким правилом руководствоваться при распределении реальных и фиктивных серий на
N–1
лентах.
Чтобы найти хорошее правило распределения, нужно знать, как выполнять слияние реальных и фиктивных серий. Очевидно, что выбор фиктивной серии из i- й последовательности в точности означает, что i- я последовательность игно%
рируется в данном слиянии, так что речь идет о слиянии менее
N–1
источников.
Слияние фиктивных серий из всех
N–1
источников означает отсутствие реальной операции слияния, но при этом в приемник нужно записать фиктивную серию.
Отсюда мы заключаем, что фиктивные серии должны быть распределены по n–1
последовательностям как можно равномернее, так как хотелось бы иметь актив%
ные слияния с участием максимально большого числа источников.
На минуту забудем про фиктивные серии и рассмотрим проблему распределе%
ния некоторого неизвестного числа серий по
N–1
последовательностям. Ясно, что числа Фибоначчи порядка
N–2
, указывающие желательное число серий в каждом источнике, могут быть сгенерированы в процессе распределения. Например,
предположим, что
N = 6
, и, обращаясь к табл. 2.14, начнем с распределения серий,
показанного в строке с индексом
L = 1 (1, 1, 1, 1, 1)
; если еще остаются серии,
переходим ко второму ряду
(2, 2, 2, 2, 1)
; если источник все еще не исчерпан,
распределение продолжается в соответствии с третьей строкой
(4, 4, 4, 3, 2)
и т. д.
Индекс строки будем называть
уровнем. Очевидно, что чем
больше число серий,
тем выше уровень чисел Фибоначчи, который, кстати говоря, равен числу прохо%
дов слияния или переключений приемника, которые нужно будет сделать в сор%
тировке. Теперь первая версия алгоритма распределения может быть сформули%
рована следующим образом:
1. В качестве цели распределения (то есть желаемых чисел серий) взять числа
Фибоначчи порядка
N–2
, уровня 1.
2. Распределять серии, стремясь достичь цели.
3. Если цель достигнута, вычислить числа Фибоначчи следующего уровня;
разности между ними и числами на предыдущем уровне становятся новой целью распределения. Вернуться на шаг 2. Если же цель не достигнута, хотя источник исчерпан, процесс распределения завершается.
Правило вычисления чисел Фибоначчи очередного уровня содержится в их определении. Поэтому можно сосредоточить внимание на шаге 2, где при задан%
Сортировка последовательностей
Сортировка
118
ной цели еще не распределенные серии должны быть распределены по одной в
N–1
последовательностей%приемников. Именно здесь вновь появляются фик%
тивные серии.
Пусть после повышении уровня очередная цель представлена разностями d
i
,
i = 0 ... N–2
, где d
i обозначает число серий, которые должны быть распределены в i
%ю последовательность на очередном шаге. Здесь можно представить себе, что мы сразу помещаем d
i фиктивных серий в i
%ю последовательность и рассматрива%
ем последующее распределение как замену фиктивных серий реальными, при каждой замене вычитая единицу из d
i
. Тогда d
i будет равно числу фиктивных се%
рий в i- й последовательности на момент исчерпания источника.
Неизвестно, какой алгоритм дает оптималь%
ное распределение, но очень хорошо зарекомен%
довало себя так называемое горизонтальное
распределение (см. [2.7], с. 297). Это название можно понять, если представить себе, что серии сложены в стопки, как показано на рис. 2.16 для
N = 6
, уровень
5
(ср. табл. 2.14). Чтобы как мож%
но быстрее достичь равномерного распределе%
ния остаточных фиктивных серий, последние заменяются реальными послойно слева напра%
во, начиная с верхнего слоя, как показано на рис. 2.16.
Теперь можно описать соответствующий ал%
горитм в виде процедуры select
, которая вызы%
вается каждый раз, когда завершено копирова%
ние серии и выбирается новый приемник для очередной серии. Для обозначения текущей принимающей последовательности используется переменная j
a i
и d
i обозначают соответственно идеальное число серий и число фиктивных серий для i
%й последо%
вательности.
j, level: INTEGER;
a, d: ARRAY N OF INTEGER;
Эти переменные инициализируются следующими значениями:
a i
= 1,
d i
= 1
для i = 0 ... N–2
a
N–1
= 0,
d
N–1
= 0
(принимающая последовательность)
j = 0,
level = 0
Заметим, что процедура select должна вычислить следующую строчку табл. 2.14, то есть значения a
0
(L) ... a
N–2
(L)
, при увеличении уровня. Одновременно вычисляется и очередная цель, то есть разности d
i
= a i
(L) – a i
(L–1)
. Приводимый алгоритм использует тот факт, что получающиеся d
i убывают с возрастанием ин%
декса («нисходящая лестница» на рис. 2.16). Заметим, что переход с уровня 0 на уровень 1 является исключением; поэтому данный алгоритм должен стартовать
Рис. 2.16. Горизонтальное распределение серий
119
с уровня 1. Процедура select заканчивается уменьшением d
j на 1; эта операция соответствует замене фиктивной серии в j
%й последовательности на реальную.
PROCEDURE select; (* *)
VAR i, z: INTEGER;
BEGIN
IF d[j] < d[j+1] THEN
INC(j)
ELSE
IF d[j] = 0 THEN
INC(level);
z := a[0];
FOR i := 0 TO N–2 DO
d[i] := z + a[i+1] – a[i]; a[i] := z + a[i+1]
END
END;
j := 0
END;
DEC(d[j])
END select
Предполагая наличие процедуры для копирования серии из последовательно%
сти%источника src с бегунком
R
в последовательность f
j с бегунком r
j
, мы можем следующим образом сформулировать фазу начального распределения (предпола%
гается, что источник содержит хотя бы одну серию):
REPEAT select; copyrun
UNTIL R.eof
Однако здесь
следует остановиться и вспомнить о явлении, имевшем место при распределении серий в ранее обсуждавшейся сортировке естественными слияниями, а именно: две серии, последовательно попадающие в один приемник,
могут «слипнуться» в одну, так что подсчет серий даст неверный результат. Этим можно пренебречь, если алгоритм сортировки таков, что его правильность не за%
висит от числа серий. Но в многофазной сортировке необходимо тщательно от%
слеживать точное число серий в каждом файле. Следовательно, здесь нельзя пренебрегать случайным «слипанием» серий. Поэтому невозможно избежать дополнительного усложнения алгоритма распределения. Теперь необходимо удерживать ключ последнего элемента последней серии в каждой последователь%
ности. К счастью, именно это делает наша реализация процедуры
Runs
. Для при%
нимающих последовательностей поле бегунка r.first хранит последний записан%
ный элемент. Поэтому следующая попытка написать алгоритм распределения может быть такой:
REPEAT select;
IF r[j].first <= R.first THEN
END;
copyrun
UNTIL R.eof
Сортировка последовательностей
Сортировка
120
Очевидная ошибка здесь в том, что мы забыли, что r[j].first получает значение только после копирования первой серии. Поэтому корректное решение требует сначала распределить по одной серии в каждую из
N–1
принимающих последо%
вательностей без обращения к first
. Оставшиеся серии распределяются следую%
щим образом:
WHILE R.eof DO
select;
IF r[j].first <= R.first THEN
copyrun;
IF R.eof THEN INC(d[j]) ELSE copyrun END
ELSE
copyrun
END
END
Наконец, можно заняться главным алгоритмом многофазной сортировки. Его принципиальная структура подобна основной части программы
N
%путевого слия%
ния: внешний цикл, в теле которого сливаются серии, пока не исчерпаются источ%
ники, внутренний цикл, в теле которого сливается по одной серии из каждого ис%
точника, а также самый внутренний цикл, в теле которого выбирается начальный ключ и соответствующий элемент пересылается в выходной файл. Главные отли%
чия от сбалансированного слияния в следующем:
1. Теперь на каждом проходе вместо
N
приемников есть только один.
2. Вместо переключения
N
источников и
N
приемников после каждого прохо%
да происходит ротация последовательностей. Для этого используется косвенная индексация последовательностей при посредстве массива t
3. Число последовательностей%источников меняется от серии к серии; в нача%
ле каждой серии оно определяется по счетчикам фиктивных последова%
тельностей d
i
. Если d
i
> 0
для всех i
, то имитируем слияние
N–1
фиктивных последовательностей в одну простым увеличением счетчика d
N–1
для пос%
ледовательности%приемника. В противном случае сливается по одной се%
рии из всех источников с d
i
= 0
, а для всех остальных последовательностей d
i уменьшается, показывая, что число фиктивных серий в них уменьши%
лось. Число последовательностей%источников, участвующих в слиянии,
обозначим как k
4. Невозможно определить окончание фазы по обнаружению конца после%
довательности с номером
N–1
, так как могут понадобиться дальнейшие сли%
яния с участием фиктивных серий из этого источника. Вместо этого теоре%
тически необходимое число серий определяется по коэффициентам a
i
. Эти коэффициенты были вычислены в фазе распределения; теперь они могут быть восстановлены обратным вычислением.
Теперь в соответствии с этими правилами можно сформулировать основную часть многофазной сортировки, предполагая, что все
N–1
последовательности с начальными сериями подготовлены для чтения и что массив отображения ин%
дексов инициализирован как t
i
= i
121
REPEAT (* t[0] ... t[N–2] t[N–1]*)
z := a[N–2]; d[N–1] := 0;
REPEAT (* *)
k := 0;
(* *)
FOR i := 0 TO N–2 DO
IF d[i] > 0 THEN
DEC(d[i])
ELSE
ta[k] := t[i]; INC(k)
END
END;
IF k = 0 THEN
INC(d[N–1])
ELSE
t[0] ... t[k–1] t[N–1]
END;
DEC(z)
UNTIL z = 0;
Runs.Set(r[t[N–1]], f[t[N–1]]);
t;
a[i] # ;
DEC(level)
UNTIL level = 0
(* f[t[0]]*)
Реальная операция слияния почти такая же, как в сортировке
N
%путевыми слияниями, единственное отличие в том, что слегка упрощается алгоритм исклю%
чения последовательности. Ротация в отображении индексов последовательно%
стей и соответствующих счетчиков d
i
(а также перевычисление a
i при переходе на уровень вниз) не требует каких%либо ухищрений; детали можно найти в следую%
щей программе, целиком реализующей алгоритм многофазной сортировки:
PROCEDURE Polyphase (src: Files.File): Files.File;
(* ADruS24_MergeSorts *)
(* #! *)
VAR i, j, mx, tn: INTEGER;
k, dn, z, level: INTEGER;
x, min: INTEGER;
a, d: ARRAY N OF INTEGER;
t, ta: ARRAY N OF INTEGER; (* *)
R: Runs.Rider; (* *)
f: ARRAY N OF Files.File;
r: ARRAY N OF Runs.Rider;
PROCEDURE select; (* *)
VAR i, z: INTEGER;
BEGIN
IF d[j] < d[j+1] THEN
INC(j)
Сортировка последовательностей
Сортировка
122
ELSE
IF d[j] = 0 THEN
INC(level);
z := a[0];
FOR i := 0 TO N–2 DO
d[i] := z + a[i+1] – a[i]; a[i] := z + a[i+1]
END
END;
j := 0
END;
DEC(d[j])
END select;
PROCEDURE copyrun; (* src f[j]*)
BEGIN
REPEAT Runs.copy(R, r[j]) UNTIL R.eor
END copyrun;
BEGIN
Runs.Set(R, src);
FOR i := 0 TO N–2 DO
a[i] := 1; d[i] := 1;
f[i] := Files.New(""); Files.Set(r[i], f[i], 0)
END;
(* *)
level := 1; j := 0; a[N–1] := 0; d[N–1] := 0;
REPEAT
select; copyrun
UNTIL R.eof OR (j = N–2);
WHILE R.eof DO
select; (*r[j].first = , f[j]*)
IF r[j].first <= R.first THEN
copyrun;
IF R.eof THEN INC(d[j]) ELSE copyrun END
ELSE
copyrun
END
END;
FOR i := 0 TO N–2 DO
t[i] := i; Runs.Set(r[i], f[i])
END;
t[N–1] := N–1;
REPEAT (* t[0] ... t[N–2] t[N–1]*)
z := a[N–2]; d[N–1] := 0;
f[t[N–1]] := Files.New(""); Files.Set(r[t[N–1]], f[t[N–1]], 0);
REPEAT (* *)
k := 0;
FOR i := 0 TO N–2 DO
IF d[i] > 0 THEN
DEC(d[i])
123
ELSE
ta[k] := t[i]; INC(k)
END
END;
IF k = 0 THEN
INC(d[N–1])
ELSE (* t[0] ... t[k–1] t[N–1]*)
REPEAT
mx := 0; min := r[ta[0]].first; i := 1;
WHILE i < k DO
x := r[ta[i]].first;
IF x < min THEN min := x; mx := i END;
INC(i)
END;
Runs.copy(r[ta[mx]], r[t[N–1]]);
IF r[ta[mx]].eor THEN
ta[mx] := ta[k–1]; DEC(k)
END
UNTIL k = 0
END;
DEC(z)
UNTIL z = 0;
Runs.Set(r[t[N–1]], f[t[N–1]]); (* *)
tn := t[N–1]; dn := d[N–1]; z := a[N–2];
FOR i := N–1 TO 1 BY –1 DO
t[i] := t[i–1]; d[i] := d[i–1]; a[i] := a[i–1] – z
END;
t[0] := tn; d[0] := dn; a[0] := z;
DEC(level)
UNTIL level = 0 ;
RETURN f[t[0]]
END Polyphase
2.4.5. Распределение начальных серийНеобходимость использовать сложные программы последовательной сортировки возникает из%за того, что более простые методы, работающие с массивами, можно применять только при наличии достаточно большого объема оперативной памяти для хранения всего сортируемого набора данных. Часто оперативной памяти не хватает; вместо нее нужно использовать достаточно вместительные устройства
хранения данных с последовательным доступом, такие как ленты или диски. Мы знаем, что развитые выше методы сортировки последовательностей практически не нуждаются в оперативной памяти, не считая, конечно, буферов для файлов и,
разумеется, самой программы. Однако даже в небольших компьютерах размер оперативной памяти, допускающей произвольный доступ, почти всегда больше,
чем нужно для разработанных здесь программ. Не суметь ее использовать опти%
мальным образом непростительно.
Сортировка последовательностей
Сортировка
124
Решение состоит в том, чтобы скомбинировать методы сортировки массивов и последовательностей. В частности, в фазе начального распределения серий мож%
но использовать вариант сортировки массивов, чтобы серии сразу имели длину
L
,
соответствующую размеру доступной оперативной памяти. Понятно, что в после%
дующих проходах слияния нельзя повысить эффективность с помощью сорти%
ровок массивов, так как длина серий только растет, и они в дальнейшем остаются больше, чем доступная оперативная память. Так что можно спокойно ограничить%
ся усовершенствованием алгоритма, порождающего начальные серии.
Естественно, мы сразу ограничим наш выбор логарифмическими методами сортировки массивов. Самый подходящий здесь метод – турнирная сортировка,
или
HeapSort
(см. раздел 2.3.2). Используемую там пирамиду можно считать фильтром, сквозь который должны пройти все элементы – одни быстрее, другие медленнее. Наименьший ключ берется непосредственно с вершины пирамиды,
а его замещение является очень эффективной процедурой. Фильтрация элемента из последовательности%источника src
(бегунок r0
) сквозь всю пирамиду
H
в при%
нимающую последовательность (бегунок r1
) допускает следующее простое опи%
сание:
Write(r1, H[0]); Read(r0, H[0]); sift(0, n–1)
Процедура sift описана в разделе 2.3.2, с ее помощью вновь вставленный эле%
мент
H
0
просеивается вниз на свое правильное место. Заметим, что
H
0
является наименьшим элементом в пирамиде. Пример показан на рис. 2.17. В итоге про%
грамма существенно усложняется по следующим причинам:
1. Пирамида
H
вначале пуста и должна быть заполнена.
2. Ближе к концу пирамида заполнена лишь частично, и в итоге она становит%
ся пустой.
3. Нужно отслеживать начало новых серий, чтобы в правильный момент из%
менить индекс принимающей последовательности j
Прежде чем продолжить, формально объявим переменные, которые заведомо нужны в процедуре:
VAR L, R, x: INTEGER;
src, dest: Files.File;
r, w: Files.Rider;
H: ARRAY M OF INTEGER; (* *)
Константа
M
– размер пирамиды
H
. Константа mh будет использоваться для обозначения
M/2
;
L и
R
суть индексы, ограничивающие пирамиду. Тогда процесс фильтрации разбивается на пять частей:
1. Прочесть первые mh ключей из src
(
r
) и записать их в верхнюю половину пирамиды, где упорядоченность ключей не требуется.
2. Прочесть другую порцию mh ключей и записать их в нижнюю половину пи%
рамиды, просеивая каждый из них в правильную позицию (построить пира%
миду).
125 3. Установить
L
равным
M
и повторять следующий шаг для всех остальных элементов в src
: переслать элемент
H
0
в последовательность%приемник.
Если его ключ меньше или равен ключу следующего элемента в исходной последовательности, то этот следующий элемент принадлежит той же се%
рии и может быть просеян в надлежащую позицию. В противном случае нужно уменьшить размер пирамиды и поместить новый элемент во вторую,
верхнюю пирамиду, которая строится для следующей серии. Границу меж%
ду двумя пирамидами указывает индекс
L
, так что нижняя (текущая) пи%
рамида состоит из элементов
H
0
... H
L–1
, а верхняя (следующая) – из
H
L
H
M–1
. Если
L = 0
, то нужно переключить приемник и снова установить
L
рав%
ным
M
4. Когда исходная последовательность исчерпана, нужно сначала установить
R
равным
M
; затем «сбросить» нижнюю часть, чтобы закончить текущую се%
рию, и одновременно строить верхнюю часть, постепенно перемещая ее в позиции
H
L
... H
R–1 5. Последняя серия генерируется из элементов, оставшихся в пирамиде.
Теперь можно в деталях выписать все пять частей в виде полной программы,
вызывающей процедуру switch каждый раз, когда обнаружен конец серии и требу%
ется некое действие для изменения индекса выходной последовательности. Вмес%
то этого в приведенной ниже программе используется процедура%«затычка», а все серии направляются в последовательность dest
Рис. 2.17. Просеивание ключа сквозь пирамиду
Сортировка последовательностей
Сортировка
126
Если теперь попытаться объединить эту программу, например, с многофазной сортировкой, то возникает серьезная трудность: программа сортировки содержит в начальной части довольно сложную процедуру переключения между последо%
вательностями и использует процедуру copyrun
, которая пересылает в точности одну серию в выбранный приемник. С другой стороны, программа
HeapSort слож%
на и использует независимую процедуру select
, которая просто выбирает новый приемник. Проблемы не было бы, если бы в одной (или обеих) программе нужная процедура вызывалась только в одном месте; но она вызывается в нескольких ме%
стах в обеих программах.
В таких случаях – то есть при совместном существовании нескольких процес%
сов – лучше всего использовать
сопрограммы. Наиболее типичной является ком%
бинация процесса, производящего поток информации, состоящий из отдельных порций, и процесса, потребляющего этот поток. Эта связь типа производитель%
потребитель может быть выражена с помощью двух сопрограмм; одной из них мо%
жет даже быть сама главная программа. Сопрограмму можно рассматривать как процесс, который содержит одну или более точек прерывания (breakpoint). Когда встречается такая точка, управление возвращается в процедуру, вызвавшую со%
программу. Когда сопрограмма вызывается снова, выполнение продолжается с той точки, где оно было прервано. В нашем примере мы можем рассматривать много%
фазную
сортировку как основную программу, вызывающую copyrun
, которая оформлена как сопрограмма. Она состоит из главного тела приводимой ниже про%
граммы, в которой каждый вызов процедуры switch теперь должен считаться точ%
кой прерывания. Тогда проверку конца файла нужно всюду заменить проверкой того, достигла ли сопрограмма своего конца.
PROCEDURE Distribute (src: Files.File): Files.File;
(* ADruS24_MergeSorts *)
CONST M = 16; mh = M DIV 2; (* *)
VAR L, R: INTEGER;
x: INTEGER;
dest: Files.File;
r, w: Files.Rider;
H: ARRAY M OF INTEGER; (* *)
PROCEDURE sift (L, R: INTEGER); (* *)
VAR i, j, x: INTEGER;
BEGIN
i := L; j := 2*L+1; x := H[i];
IF (j < R) & (H[j] > H[j+1]) THEN INC(j) END;
WHILE (j <= R) & (x > H[j]) DO
H[i] := H[j]; i := j; j := 2*j+1;
IF (j < R) & (H[j] > H[j+1]) THEN INC(j) END
END;
H[i] := x
END sift;
BEGIN
Files.Set(r, src, 0);
127
dest := Files.New(""); Files.Set(w, dest, 0);
(*v # 1: *)
L := M;
REPEAT DEC(L); Files.ReadInt(r, H[L]) UNTIL L = mh;
(*v # 2: *)
REPEAT DEC(L); Files.ReadInt(r, H[L]); sift(L, M–1) UNTIL L = 0;
(*v # 3: *)
L := M;
Files.ReadInt(r, x);
WHILE r.eof DO
Files.WriteInt(w, H[0]);
IF H[0] <= x THEN
(*x *) H[0] := x; sift(0, L–1)
ELSE (* *)
DEC(L); H[0] := H[L]; sift(0, L–1); H[L] := x;
IF L < mh THEN sift(L, M–1) END;
IF L = 0 THEN (* ; *) L := M END
END;
Files.ReadInt(r, x)
END;
(*v # 4: *)
R := M;
REPEAT
DEC(L); Files.WriteInt(w, H[0]);
H[0] := H[L]; sift(0, L–1); DEC(R); H[L] := H[R];
IF L < mh THEN sift(L, R–1) END
UNTIL L = 0;
(*v # 5: , *)
WHILE R > 0 DO
Files.WriteInt(w, H[0]); H[0] := H[R]; DEC(R); sift(0, R)
END;
RETURN dest
END Distribute
Анализ и выводы. Какой производительности можно ожидать от многофазной сортировки, если распределение начальных серий выполняется с помощью алго%
ритма
HeapSort
? Обсудим сначала, какого улучшения можно ожидать от введе%
ния пирамиды.
В последовательности со случайно распределенными ключами средняя длина серий равна
2
. Чему равна эта длина после того, как последовательность профиль%
трована через пирамиду размера m
? Интуиция подсказывает ответ m
, но, к счас%
тью, результат вероятностного анализа гораздо лучше, а именно
2m
(см. [2.7], раз%
дел 5.4.1). Поэтому ожидается улучшение на фактор m
Производительность многофазной сортировки можно оценить из табл. 2.15,
где указано максимальное число начальных серий, которые можно отсортировать за заданное число частичных проходов (уровней) с заданным числом последова%
тельностей
N
. Например, с шестью последовательностями и пирамидой размера
Сортировка последовательностей
Сортировка
128
m = 100
файл, содержащий до 165’680’100 начальных серий, может быть отсорти%
рован за 10 частичных проходов. Это замечательная производительность.
Рассматривая комбинацию сортировок
Polyphase и
HeapSort
, нельзя не удив%
ляться сложности этой программы. Ведь она решает ту же легко формулируемую задачу перестановки элементов, которую решает и любой из простых алгоритмов сортировки массива.
Мораль всей главы можно сформулировать так:
1. Существует теснейшая связь между алгоритмом и стуктурой обрабатывае%
мых данных, и эта структура влияет на алгоритм.
2. Удается находить изощренные способы для повышения производительно%
сти программы, даже если данные приходится организовывать в структуру,
которая плохо подходит для решения задачи (последовательность вместо массива).
Упражнения
2.1.
Какие из рассмотренных алгоритмов являются устойчивыми методами сор%
тировки?
2.2.
Будет ли алгоритм для двоичных вставок работать корректно, если в опера%
торе
WHILE
условие
L < R
заменить на
L
≤
R
? Останется ли он корректным,
если оператор
L := m+1
упростить до
L := m
? Если нет, то найти набор значе%
ний a
0
... a n–1
, на котором измененная программа сработает неправильно.
2.3.
Запрограммируйте и измерьте время выполнения на вашем компьютере трех простых методов сортировки и найдите коэффициенты, на которые нужно умножать факторы
C
и
M
, чтобы получались реальные оценки времени.
2.4.
Укажите инварианты циклов для трех простых алгоритмов сортировки.
2.5.
Рассмотрите следующую «очевидную» версию процедуры
Partition и най%
дите набор значений a
0
... a n–1
, на котором эта версия не сработает:
i := 0; j := n–1; x := a[n DIV 2];
REPEAT
WHILE a[i] < x DO i := i+1 END;
WHILE x < a[j] DO j := j–1 END;
w := a[i]; a[i] := a[j]; a[j] := w
UNTIL i > j
2.6.
Напишите процедуру, которая следующим образом комбинирует алгорит%
мы
QuickSort и
BubbleSort
: сначала
QuickSort используется для получения
(неотсортированных) сегментов длины m
(
1 < m < n
); затем для заверше%
ния сортировки используется
BubbleSort
. Заметим, что
BubbleSort может проходить сразу по всему массиву из n
элементов, чем минимизируются организационные расходы. Найдите значение m
, при котором полное время сортировки минимизируется.
Замечание. Ясно, что оптимальное значение m
будет довольно мало. Поэто%
му может быть выгодно в алгоритме
BubbleSort сделать в точности m–1
про%
129
ходов по массиву без использования последнего прохода, в котором прове%
ряется, что обмены больше не нужны.
2.7.
Выполнить эксперимент из упражнения 2.6, используя сортировку простым выбором вместо
BubbleSort
. Естественно, сортировка выбором не может ра%
ботать сразу со всем массивом, поэтому здесь работа с индексами потребует больше усилий.
2.8.
Напишите
рекурсивный алгоритм быстрой сортировки так, чтобы сорти%
ровка более короткого сегмента производилась до сортировки длинного.
Первую из двух подзадач решайте с помощью итерации, для второй исполь%
зуйте рекурсивный вызов. (Поэтому ваша процедура сортировки будет со%
держать только один рекурсивный вызов вместо двух.)
2.9.
Найдите перестановку ключей
1, 2, ... , n
, для которой алгоритм
QuickSort демонстрирует наихудшее (наилучшее) поведение (
n = 5, 6, 8
).
2.10. Постройте программу естественных слияний, которая подобно процедуре простых слияний работает с массивом двойной длины с обоих концов внутрь; сравните ее производительность с процедурой в тексте.
2.11. Заметим, что в (двухпутевом) естественном слиянии, вместо того чтобы все%
гда слепо выбирать наименьший из доступных для просмотра ключей, мы поступаем по%другому: когда обнаруживается конец одной из двух серий,
хвост другой просто копируется в принимающую последовательность. На%
пример, слияние последовательностей
2, 4, 5, 1, 2, ...
3, 6, 8, 9, 7, ...
дает
2, 3, 4, 5, 6, 8, 9, 1, 2, ...
вместо последовательности
2, 3, 4, 5, 1, 2, 6, 8, 9, ...
которая кажется упорядоченной лучше. В чем причина выбора такой стра%
тегии?
2.12. Так называемое каскадное слияние (см. [2.1] и [2.7], раздел 5.4.3) – это ме%
тод сортировки, похожий на многофазную сортировку. В нем используется другая схема слияний. Например, если даны шесть последовательностей
T1
T6
, то каскадное слияние, тоже начинаясь с некоторого идеального рас%
пределения серий на
T1 ... T5
, выполняет 5%путевое слияние из
T1 ... T5
на
T6
, пока не будет исчерпана
T5
, затем (не трогая
T6
), 4%путевое слияние на
T5
, затем 3%путевое на
T4
, 2%путевое – на
T3
, и, наконец, копирование из
T1
на
T2
. Следующий проход работает аналогично, начиная с 5%путевого слия%
ния на
T1
,
и т. д. Хотя кажется, что такая схема будет хуже многофазной сортировки из%за того, что в ней некоторые последовательности иногда без%
действуют, а также из%за использования операций простого копирования,
она удивительным образом превосходит многофазную сортировку для
Упражнения
Сортировка
130
(очень) больших файлов и в случае шести и более последовательностей. На%
пишите хорошо структурированную программу на основе идеи каскадных слияний.
Литература
[2.1]
Betz B. K. and Carter. Proc. ACM National Conf. 14, (1959), Paper 14.
[2.2]
Floyd R. W. Treesort (Algorithms 113 and 243). Comm. ACM, 5, No. 8, (1962),
434, and Comm. ACM, 7, No. 12 (1964), 701.
[2.3]
Gilstad R. L. Polyphase Merge Sorting – An Advanced Technique. Proc. AFIPS
Eastern Jt. Comp. Conf., 18, (1960), 143–148.
[2.4]
Hoare C. A. R. Proof of a Program: FIND. Comm. ACM, 13, No. 1, (1970), 39–45.
[2.5]
Hoare C. A. R. Proof of a Recursive Program: Quicksort. Comp. J., 14, No. 4
(1971), 391–395.
[2.6]
Hoare C. A. R. Quicksort. Comp. J., 5. No. 1 (1962), 10–15.
[2.7]
Knuth D. E. The Art of Computer Programming. Vol. 3. Reading, Mass.: Addi%
son%Wesley, 1973 (имеется перевод: Кнут Д. Э. Искусство программирова%
ния. 2%е изд. Т. 3. – М.: Вильямс, 2000).
[2.8]
Lorin H. A Guided Bibliography to Sorting. IBM Syst. J., 10, No. 3 (1971),
244–254 (см. также Лорин Г. Сортировка и системы сортировки. – М.: На%
ука, 1983).
[2.9]
Shell D. L. A Highspeed Sorting Procedure. Comm. ACM, 2, No. 7 (1959),
30–32.
[2.10] Singleton R. C. An Efficient Algorithm for Sorting with Minimal Storage (Algo%
rithm 347). Comm. ACM, 12, No. 3 (1969), 185.
[2.11] Van Emden M. H. Increasing the Efficiency of Quicksort (Algorithm 402).
Comm. ACM, 13, No. 9 (1970), 563–566, 693.
[2.12] Williams J. W. J. Heapsort (Algorithm 232) Comm. ACM, 7, No. 6 (1964),
347–348.
Скачать 2.67 Mb.