Главная Промышленная автоматика.

procedure BblCTPCOPT(S):

1. if S содержит не больше одного элемента Шеп return S else

begin

2. выбрать произвольный элемент а из S;

3. пусть S, и 5з -последовательности элементов из S,

соответственно меньших, равных и больших а;

4. return (BbICTPC0PT(5i), затем S, затем БЫСТРСОРТ (S,)) end

Рис. 3.7. Программа Быстрсорт.

времени работы других известных алгоритмов при их реализации на большинстве существующих машин. В худшем случае Быстрсорт имеет квадратичное время работы, но для многих приложений эю не существенно.

Алгоритм 3.5. Быстрсорт

Вход. Последовательность S из п элементов а, Яа, • • • , п-Выход. Элементы последовательности 5, расположенные по порядку.

Метод. Рекурсивная процедура БЫСТРСОРТ определяется на рис. 3.7. Алгоритм состоит в вызове БЫСТРС0РТ(5). □

Теорема 3.8. Алгоритм 3.5. упорядочивает последовательность из п элементов за среднее время О {п log п).

Доказательство. Корректность алгоритма 3.5 доказывается прямой индукцией по длине последовательности 5. Чтобы проще было анализировать время работы, допустим, что все элементы в 5 различны. Это допущение максимизирует размеры последовательностей 5i и 5з, которые строятся в строке 3, и тем самым максимизирует среднее время, затрачиваемое в рекурсивных вызовах в строке 4. Пусть Т (п) - среднее время, затрачиваемое алгоритмом БЫСТРСОРТ на упорядочение последовательности из п элементов. Ясно, что Т(0)=Т(1)=6 для некоторой постоянной Ь.

Допустим, что элемент а, выбираемый в строке 2, является i-m наименьшим элементом среди п элементов последовательности 5. Тогда на два рекурсивных вызова БЫСТРСОРТ в строке 4 тратится среднее время Т {i-1) и Т {п-i) соответственно. Так как i равновероятно принимает любое значение между 1 и п, а итоговое построение последовательности БЫСТРС0РТ(5) очевидно занимает



время СП для некоторой постоянной с, то

T(n)<cn-f-i-X[7(i-l) + r(n-i)] для л>2. (3.3) Алгебраические преобразования в (3.3) приводят к неравенству

Г(п)<сп+42;Г(0. (3.4)

Покажем, что при п2 справедливо неравенство Т {n)kn In п, где k=2c-\-2b и Ь=Т{0)=Т{\). Для базиса (п=2) неравенство Т(2Х2с+2& непосредственно вытекает из (3.4). Для проведения шага индукции запишем (3.4) в виде

/1-1

Г (пХСП + J + 4 И In t. (3.5)

" " i = 2

Так как функция i In / вогнута, легко показать, что i[ni\x\nxdx -2---4" •

(•= 2 2

Подставляя (3.6) в (3.5), получаем

(3.6)

T{n)Kcn+ + kn\nn-. (3.7)

Поскольку п2 и k=2c+2b, то сп+4 b/nkn/2. Таким образом, неравенство Т {n)kn In п следует из (3.7). □

Рассмотрим две детали, важные для практической реализации алгоритма. Первая - способ "произвольного" выбора элемента а в строке 2 процедуры БЫСТРСОРТ. При реализации этого оператора может возникнуть искушение встать на простой путь, а именно всегда выбирать, скажем, первый элемент последовательности 5. Подобный выбор мог бы оказаться причиной значительно худшей работы алгоритма БЫСТРСОРТ, чем это вытекает из (3.3). Последовательность, к которой применяется подпрограмма сортировки, часто бывает уже "как-то" рассортирована, так что первый элемент мал с вероятностью выше средней. Читатель может проверить, что в крайнем случае, когда БЫСТРСОРТ начинает работу на уже упорядоченной последовательности без повторений, а в качестве элемента а всегда выбирается первый элемент из S, в последовательности S всегда будет на один элемент меньше, чем в той, из которой она строится. В этом случае БЫСТРСОРТ требует квадратичного числа шагов.



Лучшей техникой для выбора разбивающего элемента в строке 2 было бы использование генератора случайных чисел для порождения целого числа i, li\S \ и выбора затем г-го элемента из S в качестве а. Более простой подход - произвести выборку элементов из 5, а затем взять ее медиану в качестве разбивающего элемента. Например, в качестве разбивающего элемента можно было бы взять медиану выборки, состоящей из первого, среднего и последнего элементов последовательности S.

Вторая деталь - как эффективно разбить S на три последовательности 5i, 52 и 5з? Можно (и желательно) иметь в массиве А все п исходных элементов. Так как процедура БЫСТРСОРТ вызывает себя рекурсивно, ее аргумент 5 всегда будет находиться в последовательных компонентах массива, скажем A[f], Л[/+1], . . . ..., All] для некоторых / и /, Выбрав "произвольный"

элемент а, можно устроить разбиение последовательности 5 на этом же месте. Иными словами, можно расположить Si в компонентах

Alf], Alf+l], . . ., Alk], а 52и5з-в Л[/г+1], Alk+2] All]

при некотором k, fkl. Затем можно, если нужно, расщепить SjUSg, но обычно эффективнее просто рекурсивно вызвать БЫСТРСОРТ на Si и 52 и 5з, если оба этих множества не пусты.

По-видимому, самый легкий способ разбить 5 на том же месте - это использовать два указателя на массив, назовем их i и /. Вначале

begin

1. i -/;

2. / -/;

3. while t</ do

begin

4. while Л[/]>а и />/ do - 1;

5. while Л[/]<а и t</ do i-b-t + 1;

6. if i < / then

begin

7. переставить A[i] и Л[/];

8. ii + l;

9. /-/-1 end

Рис. 3.8. Разбиение S на Si и SaUs на месте их расположения.

*) Через ISI обозначена длина последовательности S.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 [34] 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002