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

• Название: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
• Анкор: 11221
• Дата: 18.05.2023
• Размер: 2.67 Mb.
• Имя файла: Algoritmy_i_struktury_dannyh.pdf
• Тип: Книга; #1142198
• страница: 9 из 22

Анализ быстрой сортировки. Чтобы изучить эффективность быстрой сорти%
ровки, нужно сначала исследовать поведение процесса разделения. После выбора разделяющего значения x
просматривается весь массив. Поэтому выполняется в точности n
сравнений. Число обменов может быть определено с помощью сле%
дующего вероятностного рассуждения.
Если положение разделяющего значения фиксировано и соответствующее значение индекса равно u
, то среднее число операций обмена равно числу элемен%
тов в левой части сегмента, а именно u
, умноженному на вероятность того, что элемент попал на свое место посредством обмена. Обмен произошел, если элемент принадлежал правой части; вероятность этого равна
(n–u)/n
. Поэтому среднее число обменов равно среднему этих значений по всем возможным значениям u
:
M = [S
S
S
S
Su: 0
≤ u ≤ n–1 : u*(n–u)]/n
2
= n*(n–1)/2n – (2n
2
– 3n + 1)/6n
= (n – 1/n)/6
Если нам сильно везет и в качестве границы всегда удается выбрать медиану,
то каждый процесс разделения разбивает массив пополам, и число необходимых для сортировки проходов равно log(n)
. Тогда полное число сравнений равно n*log(n)
, а полное число обменов – n*log(n)/6
Разумеется, нельзя ожидать, что c выбором медианы всегда будет так везти,
ведь вероятность этого всего лишь
1/n
. Но удивительно то, что средняя эффек%
тивность алгоритма Quicksort хуже оптимального случая только на множитель
2*ln(2)
, если разделяющее значение выбирается в массиве случайно.
Однако и у алгоритма Quicksort есть свои подводные камни. Прежде всего при малых n
его производительность не более чем удовлетворительна, как и для всех эф%
фективных методов. Но его преимущество над другими эффективными методами заключается в легкости подключения какого%нибудь простого метода для обработки коротких сегментов. Это особенно важно для рекурсивной версии алгоритма.
Однако еще остается проблема наихудшего случая. Как поведет себя Quicksort тогда? Увы, ответ неутешителен, и здесь выявляется главная слабость этого алго%
Эффективные методы сортировки

Сортировка
92
ритма. Например, рассмотрим неудачный случай, когда каждый раз в качестве разделяющего значения x
выбирается наибольшее значение в разделяемом сег%
менте. Тогда каждый шаг разбивает сегмент из n
элементов на левую часть из n–1
элементов и правую часть из единственного элемента. Как следствие нужно сде%
лать n
разделений вместо log(n)
, и поведение в худшем случае оказывается по%
рядка n
2
Очевидно, что ключевым шагом здесь является выбор разделяющего значения x
. В приведенном варианте алгоритма на эту роль выбирается средний элемент.
Но с равным успехом можно выбрать первый или последний элемент. В этих слу%
чаях наихудший вариант поведения будет иметь место для изначально упоря%
доченного массива; то есть алгоритм Quicksort явно «не любит» легкие задачки и предпочитает беспорядочные наборы значений. При выборе среднего элемента это странное свойство алгоритма Quicksort не так очевидно, так как изначально упорядоченный массив оказывается наилучшим случаем. На самом деле если вы%
бирается средний элемент, то и производительность в среднем оказывается немного лучшей. Хоор предложил выбирать x
случайным образом или брать ме%
диану небольшой выборки из, скажем, трех ключей [2.10] и [2.11]. Такая предос%
торожность вряд ли ухудшит среднюю производительность алгоритма, но она сильно улучшает его поведение в наихудшем случае. Во всяком случае, ясно, что сортировка с помощью алгоритма Quicksort немного похожа на тотализатор,
и пользователь должен четко понимать, какой проигрыш он может себе позво%
лить, если удача от него отвернется.
Отсюда можно извлечь важный урок для программиста. Каковы последствия поведения алгоритма Quicksort в наихудшем случае, указанном выше? Мы уже знаем, что в такой ситуации каждое разделение дает правый сегмент, состоящий из единственного элемента, и запрос на сортировку этого сегмента сохраняется на стеке для выполнения в будущем. Следовательно, максимальное число таких за%
просов и, следовательно, необходимый размер стека равны n
. Конечно, это совер%
шенно неприемлемо. (Заметим, что дело обстоит еще хуже в рекурсивной версии,
так как вычислительная система, допускающая рекурсивные вызовы процедур,
должна автоматически сохранять значения локальных переменных и параметров всех активаций процедур, и для этого будет использоваться скрытый стек.) Выход здесь в том, чтобы сохранять на стеке запрос на обработку более длинной части,
а к обработке короткой части приступать немедленно. Тогда размер стека
M
мож%
но ограничить величиной log(n)
Соответствующее изменение локализовано в том месте программы, где на сте%
ке сохраняются новые запросы на сортировку сегментов:
IF j – L < R – i THEN
IF i < R THEN (*          *)
INC(s); low[s] := i; high[s] := R
END;
R := j (*€     *)
ELSE
IF L < j THEN (*          *)

93
INC(s); low[s] := L; high[s] := j
END;
L := i (*€     *)
END
2.3.4. Поиск медианы
Медиана (median) n
элементов – это элемент, который меньше (или равен) поло%
вины n
элементов и который больше (или равен) элементов другой половины.
Например, медиана чисел
16 12 99 95 18 87 10
равна
18
. Задача нахождения медианы обычно связывается с задачей сортировки, так как очевидный метод определения медианы состоит в сортировке n
элементов и вы%
боре среднего элемента. Но использованная выше процедура разделения дает потен%
циальную возможность находить медиану гораздо быстрее. Метод, который мы сей%
час продемонстрируем, легко обобщается на задачу нахождения k
%го наименьшего из n
элементов. Нахождение медианы соответствует частному случаю k = n/2
Этот алгоритм был придуман Хоором [2.4] и работает следующим образом.
Во%первых, операция разделения в алгоритме Quicksort выполняется с
L = 0
и
R = n–1
, причем в качестве разделяющего значения x
выбирается a
k
. В результате получаются значения индексов i
и j
– такие, что
1.
a h
< x для всех h < i
2.
a h
> x для всех h > j
3.
i > j
Здесь возможны три случая:
1. Разделяющее значение x
оказалось слишком мало; в результате граница между двумя частями меньше нужного значения k
. Тогда операцию разде%
ления нужно повторить с элементами a
i
... a
R
(см. рис. 2.9).
Рис. 2.9. Значение x слишком мало
2. Выбранное значение x
оказалось слишком велико. Тогда операцию разде%
ления нужно повторить с элементами a
L
... a j
(см. рис. 2.10).
3.
j < k < i:
элемент a
k разбивает массив на две части в нужной пропорции и поэтому является искомым значением (см. рис. 2.11).
Операцию разделения нужно повторять, пока не реализуется случай 3. Этот цикл выражается следующим программным фрагментом:
Эффективные методы сортировки

Сортировка
94
L := 0; R := n;
WHILE L < R–1 DO
x := a[k];
        #  (a[L] ... a[R–1]);
IF j < k THEN L := i END;
IF k < i THEN R := j END
END
За формальным доказательством корректности алгоритма отошлем читателя к оригинальной статье Хоора. Теперь нетрудно выписать процедуру
Find це%
ликом:
PROCEDURE Find (k: INTEGER);
(* ADruS2_Sorts *)
(*    a  ,  a[k]   k–     *)
VAR L, R, i, j: INTEGER; w, x: Item;
BEGIN
L := 0; R := n–1;
WHILE L < R–1 DO
x := a[k]; i := L; j := R;
REPEAT
WHILE a[i] < x DO i := i+1 END;
WHILE x < a[j] DO j := j–1 END;
IF i <= j THEN
w := a[i]; a[i] := a[j]; a[j] := w;
i := i+1; j := j–1
END
UNTIL i > j;
IF j < k THEN L := i END;
IF k < i THEN R := j END
END
END Find
Рис. 2.10. Значение x слишком велико
Рис. 2.11. Значение x оказалось правильным

95
Если предположить, что в среднем каждое разбиение делит пополам размер той части массива, в которой находится искомое значение, то необходимое число сравнений будет n + n/2 + n/4 + ... + 1
≈ 2n то есть величина порядка n
. Это объясняет эффективность процедуры
Find для нахождения медиан и других подобных величин, и этим объясняется ее превос%
ходство над простым методом, состоящим в сортировке всего массива с последую%
щим выбором k
%го элемента (где наилучшее поведение имеет порядок n*log(n)
).
Однако в худшем случае каждый шаг разделения уменьшает размер множества кандидатов только на единицу, что приводит к числу сравнений порядка n
2
. Как и ранее, вряд ли имеет смысл использовать этот алгоритм, когда число элементов мало, скажем меньше 10.
2.3.5. Сравнение методов сортировки массивов
Чтобы завершить парад методов сортировки, попробуем сравнить их эффектив%
ность. Пусть n
обозначает число сортируемых элементов, а
C
и
M
– число сравне%
ний ключей и пересылок элементов соответственно. Для всех трех простых ме%
тодов сортировки имеются замкнутые аналитические формулы. Они даны в табл. 2.8. В колонках min
, max
, avg стоят соответствующие минимальные, мак%
симальные значения, а также значения, усредненные по всем n!
перестановкам n
элементов.
Таблица 2.8.
Таблица 2.8.
Таблица 2.8.
Таблица 2.8.
Таблица 2.8. Сравнение простых методов сортировки min avg max
Простые
C = n–1
(n
2
+ n – 2)/4
(n
2
– n)/2 – 1
вставки
M = 2(n–1)
(n
2
– 9n –10)/4
(n
2
– 3n – 4)/2
Простой
C = (n
2
– n)/2
(n
2
– n)/2
(n
2
– n)/2
выбор
M = 3(n–1)
n*(ln(n) + 0.57)
n
2
/4 + 3(n–1)
Простые
C = (n
2
–n)/2
(n
2
–n)/2
(n
2
–n)/2
обмены
M = 0
(n
2
–n)*0.75
(n
2
–n)*1.5
Для эффективных методов простых точных формул не существует. Основные факты таковы: вычислительные затраты для Shellsort оцениваются величиной порядка c*n
1.2
, а для сортировок Heapsort и Quicksort – величиной c*n*log(n)
, где c
– некоторые коэффициенты.
Эти формулы дают только грубую оценку эффективности как функцию параметра n
, и они позволяют классифицировать алгоритмы сортировки на примитивные, простые методы (
n
2
) и эффективные, или «логарифмические»,
методы (
n*log(n)
). Однако для практических целей полезно иметь эмпирические данные о величинах коэффициентов c
, чтобы можно было сравнить разные ме%
тоды. Более того, формулы приведенного типа не учитывают вычислительных
Эффективные методы сортировки

Сортировка
96
затрат на операции, отличные от сравнений ключей и пересылок элементов, та%
кие как управление циклами и т. п. Понятно, что эти факторы в какой%то степе%
ни зависят от конкретной вычислительной системы, но тем не менее для ориен%
тировки полезно иметь какие%нибудь эмпирические данные. Таблица 2.9
показывает время (в секундах), затраченное обсуждавшимися методами сорти%
ровки, при выполнении на персональном компьютере Лилит (Lilith). Три ко%
лонки содержат время, затраченное на сортировку уже упорядоченного массива,
случайной перестановки и массива, упорядоченного в обратном порядке. Табли%
ца 2.9 содержит данные для массива из 256 элементов, таблица 2.10 – для масси%
ва из 2048 элементов. Эти данные демонстрируют явное различие между квад%
ратичными (
n
2
) и логарифмическими методами (
n*log(n)
). Кроме того, полезно отметить следующее:
1. Замена простых вставок (
StraightInsertion
) на двоичные (
BinaryInsertion
)
дает лишь незначительное улучшение, а в случае уже упорядоченного мас%
сива приводит даже к ухудшению.
2. Пузырьковая сортировка (
BubbleSort
) – определенно наихудший из всех сравниваемых здесь методов. Даже его усовершенствованная версия, шей%
кер%сортировка (
ShakerSort
), все равно хуже, чем методы простых вставок
(
StraightInsertion
) и простого выбора (
StraightSelection
), за исключением патологического случая сортировки уже упорядоченного массива.
3. Быстрая сортировка (
QuickSort
) лучше турнирной (
HeapSort
) на множи%
тель от 2 до 3. Она сортирует обратно упорядоченный массив практически с такой же скоростью, как и просто упорядоченный.
Таблица 2.9.
Таблица 2.9.
Таблица 2.9.
Таблица 2.9.
Таблица 2.9. Время выполнения процедур сортировки для массивов из 256 элементов
Š 
‹  
Π 
StraightInsertion
0.02 0.82 1.64
BinaryInsertion
0.12 0.70 1.30
StraightSelection
0.94 0.96 1.18
BubbleSort
1.26 2.04 2.80
ShakerSort
0.02 1.66 2.92
ShellSort
0.10 0.24 0.28
HeapSort
0.20 0.20 0.20
QuickSort
0.08 0.12 0.08
NonRecQuickSort
0.08 0.12 0.08
StraightMerge
0.18 0.18 0.18

97
Таблица 2.10.
Таблица 2.10.
Таблица 2.10.
Таблица 2.10.
Таблица 2.10. Время выполнения процедур сортировки для массивов из 2048 элементов
Š 
‹  
Π 
StraightInsertion
0.22 50.74 103.80
BinaryInsertion
1.16 37.66 76.06
StraightSelection
58.18 58.34 73.46
BubbleSort
80.18 128.84 178.66
ShakerSort
0.16 104.44 187.36
ShellSort
0.80 7.08 12.34
HeapSort
2.32 2.22 2.12
QuickSort
0.72 1.22 0.76
NonRecQuickSort
0.72 1.32 0.80
StraightMerge
1.98 2.06 1.98
2.4. Сортировка последовательностей
2.4.1. Простые слияния
К сожалению, алгоритмы сортировки, представленные в предыдущей главе,
неприменимы, когда объем сортируемых данных таков, что они не помещаются целиком в оперативную память компьютера и хранятся на внешних устройствах последовательного доступа, таких как ленты или диски. В этом случае будем счи%
тать, что данные представлены в виде (последовательного) файла, для которого характерно, что в каждый момент времени непосредственно доступен только один элемент. Это очень сильное ограничение по сравнению с теми возможностями,
которые дают массивы, и здесь нужны другие методы сортировки.
Самый важный метод – сортировка слияниями (для всех вариантов сортиров%
ки слияниями Вирт употребляет родовое наименование Mergesort – прим. перев.).
Слиянием (merging, collating) называют объединение двух (или более) упорядо%
ченных последовательностей в одну, тоже упорядоченную последовательность повторным выбором из доступных в данный момент элементов. Слияние – гораз%
до более простая операция, чем сортировка, и эту операцию используют в каче%
стве вспомогательной в более сложных процедурах сортировки последовательно%
стей. Один из способов сортировки на основе слияний – простая сортировка
слияниями (StraightMerge) – состоит в следующем:
1. Разобьем последовательность на две половины, b
и c
2. Выполним слияние частей b
и c
, комбинируя по одному элементу из b
и c
в упорядоченные пары.
3. Назовем получившуюся последовательность a
, повторим шаги 1 и 2, на этот раз выполняя слияние упорядоченных пар в упорядоченные четверки.
4. Повторим предыдущие шаги, выполняя слияние четверок в восьмерки,
и будем продолжать в том же духе, каждый раз удваивая длину сливаемых
Сортировка последовательностей

Сортировка
98
подпоследовательностей, пока вся последовательность не окажется упоря%
доченной.
Например, рассмотрим следующую последовательность:
44 55 12 42 94 18 06 67
На шаге 1 разбиение последовательности дает две такие последовательности:
44 55 12 42 94 18 06 67
Слияние одиночных элементов (которые представляют собой упорядоченные последовательности длины 1) в упорядоченные пары дает:
44 94 ' 18 55 ' 06 12 ' 42 67
Снова разбивая посередине и выполняя слияние упорядоченных пар, получаем
06 12 44 94 ' 18 42 55 67
Наконец, третья операция разбиения и слияния дает желаемый результат:
06 12 18 42 44 55 67 94
Каждая операция, которая требует однократного прохода по всему набору дан%
ных, называется фазой (phase), а наименьшая процедура, из повторных вызовов которой состоит сортировка, называется проходом (pass). В приведенном примере сортировка состояла из трех проходов, каждый из которых состоял из фазы разби%
ения и фазы слияния. Чтобы выполнить сортировку, здесь нужны три ленты, по%
этому процедура называется трехленточным слиянием (three%tape merge).
На самом деле фазы разбиения не дают вклада в сортировку в том смысле, что элементы там не переставляются; в этом отношении они непродуктивны, хотя и составляют половину всех операций копирования. Их можно вообще устранить,
объединяя фазы разбиения и слияния. Вместо записи в единственную последова%
тельность результат слияния сразу распределяется на две ленты, которые будут служить источником исходных данных для следующего прохода. В отличие от вышеописанной двухфазной (two%phase) сортировки слиянием, такой метод назы%
вается однофазным (single%phase), или методом сбалансированных слияний
(balanced merge). Он явно более эффективен, так как нужно вдвое меньше опера%
ций копирования; плата за это – необходимость использовать четвертую ленту.
Мы детально разберем процедуру слияния, но сначала будем представлять данные с помощью массивов, только просматривать их будем строго последова%
тельно. Затем мы заменим массивы на последовательности, что позволит срав%
нить две программы и показать сильную зависимость вида программы от используемого представления данных.
Вместо двух последовательностей можно использовать единственный массив,
если считать, что оба его конца равноправны. Вместо того чтобы брать элементы для слияния из двух файлов, можно брать элементы с двух концов массива%источ%
ника. Тогда общий вид объединенной фазы слияния%разбиения можно проил%
люстрировать рис. 2.12. После слияния элементы отправляются в массив%прием%

99
ник с одного или другого конца, причем переключение происходит после каждой упорядоченной пары, получающейся в результате слияния в первом проходе, пос%
ле каждой упорядоченной четверки на втором проходе и т. д., так что будут равно%
мерно заполняться обе последовательности, представленные двумя концами единственного массива%приемника. После каждого прохода два массива меняют%
ся ролями, источник становится приемником и наоборот.
Дальнейшее упрощение программы получается, если объединить два концеп%
туально разных массива в единственный массив двойного размера. Тогда данные будут представлены так:
a: ARRAY 2*n OF   
Индексы i
и j
будут обозначать два элемента из массива%источника, а k
и
L
– две позиции в массиве%приемнике (см. рис. 2.12). Исходные данные – это, конечно,
элементы a
0
... a n–1
. Очевидно, нужна булевская переменная up
, чтобы управлять направлением потока данных; up будет означать, что в текущем проходе элементы a
0
... a n–1
пересылаются «вверх» в переменные a
n
... a
2n–1
, тогда как

up будет указывать, что a
n
... a
2n–1
пересылаются «вниз» в a
0
... a n–1
. Значение up переклю%
чается перед каждым новым проходом. Наконец, для обозначения длины сливае%
мых подпоследовательностей вводится переменная p
. Сначала ее значение равно
1, а затем оно удваивается перед каждым следующим проходом. Чтобы немного упростить дело, предположим, что n
всегда является степенью 2. Тогда первый вариант простой сортировки слияниями приобретает следующий вид:
PROCEDURE StraightMerge;
VAR i, j, k, L, p: INTEGER; up: BOOLEAN;
BEGIN
up := TRUE; p := 1;
REPEAT
           ;
IF up THEN
i := 0; j := n–1; k := n; L := 2*n–1
ELSE
k := 0; L := n–1; i := n; j := 2*n–1
END;
    p-   i-  j-   k-  L-  ;
up := up; p := 2*p
UNTIL p = n
END StraightMerge
Рис. 2.12. Простая сортировка слияниями с двумя массивами
Сортировка последовательностей

Сортировка
100
На следующем шаге разработки мы должны уточнить инструкции, выделен%
ные курсивом. Очевидно, что проход слияния, обрабатывающий n
элементов, сам является серией слияний подпоследовательностей из p
элементов (
p
наборов).
После каждого такого частичного слияния приемником для подпоследователь%
ности становится попеременно то верхний, то нижний конец массива%приемника,
чтобы обеспечить равномерное распределение в обе принимающие «последова%
тельности». Если элементы после слияния направляются в нижний конец массива%
приемника, то индексом%приемником является k
, и k
увеличивается после каждой пересылки элемента. Если они пересылаются в верхний конец массива%приемни%
ка, то индексом%приемником является
L
, и его значение уменьшается после каж%
дой пересылки. Чтобы упростить получающийся программный код для слияния,
k всегда будет обозначать индекс%приемник, значения переменых k
иa
L
будут об%
мениваться после каждого слияния p
%наборов, а переменная h
, принимающая зна%
чения
1
или
–1
, будет всегда обозначать приращение для k
. Эти проектные реше%
ния приводят к такому уточнению:
h := 1; m := n; (*m =      *)
REPEAT
q := p; r := p; m := m – 2*p;
 q     i-   r      j-  ;
  –     k,    k h;
h := –h;
   k  L
UNTIL m = 0
На следующем шаге уточнения нужно конкретизировать операцию слияния.
Здесь нужно помнить, что остаток той последовательности, которая осталась не%
пустой после слияния, должен быть присоединен к выходной последовательности простым копированием.
WHILE (q > 0) & (r > 0) DO
IF a[i] < a[j] THEN
        i-   k-  ;
  i  k; q := q–1
ELSE
        j-   k-  ;
  j  k; r := r–1
END
END;
    i-    ;
    j-    
Уточнение операций копирования остатков даст практически полную про%
грамму. Прежде чем выписывать ее, избавимся от ограничения, что n
является степенью двойки. На какие части алгоритма это повлияет? Нетрудно понять, что справиться с такой более общей ситуацией проще всего, если как можно дольше действовать старым способом. В данном примере это означает, что нужно продол%
жать сливать p
%наборы до тех пор, пока остатки последовательностей%источников

101
не станут короче p
. Это повлияет только на операторы, в которых устанавливают%
ся значения длины сливаемых последовательностей q
и r
. Три оператора q := p; r := p; m := m –2*p нужно заменить на приведенные ниже четыре оператора, которые, как читатель может убедиться, в точности реализуют описанную стратегию; заметим, что m
обозначает полное число элементов в двух последовательностях%источниках, ко%
торые еще предстоит слить:
IF m >= p THEN q := p ELSE q := m END;
m := m–q;
IF m >= p THEN r := p ELSE r := m END;
m := m–r
Кроме того, чтобы обеспечить завершение программы, нужно заменить усло%
вие p = n
, которое управляет внешним циклом, на p
≥
n
. После этих изменений весь алгоритм можно выразить в виде процедуры, работающей с глобальным мас%
сивом из
2n элементов:
PROCEDURE StraightMerge;
(* ADruS24_MergeSorts *)
VAR i, j, k, L, t: INTEGER; (*        a is 0 .. 2*n–1 *)
h, m, p, q, r: INTEGER; up: BOOLEAN;
BEGIN
up := TRUE; p := 1;
REPEAT
h := 1; m := n;
IF up THEN
i := 0; j := n–1; k := n; L := 2*n–1
ELSE
k := 0; L := n–1; i := n; j := 2*n–1
END;
REPEAT (*        
 i-  j-   k-   *)
IF m >= p THEN q := p ELSE q := m END;
m := m–q;
IF m >= p THEN r := p ELSE r := m END;
m := m–r;
WHILE (q > 0) & (r > 0) DO
IF a[i] < a[j] THEN
a[k] := a[i]; k := k+h; i := i+1; q := q–1
ELSE
a[k] := a[j]; k := k+h; j := j–1; r := r–1
END
END;
WHILE r > 0 DO
a[k] := a[j]; k := k+h; j := j–1; r := r–1
END;
WHILE q > 0 DO
a[k] := a[i]; k := k+h; i := i+1; q := q–1
END;
Сортировка последовательностей

Сортировка
102
h := –h; t := k; k := L; L := t
UNTIL m = 0;
up := up; p := 2*p
UNTIL p >= n;
IF up THEN
FOR i := 0 TO n–1 DO a[i] := a[i+n] END
END
END StraightMerge