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

return{к)

else if А[к].кву < firstkey then return(i) ;

return(0) { различные ключи не найдены } end; { findpivot }

Теперь реализуем строку (3) из листинга 8.5, где необходимо переставить элементы -А[0> А[/]так, чтобы все элементы с ключами, меньшими опорного значения, располагались слева от остальных элементов. Чтобы выполнить эти перестановки, введем два курсора 1н г, указывающие соответственно на левый и правый концы той части массива А, где в настоящий момент мы переставляем (упорядочиваем) элементы. При этом считаем, что уже все элементы АЦ - 1], расположенные слева от I, имеют значения ключей, меньшие опорного значения. Соответственно элементы А{г + 1], A[j\, расположенные справа от г, имеют значения ключей, большие или равные опорному значению (рис. 8.2). Нам необходимо рассортировать элементы АЩ> A[f\.

КЛЮЧИ < опорное значение

ключи > опорное значение

i I г 1

Рис. 8.2. Ситуация, возникающая в процессе перемещения элементов

Сначала положим I = i н г = j. Затем будем повторять следующие действия, которые перемещают курсор I вправо, а курсор г влево до тех пор, пока курсоры не пересекутся.

1. Курсор перемещается I вправо, пока не встретится запись с ключом, не меньшим опорного значения. Курсор г перемещается влево, также до тех пор, пока не встретится запись с ключом, меньшим опорного значения. Отметим, что выбор опорного значения функцией findpivot гарантирует, что есть по крайней мере одна запись с ключом, значение которого меньше опорного значения, и есть хотя бы одна запись со значением ключа, не меньшим выбранного опорного значения. Поэтому обязательно существует "промежуток" между элементами и -А[у], по которому могут перемещаться курсоры I и г.

2. Выполняется проверка: если I > г (на практике возможна только ситуация, когда 1= г + 1), то перемещение элементов А[г]. .... ЖЛзаканчивается.

3. В случае I < г (очевидно, что случай I = г невозможен) переставляем местами элементы А[1] и А[г]. После этого запись А[1] будет иметь значение ключа меньшее, чем опорное значение, а А[г\ - большее или равное опорному значению. Курсор I перемещается на одну позицию от предыдущего положения вправо, а курсор г-на одну позицию влево. Далее процесс продолжается с пункта 1.

Описанный циклический процесс несколько неуклюжий, поскольку проверка, приводящая к окончанию процесса, расположена посредине. Если этот процесс оформить в виде цикла repeat, то этап 3 надо переместить в начало. Но в этом случае при 1= i и г =j сразу меняются местами элементы A{i] и независимо от того, надо это делать или нет. Но с другой стороны, это несущественно, так как мы не предполагаем перво-

Можно скопировать элементы АЩ, .... АЦ] в другой массив, упорядочить их там, а затем вернуть обратно в ячейки A[i] . . . Alj] массива А. Но мы не будем обсу>иаать этот подход, так как он требует дополнительной памяти и удлиняет сам процесс сортировки по сравнению с рассматриваемым подходом, когда перестановки элементов выполняются непосредственно в массиве А.



начальное упорядочивание элементов A[i], A[f].B любом случае, читатель должен знать о таких "шалостях" алгоритма, поэтому они не должны его озадачивать. Функция partition (разделение), которая выполняет перестановки элементов и возврашает индекс I, указываюший на точку разделения данного фрагмента массива А на основе заданного опорного значения pivot, приведена в листинге 8.7.

Листинг 8.7. Функция partition

function partition ( i, j: integer; pivot: keytype ): integer;

i, r: integer;

{ курсоры }

begin

r:= ];

repeat

swap(A[l] ,

A[r]);

wliile A[l]

. key < pivot do

i:= ;

+ 1;

while A[r]

.key>= pivot do

r: = r

until

1 > r;

return(1)

end; { partition }

Теперь можно преобразовать эскиз алгоритма быстрой сортировки (листинг 8.5) в настояшую программу quicksort (быстрая сортировка). Код этой программы приведен в листинге 8.8. Для сортировки элементов массива А типа аггау[1..п] of recordtype надо просто вызвать процедуру quicksort{l, п).

Листинг 8.8. Процедура быстрой сортировки

procedure quicksort ( i, j: integer ) ;

{ сортирует элементы Л [1], A[j) внешнего массива А }

pivot: keytype; { опорное значение } pivotindex: integer;

{ индекс элемента массива А, чей ключ равен pivot } к: integer;

{начальный индекс группы элементов, чьи ключи > pivot)

begin

(1) pivotindex:= findpivot(i, j);

(2) if pivotindex <> 0 then begin

{ если все ключи равны, то ничего делать не надо }

(3) pivot:= Alpivotindex] .key;

(4) к: = portition{i, J, pivot);

(5) quicksortd, k-1) ;

(6) qulcksort(k, j) end

end; { quicksort }

Временная сложность быстрой сортировки

Покажем, что время выполнения быстрой сортировки п элементов составляет в среднем 0(п logn) и О(п) в худшем случае. В качестве первого шага в доказательстве обоих утвервдений надо показать, что время вьшолнения процедуры partition(i, j, v)



имеет порядок 0(j - i + 1), т.е. пропорционально числу элементов, над которыми она выполняется.

Чтобы "разобраться" с временем выполнения процедуры partition, воспользуемся приемом, который часто применяется при анализе алгоритмов. Надо найти определенные "элементы", для которых в принципе можно вычислить время выполнения, а затем необходимо показать, что каждый шаг алгоритма для "обработки" одного "элемента" требует времени, не иревышаюшего константы. Тогда обшее время выполнения алгоритма можно вычислить как произведение этой константы на количество "элементов".

В данном случае в качестве "элементов" можно просто взять элементы АЩ, A[f] и для кавдого из них оценить время, необходимое для достижения в процедуре partition курсорами / и г этого элемента, начиная от исходного положения этих курсоров. Сначала отметим, что эта процедура всегда возврашает значение курсора, раз-биваюшее множество элементов А[г], на две группы, причем каждая из этих

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

Перемешение курсоров осушествляется в циклах строк (4) и (6) листинга 8.7 путем увеличения на 1 значения / или уменьшения на 1 значения г. Сколько шагов может сделать алгоритм между двумя выполнениями оператора 1:= I + 1 или оператора г:= г - 1? Для того чтобы смоделировать самый худший случай, надо обратиться к началу процедуры. В строках (1), (2) происходит инициализация курсоров I и г. Затем обязательно выполняется перестановка элементов в строке (3). Далее предположим, что циклы строк (4) и (6) "перескакивают" без изменения значений курсоров I и г. На втором и иоследуюших итерациях цикла repeat перестановка в строке (3) гарантирует, что хотя бы один из циклов while строк (4) и (6) будет выполнен не менее одного раза. Следовательно, мевду выполнениями оператора 1:= I + 1 или г:= г - 1 в самом худшем случае выполняются строки <1), (2), дважды строка (3) и проверки логических условий в строках (4), (6), (8) и снова в строке (4). Все эти операции требуют фиксированного времени, независяшего от значений in j.

В конце исполнения процедуры выполняются проверки в строках (4), (6) и (8), не связанные ни с какими "элементами", но время этих операций таюке фиксировано и поэтому его можно "присоединить" к времени обработки какого-либо элемента. Из всего вышесказанного следует вывод, что сушествует такая временная константа с, что на обработку любого элемента затрачивается время, не превышаюшее с. Поскольку процедура partition(i, j, v) обрабатывает j - i + 1 элементов, то, следовательно, обшее время выполнения этой процедуры имеет порядок ОО - i + 1).

Вернемся к оценке времени выполнения процедуры quicksort(i,j). Легко проверить, что вызов процедуры findpivot в строке (1) листинга 8.8 занимает время порядка 0{j- i -Ь 1), а в большинстве случаев значительно меньше. Проверка логического условия в строке (2) выполняется за фиксированное время, так же, как и оператор в строке (3), если, конечно, он выполняется. Вызов пропелуры partitlon(i, j, pivot), как мы показали, требует времени порядка 0(j - i + 1). Таким образом, без учета рекурсивных вызовов quicksort каждый отдельный вызов этой процедуры требует времени, по крайней мере пропорционального количеству элементов, упорядочиваемых этим вызовом quicksort.

Если посмотреть с другой стороны, то обшее время выполнения процедуры quicksort является суммой по всем элементам количества времени, в течение которого элементы находятся в части массива 4, обрабатываемой данным вызовом процедуры quicksort. Вернемся к рис. 8.1, где вызовы процедуры quicksort показаны по этапам (уровням). Очевидно, что никакой элемент не может участвовать в двух вызовах процедуры quicksort на одном уровне, поэтому время выполнения данной процедуры можно выразить как сумму по всем элементам определенной глубины, т.е. максимального уровня, на котором заканчивается сортировка для данного эле-





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

0.0019