будет разделить. Итак, мы вводим переменную-массив, зываемую stack, и индекс s, указывающий на самую посдед нюю запись в этом стеке (см. программу 2.11). Каким до

procedure quicksort 1;

const m = 12;

таг i,j,l,r: index; x,w: item; s: 0 .. m; stack: array [1.. m] of

record l,r: index end; begin s := I; stack[l] ./ := 1; stack[l] .r := n; i

repeat {выбор запроса из вершины стека] i

/ := stack[s] ./; г :== stack[s] .г; s :- s-1; repeat [split a[l] ... a[rj\

i := hj := r; x := a[(l+r) div 2]; repeat

while a[i] .key < x .key do / := i-f-1; while X .key < a[j] .key do j : = if i j thai

iiegin w := a[i]; я[/]:= o[y]; ф ] := w; i:= i-f-l;j:==y-l

end until I > j; Si < r then

begin [запись в стек запроса на сортировку правой части] S := S+1; slack[s] .1 :==./; stackis] ,r := г end ;

/ :==/.. until / г until 5 = 0 end [quicksort 1}

Программа 2.11.Нерекурсивная версия быстрой сортировки.

жен быть размер стека т, мы обсудим при анализе быстро!* сортировки. j

Анализ быстрой сортировки. Для того чтобы проанализй ровать свойства быстрой сортировки, мы должны сначал И)учить поведение процесса разбиения. После выбора гр

цы X процессу разбиения подвергается весь массив. Таким образом, выполняется ровно п сравнений. Число обменов ложно оценить при помощи следующего вероятностного рассуждения.

Предположим, что множество данных, которые нужно раз-де.т1ить, состоит из п ключей 1, п, и мы выбрали х в качестве границы. После разделения х будет занимать в мас-;иве позицию х. Число требующихся обменов равно числу элементов в левой части х-1, умноженному на вероятность того, что ключ нужно обменять. Ключ обменивается, если он не меньше чем х. Вероятность этого равна (п - х+\)/п. Ожидаемое число обменов вычисляется при помощи суммирования всех возможных вариантов выбора границы и деления этой суммы на п:

Следовательно, ожидаемое число обменов равно приблизительно /6.

Если предположить, что нам очень везет и мы всегда выбираем в качестве границы медиану*), то каждое разделение разбивает массив на две равные части и число проходов, необходимых для сортировки, равно log п. Тогда общее число сравнений составит n-logn, а общее число обменов - (n/6)-logn. Разумеется, нельзя ожидать, что мы все время будем попадать на медиану. На самом деле, вероятность этого равна всего лишь 1/п. Но к удивлению, если граница выбирается случайным образом, эффективность быстрой сортировки в среднем хуже оптимальной лишь в 2-In2 раз.

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

Тем не менее остается проблема наихудшего случая. Как тогда ведет себя быстрая сортировка? Ответ, к сожалению, разочаровывает. Здесь проявляется слабость быстрой сортировки (которая в таких случаях становится медленной сортировкой ). Рассмотрим, например, неблагоприятный случай.

*) См. следующий раздел. - Прим, перев.

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

Очевидно, что эффективность алгоритма быстрой сорти-ровки определяется выбором элемента х. В нащем примере программа выбирает в качестве х элемент, расположенный посередине. Заметим, что почти с тем же успехом можно было бы выбрать либо первый, либо последний элемент; а [I] или а[г]. Но при таком выборе наихудщий вариант встретится, когда массив уже предварительно рассортирован; быстрая сор! тировка в этом случае проявляет определенную неприязнь к тривиальной работе и пpeдпoчитae.т..Jбecпopядoчныe массивы. При выборе среднего элемента в качестве границы это странное свойство быстрой сортировки менее заметно, так как уже рассортированный массив становится оптимальным случаем! Действительно, средняя скорость работы здесь оказывается несколько выще, если выбирается средний элемент. Хоор считает, что выбор х должен быть случайным , или в качестве х нужно выбирать медиану из небольщого числа ключей (скажем, из 3-ех) [2.12, 2.13]. Такой осмотрительный выбор почти не влияет на среднюю скорость быстрой сортировки, но значительно улучщаёт скорость в худшем случае. Как мы видим, быстрая сортировка напоминает азартню игру, где следует заранее рассчитать, сколько можно позволить себе проиграть в случае невезения.

Из этого нужно сделать важный вывод, на который программист должен обратить особое внимание. К чему приводит наихудший случай, разобранный выше в связи со скоростью выполнения программы 2.11? Мы видим, что при каждом разбиении правая часть подмассива состоит из одного элемента; запрос на сортировку этой части заносится в стек для последующего выполнения. Следовательно, максимальное число запросов и поэтому необходимый общий размер стека оказываются равными п. Конечно же, это абсолютно неприемлемо. (Заметим, что с рекурсивной версией дело обстоит не лучше, а на самом деле даже хуже, поскольку система, допускающая рекурсивный вызов процедур, должна автоматически, сохранять значения локальных переменных и параметров при всех вызовах процедур, и для этой цели она использует неявный стек.) Это можно исправить, если хранить в стеке запрос на сортировку более длинной части и сразу продолжать да.пьнейшее разделение коротких частей-В этом случае размер стека можно ограничить до m calogan, ,