Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 18
Текст из файла (страница 18)
Сортировка с и одинаковыми ключами, в котором выполняется л/2 обменов. Эти ненужные обмены можно легко устранить, заменив операторы просмотра на ъЫе аЯ .кеу х .кеу йе 1;= 1+1: иИе х 7геу «~ а!у] .кеу до у:= 7 — 1; Но тогда выбранный для сравнения элемент к, который на« ходится в массиве, перестанет служить в качестве барьера для двух разнонаправленных просмотров. В случае когда в массиве все ключи одинаковы, просмотры выйдут за его границы, если не использовать более сложные условия окон.
чвния. Простота условий в программе 2.9 оправдывает из. лишние обмены, которые в среднем для «случайных» массивов происходят довольно редко. Небольшую экономию можно, однако, получить, заменив условие, управляющее обменом, на 1С! вместе ! ~1. Но такую замену нельзя распространить на оба оператора 1:=!+ 1; 7':=! — 1 которые поэтому требуют использования различных условий.
Необходимость условия 1(1 можно проиллюстрировать следуюшим примером при х = 2: 1112! 1! Первый просмотр и обмен дают 11! 1112 причем ! = 5, ) 6. Второй просмотр не изменяет массив и заканчивается с ! = 7 и 1= 6. Если бы обмен не подчинялся условию 1я1.:1, то произошел бы ошибочный обмен Йв н Йт. В правильности алгоритма разделения можно убедиться на основании того, что оба утверждения (2.14) являются вариантами оператора цикла с постусловием.
Вначале, при 1= 1 и 1= и, они, очевидно, истинны, а при выходе с 1) ! онн предполагают, что получен нужный результат. Теперь нам пора вспомнить, что наша цель — не только разделить исходный массив элементов на большие и меньшие, йо также рассортировать его. Однако от разделения до сортировки всего лишь один небольшой шаг: разделив массив, нужно сделать то же самое с обеими полученными частями, затем с частями этих частей 'и т, д.. .пока каждая часть нв 2.2, Сортировка массивов будет содержать только один элемент.
Этот метод представлен программой 2.10. Процедура зогЕ рекурсивно вызывает сама себя. Такое использование рекурсии в алгоритмах — очень мощное средство. Мы обсудим его позже в гл. 3. В некоторых языках программирования старого образца рекурсия по некоторым техническим причинам запрещена. Сейчас мы покажем, как ргосее1пге етееЕЕЕстогЕ; ргосенвге логЕ (1,г: тетех); тат 1,1: теЕсх; л;ж: егет; Ъея!и е:==- 1; 1:= г; л:.= а((1+г) в(т 2]; гереае вЬ!1е аЯ .Аеу < 2,1сеу.йо 1:= с+1; вЫ!е х,1сеу < оИ .кеу оо 1:= 1 — 1," 1т е "1еъеп Ъев1в и':= аК; аЯ:ч а~Я; а(Я е= н'; 1:=- е+1; 1;= т' — 1 еве1 впг11 т > Л 1Г 1 < 1 тйев вогЕ(1,О1 11 е < г ЕЪевлогЕ(1,г) ево ; Ъейев логе(1,ее) ево (еЕи1с1слогЕ) Программа 2.10.
Быстрая сортировка. можно выразить тот же алгоритм в виде нерекурспвной процедуры. Очевидно, что при этом рекурсия представляется как нтерацпя, причем необходимы некоторые дополнительные операции для хранения информации. Основа итеративного решения — ведение списка запросов иа разделения, которые еще предстоит выполнить. После каждого шага нужно произвести два очередных разделения, и лишь одно из них можно выполнить непосредственно при следующей итерации, запрос на другое заносится в список.
Важно, разумеется, что запросы из списка выполняются в обратной последовательности. Это предполагает, что первый занесенный в список запрос выполняется последним и наоборот; список ведет себя как пульсирующий стек. В сле. дующей нерекурсивиой версии быстрой сортировки каждый запрос представлен просто левым и правым индексами, опре. деляющими границы части, которую впоследствии нужно !00 2. Сортировка будет разделить. Итак, мы вводим переменную-массив, называемую з)асй, и индекс з, указываюнгий на самую последнюю запись в этом стеке (см.
программу 2,! !). Каким дол. ргеседоге ди)сйзогг 1; сопит т = 12; тат 1„1,1,г: 1пг)ех; х,мч 11вт; з:О.,т; Маей; аггау 11,.т) оа гесоп$1,г: 1пйвх сои; Ъей)в и:= 1; згасй1Ц .1:= 1; згасй1!) .г:= и; геРеаз (выбор запроса из вершины стека) 1:= згасй1з) .1; г:= згасй)з) .г; з:= з — 1 гереаг )зр!й а11) ... а(г)) г:= 1; з:= г; х;= а[(1+г) Йг 2); геринг зтЫ)е а11) .йеу < х .1сау йо 1:= 1+11 тгЬ~1е х .1сеу < аЦ,йеу во 1:=,1'-1; 11 1 ~„1' ЬЬен Ъей!н тг:= аИ; аИ:= а)Я; а11):= тр) 1:= 1+1; 1:= 1 — 1 еЫ ов)И т >1; 111< гбтен Ьей)о (запись в стек запроса на сортировку правой части) з:= з+1; зтас1ф) .1:= 1; згасй!з),г:= г оно; г:=1, паЬ1 1:> г пнЬ) з = О еЫ (ри)сйзогг 1) Программа 2.1!.Нерекурсивиаи версии быстрой сортировки.
жен быть размер стека т, мы обсудим прн анализе быстрой сортировки. Лнплиз быстрой сортировки. Для того чтобы проаналнзцповать свойства быстрой сортировки, мы должны сначалр неучнть поведение процесса разбиения. После выбора грй' 10! 2.2. Сортировка массовое ннцы х процессу разбиения подвергается весь массив.
Таким образом, выполняется ровно п сравнений. Число обменов можно оценить при помощи следующего вероятностного рассуждения. Предположим, что множество данных, которые нужно разделить, состоит из и ключей 1... п, и мы выбрали х в качестве границы. После разделения х будет занимать в массиве позицию х. Число требующихся обменов равно числу элементов в левой части х — 1, умноженному на вероятность того, что ключ нужно обменять. Ключ обменивается, если ои не меньше чем х. Вероятность этого равна (п — х+1)/и. Ожидаемое число обменов вычисляется при помощи суммирования всех возможных вариантов выбора границы и деления этой суммы на п: М = — ~ — ° !и — х+ 1) = — — —.
(2.15) 1 ч'з х — 1 а 1 пав и 6 6а' х ! Следовательно, ожидаемое число обменов равно приблизительно и/б. Если предположить, что нам очень везет и мы всегда выбираем в качестве границы медиану в!, то каждое разделение разбивает массив на две равные части и число проходов, необходимых для сортировки, равно !оп п.
Тогда общее число сравнений составит п !оцп, а общее число обмснов— (и/6) 1опп. Разумеется, нельзя ожидать, что мы все время будем попадать на медиану. На самом деле, вероятность этого равна всего лишь 1/и. Но к удивлению, если граница выбирается случайным образом, эффективность быстрой сортировки в среднем хуже оптимальной лишь в 2.1п2 раз.
Однако быстрая сортировка все же имеет свои «подводные камни». Прежде всего при небольших значениях п ее эффективность невелика, как и у всех усовершенствованных методов. Ее преимущество по сравнению с другими усовершенствованными методами заключается в том, что для сортировки уже разделенных небольших подмассивов легко можно применить какой-либо простой метод.
Это особенно ценно, если говорить о рекурсивной версии программы. Тем не менее остается проблема наихудшего случая. Как тогда ведет себя быстрая сортировка? Ответ, к сожалению, разочаровывает. Здесь проявляется слабость быстрой сортировки (которая в таких случаях становится «медленной сортировкой»). Рассмотрим,например, неблагоприятный случай, ") См.
следующий раздел. — Прим. перев. х. Сортировка когда каждыи раз в качестве х выбирается наибольшее значение в подмассиве. Тогда каждый шаг разбивает сегмент из и элементов на левую часть из и — 1 элементов и правую часть, состоящую из одного элемента. В результате вместо 1од п необходимо и разбиений, и скорость работы в наихудшем случае оказывается порядка ит Очевидно, что эффективность алгоритма быстрой сортировки определяется выбором элемента х.
В нашем примере программа выбирает в качестве х элемент, расположенный посередине. Заметим, что почти с тем же успехом можно было бы выбрать либо первый, либо последний элемент: а11) или а1г). Но прн таком выборе наихудший вариант встретится, когда массив уже предварительно рассортирован; быстрая сор. тнровка в этом случае проявляет определенную «неприязнь ° к тривиальной работе и предпочитает беспорядочные массивы.
При выборе среднего элемента в качестве границы это странное свойство быстрой сортировки менее заметно, так как уже рассортированный массив становится оптимальным случаем! Действительно, средняя скорость работы здесь оказывается несколько выше, если выбирается средний элемент. Хоор считает, что выбор х должен быть «случайным», или в качестве х нужно выбирать медиану из небольшого числа ключей 1скажем, из 3-ех) 12.12, 2.!3). Такой осмотрительный выбор почти не влияет на среднюю скорость быстрой сортировки, но значительно улучшает скорость в худшем случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
