Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

Сортировка
76
2.2.2. Простая сортировка выбором
Данный метод основан на следующей схеме:
1. Выберем элемент с наименьшим ключом.
2. Переставим его с первым элементом a
0 3. Повторим эти операции с остальными n–1
элементами, затем с n–2
элемен%
тами.., пока не останется только один – наибольший – элемент.
Проиллюстрируем метод на той же последовательности из восьми ключей, что и в табл. 2.1:
Таблица 2.2.
Таблица 2.2.
Таблица 2.2.
Таблица 2.2.
Таблица 2.2. Пример простой сортировки выбором
Начальные ключи:
44 55 12 42 94 18 06 06 06 06 06 67
i=1 06 55 12 12 12 12 12 42 94 18 44 67
i=2 06 12 55 42 94 18 18 18 18 18 44 67
i=3 06 12 18 42 42 42 42 42 94 55 44 67
i=4 06 12 18 42 94 55 44 44 44 44 44 67
i=5 06 12 18 42 44 55 55 55 55 55 94 67
i=6 06 12 18 42 44 55 94 67 67 67 67 67
i=7 06 12 18 42 44 55 67 94
Алгоритм формулируется следующим образом:
FOR i := 0 TO n–1 DO
присвоить k
индекс наименьшего элемента из a
i
... a n–1
;
переставить
a i
и a
k
END
Этот метод можно назвать простой сортировкой выбором. В некотором смысле он противоположен простой сортировке вставками: в последней на каждом шаге,
чтобы найти позицию вставки, рассматривается один очередной элемент массива%
источника и все элементы массива%приемника; в простой сортировке выбором просматривается весь массив%источник, чтобы найти один элемент с наименьшим ключом, который должен быть вставлен в массив%приемник.
PROCEDURE StraightSelection;
(* ADruS2_Sorts *)
VAR i, j, k: INTEGER; x: Item;
BEGIN
FOR i := 0 TO n–2 DO
k := i; x := a[i];
FOR j := i+1 TO n–1 DO
IF a[j] < x THEN k := j; x := a[k] END
END;
a[k] := a[i]; a[i] := x
END
END StraightSelection

77
Анализ простой сортировки выбором. Очевидно, число
C
сравнений ключей не зависит от начального порядка ключей. В этом смысле можно сказать, что этот метод ведет себя не так естественно, как метод простых вставок. Получаем:
C = (n
2
– n)/2
Число
M
пересылок не меньше, чем
M
min
= 3*(n – 1)
для изначально упорядоченных ключей, и не больше, чем
M
max
= n
2
/4 + 3*(n – 1),
если изначально ключи стояли в обратном порядке. Чтобы определить
M
avg
, бу%
дем рассуждать так: алгоритм просматривает массив, сравнивая каждый элемент с наименьшим значением, найденным до сих пор, и если элемент оказывается меньше, чем этот минимум, выполняется присваивание. Вероятность, что второй элемент меньше, чем первый, равна 1/2; такова же и вероятность присваивания минимуму нового значения. Вероятность того, что третий элемент окажется мень%
ше, чем первые два, равна 1/3, а вероятность того, что четвертый окажется наи%
меньшим, равна 1/4, и т. д. Поэтому полное среднее число пересылок равно
H
n–1
,
где
H
n
– n
%ое гармоническое число
H
n
= 1 + 1/2 + 1/3 + ... + 1/n
H
n можно представить как
H
n
= ln(n) + g + 1/2n – 1/12n
2
+ ...
где g = 0.577216...
– константа Эйлера. Для достаточно больших n
можно отбро%
сить дробные члены и получить приближенное среднее число присваиваний на i
%м проходе в виде
F
i
= ln(i) + g + 1
Тогда среднее число пересылок
M
avg в сортировке выбором равно сумме величин
F
i с i
, пробегающим от
1
до n
:
M
avg
= n*(g+1) + (S
S
S
S
Si: 1
≤ i ≤ n: ln(i))
Аппроксимируя дискретную сумму интегралом
Integral (1:n) ln(x) dx = n * ln(n) – n + 1
получаем приближенное выражение
M
avg
= n * (ln(n) + g)
Можно заключить, что в общем случае простая сортировка выбором предпоч%
тительней простой сортировки вставками, хотя если ключи изначально упорядо%
чены или почти упорядочены, простые вставки работают немного быстрее.
Сортировка массивов

Сортировка
78
2.2.3. Простая сортировка обменами
(пузырьковая)
Классификация методов сортировки не вполне однозначна. Оба обсуждавшихся выше метода можно также рассматривать как сортировки обменами. Однако сей%
час мы представим метод, в котором обмен двух элементов играет главную роль.
Получающаяся простая сортировка обменами использует сравнение и обмен пар соседних элементов до тех пор, пока не будут отсортированы все элементы.
Как и ранее в простой сортировке выбором, здесь выполняются повторные про%
ходы по массиву, причем каждый раз наименьший элемент оставшегося множества просеивается в направлении левого конца массива. Если для разнообразия считать массив расположенным вертикально, а не горизонтально, и вообразить, что элемен%
ты – это пузырьки в сосуде с водой, причем их вес равен значению ключа, тогда проходы по массиву приводят к подъему пузырька на уровень, соответствующий его весу (см. табл. 2.3). Такой метод широко известен как пузырьковая сортировка.
Таблица 2.3.
Таблица 2.3.
Таблица 2.3.
Таблица 2.3.
Таблица 2.3. Пример работы пузырьковой сортировки i = 0 1
2 3
4 5
6 7
44 06 06 06 06 06 06 06 55 44 12 12 12 12 12 12 12 55 44 18 18 18 18 18 42 12 12 12 12 12 55 44 42 42 42 42 94 42 18 18 18 18 18 55 44 44 44 44 18 94 42 42 42 42 42 42 55 55 55 55 06 06 06 06 06 18 18 18 18 18 94 67 67 67 67 67 67 67 67 67 67 67 67 94 94 94 94 94
PROCEDURE BubbleSort;
(* ADruS2_Sorts *)
VAR i, j: INTEGER; x: Item;
BEGIN
FOR i := 1 TO n–1 DO
FOR j := n–1 TO i BY –1 DO
IF a[j–1] > a[j] THEN
x := a[j–1]; a[j–1] := a[j]; a[j] := x
END
END
END
END BubbleSort
Этот алгоритм нетрудно улучшить. Пример в табл. 2.3 показывает, что после%
дние три прохода не влияют на порядок элементов, так как они уже отсортирова%
ны. Очевидный способ улучшить алгоритм – запомнить, имел ли место хотя бы один обмен во время прохода. Тогда проход без обменов сигнализирует, что алго%

79
ритм может быть остановлен. Однако можно сделать еще одно улучшение, запо%
миная не только факт обмена, но и позицию (индекс) последнего обмена. Ясно,
например, что все пары соседних элементов левее этого значения индекса (назо%
вем его k
) уже упорядочены. Поэтому последующие проходы могут останавли%
ваться на этом значении индекса, вместо того чтобы продолжаться до i
. Однако внимательный программист заметит любопытную асимметрию: если вначале только один пузырек стоит не на своем месте в «тяжелом» конце, то он доберется до своего места за один проход, а если такой пузырек стоит в «легком» конце, то он будет опускаться в свою правильную позицию только на один шаг за каждый про%
ход. Например, массив
12 18 42 44 55 67 94 06
сортируется улучшенной пузырьковой сортировкой за один проход, а массив
94 06 12 18 42 44 55 67
требует семи проходов. Такая неестественная асимметрия наводит на мысль о третьем усовершенствовании: менять направление последовательных проходов.
Получающийся алгоритм называют шейкерсортировкой (shaker sort). Его работа показана в табл. 2.4, где он применяется к той же последовательности из восьми ключей, что и в табл. 2.3.
PROCEDURE ShakerSort;
(* ADruS2_Sorts *)
VAR j, k, L, R: INTEGER; x: Item;
BEGIN
L := 1; R := n–1; k := R;
REPEAT
FOR j := R TO L BY –1 DO
IF a[j–1] > a[j] THEN
x := a[j–1]; a[j–1] := a[j]; a[j] := x; k := j
END
END;
L := k+1;
FOR j := L TO R BY +1 DO
IF a[j–1] > a[j] THEN
x := a[j–1]; a[j–1] := a[j]; a[j] := x; k := j
END
END;
R := k–1
UNTIL L > R
END ShakerSort

Сортировка
80
M
min
= 0,
M
avg
= 3*(n
2
– n)/2,
M
max
= 3*(n
2
– n)/4.
Анализ улучшенных вариантов, особенно шейкер%сортировки, довольно сло%
жен. Наименьшее число сравнений здесь равно
C
min
= n–1
. Для улучшенной пу%
зырьковой сортировки Кнут (см. [2.7] – прим. перев.) нашел, что среднее число проходов пропорционально величине n – k
1
*n
1/2
, а среднее число сравнений – ве%
личине
(n
2
–
n*(k
2
+
ln(n)))/2
. Но нужно отметить, что ни одно из упомянутых улучшений не может повлиять на число обменов; уменьшается только число из%
быточных проверок. К несчастью, обмен двух элементов – обычно более затрат%
ная операция, чем сравнение ключей; поэтому все наши хитроумные улучшения имеют гораздо меньший эффект, чем интуитивно ожидается.
Этот анализ показывает, что сортировка обменами и ее небольшие улучшения хуже, чем и сортировка вставками и сортировка выбором; на самом деле пузырь%
ковая сортировка вряд ли чем%нибудь интересна, кроме своего запоминающегося названия. Шейкер%сортировка выгодна в тех случаях, когда элементы уже стоят в почти правильном порядке, – но это редко случается на практике.
Можно показать, что среднее расстояние, которое должен пройти каждый из n
элементов за время сортировки, равно n/3
позиций. Это число указывает, в ка%
ком направлении нужно искать более эффективные методы сортировки. В сущно%
сти, все простые методы перемещают элемент на одну позицию на каждом эле%
ментарном шаге. Поэтому они всегда требуют порядка n
2
таких шагов. Любое серьезное усовершенствование должно иметь целью увеличение расстояния, на которое перемещаются элементы в каждом прыжке.
В дальнейшем будут обсуждаться три эффективных метода, по одному на каж%
дый из простых методов сортировки: вставками, выбором и обменами.
Таблица 2.4.
Таблица 2.4.
Таблица 2.4.
Таблица 2.4.
Таблица 2.4. Пример работы шейкер:сортировки
L =
2 3
3 4
4
R =
8 8
7 7
4
dir =
↑
↓
↑
↓
↑
44 06 06 06 06 55 44 44 12 12 12 55 55 55 55 55 12 12 12 12 12 44 44 44 44 44 18 42 12 42 18 42 94 42 55 42 44 18 94 94 94 94 94 18 18 18 18 18 55 55 06 06 06 06 06 18 67 67 67 67 67 94 94 94

81
2.3. Эффективные методы сортировки
2.3.1. Сортировка вставками
с уменьшающимися расстояниями
В 1959 г. Шелл [2.9] предложил способ ускорить сортировку простыми вставками.
Проиллюстрируем метод Шелла с помощью нашего стандартного примера с восе%
мью элементами (см. табл. 2.5). Сначала каждая группа элементов, отстоящих друг от друга на четыре позиции, сортируется отдельно. Этот процесс называется 4%сор%
тировкой. В нашем примере с восемью элементами каждая такая группа состоит в точности из двух элементов. После первого прохода снова рассматриваются груп%
пы элементов, но уже отстоящих на две позиции, и снова группы сортируются по отдельности. Этот процесс называется 2%сортировкой. Наконец, на третьем проходе все элементы сортируются обычной сортировкой, или 1%сортировкой.
Таблица 2.5.
Таблица 2.5.
Таблица 2.5.
Таблица 2.5.
Таблица 2.5. Сортировка вставками с уменьшающимися расстояниями
44 55 12 42 94 18 06 67
После 4%сортировки
44 18 06 42 94 55 12 67
После 2%сортировки
06 18 12 42 44 55 94 67
После 1%сортировки
06 12 18 42 44 55 67 94
Встает резонный вопрос: не превысят ли возможную экономию затраты на вы%
полнение нескольких проходов, в каждом из которых сортируются все элементы?
Однако каждая сортировка одной группы элементов либо имеет дело с относи%
тельно небольшим их числом, либо элементы уже частично отсортированы, так что нужно сделать сравнительно немного перестановок.
Очевидно, что метод приводит к отсортированному массиву, и нетрудно по%
нять, что на каждом шаге нужно выполнить меньше работы благодаря предыду%
щим (так как каждая i
%сортировка комбинирует две группы, отсортированные предыдущей
2i
%сортировкой). Очевидно также, что допустима любая последова%
тельность расстояний, лишь бы последнее из них было равно единице, так как в худшем случае вся работа будет выполняться на последнем проходе. Гораздо менее очевидно, что метод работает еще лучше, если уменьшающиеся расстояния выбирать отличными от степеней двойки.
Поэтому построим процедуру для произвольной последовательности рассто%
яний. Всего будет
T
расстояний h
0
, h
1
,
, h
T–1
, удовлетворяющих условиям h
T–1
= 1, h i+1
< h i
Эффективные методы сортировки

Сортировка
82
Алгоритм описан в процедуре
ShellSort
[2.9] для
T = 4
:
PROCEDURE ShellSort;
(* ADruS2_Sorts *)
CONST T = 4;
VAR i, j, k, m, s: INTEGER;
x: Item;
h: ARRAY T OF INTEGER;
BEGIN
h[0] := 9; h[1] := 5; h[2] := 3; h[3] := 1;
FOR m := 0 TO T–1 DO
k := h[m];
FOR i := k TO n–1 DO
x := a[i]; j := i–k;
WHILE (j >= k) & (x < a[j]) DO
a[j+k] := a[j]; j := j–k
END;
IF (j >= k) OR (x >= a[j]) THEN
a[j+k] := x
ELSE
a[j+k] := a[j];
a[j] := x
END
END
END
END ShellSort
Анализ сортировки Шелла. Анализ этого алгоритма – очень сложная матема%
тическая проблема, полностью еще не решенная. В частности, неизвестно, какая последовательность расстояний дает наилучший результат. Но удивительно то,
что расстояния не должны быть кратными друг другу. Тогда исчезнет явление,
наблюдаемое в приведенном примере, когда каждый проход сортировки объеди%
няет две цепочки, до того никак не «общавшиеся». На самом деле желательно,
чтобы различные цепочки «общались» как можно чаще, причем выполняется следующая теорема: если последовательность после k
%сортировки подвергается i
%сортировке, то она остается k
%отсортированной. Кнут в [2.7] (см. с. 105–115 пе%
ревода) приводит аргументы в пользу того, что неплохим выбором расстояний яв%
ляется последовательность (записанная здесь в обратном порядке)
1, 4, 13, 40, 121, ...
где h
k–1
= 3h k
+1
, h
T
= 1
, и
T = k
×
⎣
log
3
(n)
⎦
– 1
. Он также рекомендует последова%
тельность
1, 3, 7, 15, 31, ...
где h
k–1
= 2h k
+1,
h
T
= 1
, и
T = k
×
⎣
log
2
(n)
⎦
– 1
. В последнем случае математическое исследование показывает, что при сортировке n
элементов алгоритмом Шелла затраты пропорциональны n
1.2
. Хотя это гораздо лучше, чем n
2
, мы не будем уг%
лубляться в этот метод, так как есть алгоритмы еще лучше.

83
2.3.2. Турнирная сортировка
Простая сортировка выбором основана на повторном выборе наименьшего ключа среди n
элементов, затем среди оставшихся n–1
элементов и т. д. Очевидно, для нахождения наименьшего ключа среди n
элементов нужно n–1
сравнений, среди n–1
элементов – n–2
сравнений и т. д., а сумма первых n–1
целых равна
(n
2
–n)/2
Как же можно улучшить такую сортировку? Только если после каждого просмот%
ра сохранять больше информации, чем всего лишь информацию об одном наименьшем элементе. Например, n/2
сравнений позволяют определить меньший ключ в каждой паре элементов, еще n/4
сравнений дадут меньший ключ в каждой паре из уже найденных меньших ключей, и т. д. Имея только n–1
сравнений, мы можем построить дерево выбора, показанное на рис. 2.3, причем в корне будет ис%
комый наименьший ключ [2.2].
Рис. 2.3. Повторные выборы среди двух ключей («турнир ключей»)
Второй шаг состоит в спуске по пути, соответствующему наименьшему ключу,
и в его удалении последовательной заменой либо на пустую позицию («дырку»)
в самом низу, либо на элемент из другой ветки в промежуточных узлах (см.
рис. 2.4 и 2.5). Теперь элементом в корне дерева будет второй наименьший ключ, и его можно удалить. После n
таких шагов выбора дерево станет пустым (то есть будет заполнено дырками), и процесс сортировки прекращается. Следует заметить,
что на каждом из n
шагов выбора требуется только log(n)
сравнений. Поэтому вся процедура требует лишь порядка n*log(n)
элементарных операций в дополнение к тем n
шагам, которые нужны для построения дерева. Это очень существенное
Рис. 2.4. Выбор наименьшего ключа
Эффективные методы сортировки

Сортировка
84
улучшение по сравнению с простыми методами, требующими n
2
шагов, и даже по сравнению с сортировкой Шелла, требующей n
1.2
шагов. Естественно, организовать работу такого алгоритма труднее, поэтому сложность отдельных шагов в турнир%
ной сортировке выше: чтобы сохранить всю информацию с предыдущих шагов,
нужно работать с некоторой древесной структурой. Нашей следующей задачей будет найти способ эффективно организовать всю эту информацию.
Прежде всего важно избавиться от необходимости иметь дело с дырками, кото%
рые в итоге заполнят все дерево и потребуют много лишних сравнений. Затем нужно найти способ представить дерево из n
элементов в n
единицах памяти вме%
сто
2n – 1
, как это имеет место на приведенных рисунках. Обе цели были достиг%
нуты в алгоритме Heapsort, названном так его изобретателем Вильямсом [2.12];
этот алгоритм представляет собой радикальное улучшение по сравнению с более традиционными подходами к турнирной сортировке. Пирамида (heap) определя%
ется как последовательность ключей h
L
, h
L+1
, ... , h
R
(L
≥
0)
, такая, что h
i
< h
2i+1
и h
i
< h
2i+2
для i = L ... R/2–1
Если представить двоичное дерево массивом так, как показано на рис. 2.6, то деревья сортировки на рис. 2.7 и 2.8 тоже суть пирамиды, в частности элемент h
0
пирамиды является ее наименьшим элементом:
h
0
= min(h
0
, h
1
, ... , h n–1
)
Пусть дана пирамида с элементами h
L+1
... h
R
с некоторыми
L
и
R
, и пусть нужно добавить новый элемент x
так, чтобы получилась расширенная пирамида h
L
... h
R
. Например, возьмем начальную пирамиду h
1
... h
7
, показанную на
Рис. 2.5. Заполнение дырок
Рис. 2.6. Массив, представленный в виде двоичного дерева

85
рис. 2.7, и расширим пирамиду влево элементом h
0
= 44
. Новая пирамида получа%
ется так: сначала x
ставится на вершину древесной структуры, а потом просеива%
ется вниз, меняясь местами с наименьшим из двух потомков, который соответ%
ственно передвигается вверх. В нашем примере значение 44 сначала меняется местами с 06, затем с 12, так что получается дерево на рис. 2.8. Мы сформулиру%
ем алгоритм просеивания в терминах пары индексов i, j
, соответствующих эле%
ментам, которые обмениваются на каждом шаге просеивания. А читателю пред%
лагается убедиться в том, что метод действительно сохраняет инварианты,
определяющие пирамиду.
Элегантный метод построения пирамиды in situ был предложен Флойдом
[2.2]. Метод использует процедуру просеивания sift
, представленную ниже.
Пусть дан массив h
0
... h n–1
; ясно, что элементы h
m
... h n–1
(с m = n DIV 2
) уже образуют пирамиду, так как среди них нет таких пар i
,
j
, чтобы j = 2i+1
или j = 2i+2
. Эти элементы образуют нижний ряд соответствующего двоичного дере%
ва (см. рис. 2.6), где никакой упорядоченности не требуется. Затем пирамида расширяется влево, причем за один шаг в нее включается один новый элемент,
который ставится на свое правильное место просеиванием. Этот процесс пока%
зан в табл. 2.6.
PROCEDURE sift (L, R: INTEGER); (* *)
VAR i, j: INTEGER; x: Item;
BEGIN
i := L; j := 2*i+1; x := a[i];
IF (j < R) & (a[j+1] < a[j]) THEN j := j+1 END;
WHILE (j <= R) & (a[j] < x) DO
a[i] := a[j]; i := j; j := 2*j + 1;
IF (j < R) & (a[j+1] < a[j]) THEN j := j+1 END
END;
a[i] := x
END sift
Рис. 2.7. Пирамида с семью элементами
Рис. 2.8. Просеивание ключа 44 сквозь пирамиду
Эффективные методы сортировки