Главная  Терминология Хоора 

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

меньшими, чем х, и правую - с ключами большими .к. лерь запишем этот алгоритм разделения в виде процедуры оограмме 2.9. Заметим, что отношения > и <; заменены -р. и отрицания которы.х в операторе цикла с пред-й^лем - это < и >. При такой замене х действует как барьер Д- обоих просмотров.

procedurepattition\

таг w,x: item;

begin i I; j . n;

выбор случайного элемента x;

repeat

wliile a\i].key < x .key do f := i-f I; wliile x.key < a[j] .key do j := j-1; if/<7tlien

begin w := a{i]; a[i] := a[j]; alj] w;

until J > J

Программа 2.9. Разделение.

Если, например, в качестве х выбрать средний ключ, равный 42, из массива ключей

44 55 12 42 94 06 18 67, то для того, чтобы разделить массив, потребуются два обмена

18 06 12 1421 94 55 44 67,

конечные значения индексов i = 5 и / = 3. Ключи ai, ...

й, 1 меньше или равны ключу х = 42, ключи й/+ь ... I с„ больше или равны х. Следовательно, мы получили два подмассива

ak-keyx.key для ft== 1, -1,

ati-keyx.key для /г==/--1. .... п

следовательно,

uk.key -x.key /г = / + 1, 1.

Тот алгоритм очень прост и эффективен, так как основные Личины, участвующие в сравнениях: i, j и х, можно ва Р^Мя просмотра хранить на быстрых регистрах. Но он ®*е может быть весьма неуклюжим, как видно из примера



С п одинаковыми ключами, в котором выполняется п/2 обц, нов. Эти ненужные обмены можно легко устранить, замець операторы просмотра на

while a[i] .key х .key do i := i+l; while л: .key ;< a[j] .key io j i=: j-l;

Ho тогда выбранный для сравнения элемент х, который щ,-ходится в массиве, перестанет служить в качестве барьер для двух разнонаправленных просмотров. В случае когд в массиве все ключи одинаковы, просмотры выйдут за его границы, если не использовать более сложные условия окоц. чания. Простота условий в программе 2.9 оправдывает из--пнтттнир пбмрны кптпрьтр R среднем для случайных масса. ВОВ происходят довольно редко. Небольшую экономии можно, однако, получить, заменив условие, управляющее обменом, на I

i<i

вместе i /. Но такую замену нельзя распространить на оба оператора

/:==г+1; /:==/-1

которые поэтому требуют использования различных условий, Необходимость условия i / можно проиллюстрировать следующим примером при д; = 2: -

1112 11/

Первый просмотр и обмен дают

1111112

причем i = 5, / = 6. Второй просмотр не изменяет массив и заканчивается с i == 7 и / = 6. Если бы обмен не подчй' нялся условию i /, то произошел бы ошибочный обмен Об и йу.

В правильности алгоритма разделения можно убедитьс! на основании того, что оба утверждения (2.14) являютс* вариантами оператора цикла с постусловием. Вначале, пр i = I и / = п, они, очевидно, истинны, а при выходе с i они предполагают, что получен нужный результат.

Теперь нам пора вспомнить, что наша цель - не тольК' разделить исходный массив элементов на большие и меньШй ко также рассортировать его. Однако от разделения до сор тировки всего лишь один небольшой шаг: разделив масс! нужно, еделать то же самое с обеими полученными частда: затем с частями этих частей и т. д., пока каждая часть



п содержать только один элемент. Этот метод представ-Гпрограммой 2.10.

л^ -,рдцедура sort рекурсивно вызывает сама себя. Такое ользование рекурсии в алгоритмах - очень мощное сред-f. Мы обсудим его позже в гл. 3. В некоторых языках ограммирования старого образца рекурсия по некоторым ехн^ческим причинам запрещена. Сейчас мы покажем, как

procedure quicksort;

ftoceume sort (l,r: index); var i,j: index; x,w: item; begin i := l;j := r;

X a[(l+r) div 2]; . repeat

while a[i] .key < x .key do / := i+l;-

while ДГ .key < a[j] .key do j : = j-l; if i <. j flien

begin w := ali]; аЩ := dU]; dU] := н-; i:-i+l;j:=j-l

M end

until I >j;

if / < Jf then sort(l,j)l if f < r thenw/(i

end ; begin sort(l,n) end {quicksort}

Программа 2.10. Быстрая сортировка.

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

Основа итеративного решения - ведение списка запросов на разделения, которые еще предстоит выполнить. После каждого шага нужно произвести два очередных разделения, н лишь одно из них можно выполнить непосредственно при Следующей итерации, запрос на другое заносится в список, ажно, разумеется, что запросы из списка выполняются обратной последовательности. Это предполагает, что пер-нын занесенный в список запрос выполняется последним Наоборот; список ведет себя как пульсирующий стек. В следующей нерекурсивной версии быстрой сортировки каждый апрос представлен просто левым и правым индексами, опре- ляющими границы части, которую впоследствии нужно




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