Быстрая сортировка (quick sort)
Разобравшись в двух усовершенствованных методах сортировки, построенных на принципах включения и выбора, мы теперь коснемся третьего улучшенного метода, основанного на обмене. Если учесть, что пузырьковая сортировка в среднем была самой неэффективной из всех трех алгоритмов прямой (строгой) сортировки, то следует ожидать относительно существенного улучшения. И все же это выглядит как некий сюрприз: улучшение метода, основанного на обмене, о котором мы будем сейчас говорить, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Его производительность столь впечатляюща, что изобретатель Ч. Хоар даже назвал метод быстрой сортировкой (QuickSort).
В QuickSort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов: сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но из этого примера можно извлечь и нечто действительно поучительное.
Давайте попытаемся воспользоваться таким алгоритмом: выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент ai>x. затем будем просматривать массив справа, пока не встретим aj
PROCEDURE partition:
VAR w, x: item;
BEGIN i:= 1; j := n;
Случайно выбрать x;
REPEAT
WHILE а[i] < x DO i:= i+1 END;
WHILE x < a[j] DO j:= j-1 END;
IF i <= j THEN
w :=a[i]; a[i]:=а[j]; a[j]:= w; i:= i+1; j:= j-1;
END
UNТIL i > j
END partition;
Обратите внимание, что вместо отношений> и < используются ? и ?, а в заголовке цикла с WНILE - их отрицания: < и >. При таких изменениях x выступает в роли барьера для того и другого просмотра. Если взять в качестве x для сравнения средний ключ 42, то в массиве Ключей
44 55 12 42 94 06 18 67
для разделения понадобятся два обмена: 18 с 44 и 6 с 55.
Последние значения индексов таковы: i = 5, а j = 3. Ключи а1…ai-1 меньше или равны ключу x= 42, а ключи aj+1…ап больше или равны х. Следовательно, существует две части, а именно:
Ak: 1 <= k< i: ak<=x,
Ak: j < k <= n : x<=ak.
Описанный алгоритм очень прост и эффективен, поскольку главные сравниваемые величины i, j и x можно хранить во время просмотра в быстрых регистрах машины. Однако он может оказаться и неудачным, что, например, происходит в случае n идентичных ключей: для разделения нужно n/2 обменов. Этих необязательных обменов можно избежать, если операторы просмотра заменить на такие:
WНILE a[i] <= x DO i:= i +1 END;
WНILE x <= a[j] DO j:= j-1 END;
Однако в этом случае выбранный элемент Х, находящийся среди компонент массива, уже не работает как барьер для двух просмотров. В результате просмотры массива со всеми идентичными ключами приведут, если только не использовать более сложные вия их окончания, к переходу через границы массива. Простота условий, употребленных в первоначальной программе, вполне оправдывает те дополнительные обмены, которые происходят в среднем относительно редко. Можно еще немного сэкономить, если изменить заголовок, управляющий самим обменом: от i <= j перейти к i = j. Однако это изменение не должно касаться двух операторов: i := i – 1; j := j - 1. Поэтому для них потребуется отдельный условный оператор. Убедиться в правильности алгоритма разделения можно, удостоверившись, что отношения представляют собой инварианты оператора цикла с REPEAT. Вначале при i = 1 и j = n их истинность тривиальна, а при выходе с 1 > j они дают, как раз желаемый результат.
Теперь напомним, что наша цель - не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет, однако, лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем - к частям частей, и так до тех пор, пока каждая из частей не будет состоять из одного-единственного элемента. Эти действия описываются ниже.
PROCEDURE QuickSort;
PROCEDURE sort(L,R: index);
VAR i, j; index; w, x: item;
BEGIN i := L; j := А;
x:= a[(L+R) DIV 2];
REPEAT
WНILE a[i] < x DO i := i+1 END;
WНILE x < a[j] DO j := j-1 END;
IF i <= j THEN
w := а[i]; a[i] := a[j]; a[j] := w; i:= i+1; j:=j+1;
END
UNTIL i > j;
IF L < j THEN sort(L, j) END;
IF i < R ТНEN sort (i , R) END
END sort;
BEGIN sort(1, n)
END QuickSort;
Процедура sort рекурсивно обращается сама к себе. Рекурсии в алгоритмах - это очень мощный механизм. Во многих "старых" языках программирования от рекурсий по некоторым техническим причинам отказывались. Поэтому мы теперь покажем, как тот же алгоритм можно выразить и не рекурсивной процедурой. Решение, очевидно, заключается в том, что рекурсию нужно заменить итерацией. При этом понадобятся, конечно, некоторые дополнительные операции по сохранению нужной информации.
Суть итеративного решения заключается во введении списка требуемых разделений, т. е. разделений, которые необходимо провести. На каждом этапе возникают две задачи по разделению. И только к одной из них мы можем непосредственно сразу же приступить в очередной итерации, другая же заносится в упомянутый список. При этом, конечно, существенно, что требования из списка выполняются несколько специфическим образом, а именно в обратном порядке. Следовательно, первое из перечисленных требований выполняется последним и наоборот. В приводимой рекурсивной версии QuickSort каждое требование задается просто левым и правым индексами - это границы части, требующей дальнейшего разделения. Таким образом, мы вводим переменную-массив под именем stack и индекс s, указывающий на самую последнюю строку в стеке. О том, как выбрать подходящий размер стека М, речь пойдет при анализе работы QuickSort.
PROCEDURE NonRecursiveQuickSort;
CONST M = 12;
VAR i, j, L, А: index; x, W: item;
s:[О .. М];
stack: ARRAY [1 .. М] OF RECORD L,R: index END;
BEGIN s: = 1; stack [1].L:= 1; stack[s].R:= n;
REPEAT (*. выбор из стека последнего запроса *)
L := stack[s]. L; R: = stack[s].R; s: = s-1;
REPEAT (* разделение а[ L] ... а[R] *)
i := L; j := А; x := a[(L+R) DIV 2];
REPEAT
WHILE а[i] < x DO i:=i+1 END;
WHILE x < a[j] DO j:=j-1 END;
IF i <= j THEN
w:= а[i]; а[i] := a[j]; a[j] := w; i:=i+1; j:=j-1
END
UNПL i > j;
IF i < R THEN (* запись в стек запроса из правой части * )
s := s+1; stack[s].L := i; stack[s].R := R
END;
R = j (* теперь L и R ограничивают левую часть *)
UNПL L >= R
UNПL s = 0
END NonRecursiveQuickSort;
Анализ QuickSort.
Для исследования производительности QuickSort сначала необходимо разобраться, как идет процесс разделения. Выбрав некоторое граничное значение x, мы затем ходим целиком по всему массиву. Следовательно, при этом выполняется точно n сравнений. Число же обменов можно определить из следующих вероятностных соображений. При заданной границе значений x ожидаемое число операций обмена равно, числу элементов в левой части разделяемой последовательности, то есть n - 1, умноженному на вероятность того, что при обмене каждый такой элемент попадает на свое место. Обмен происходит, этот элемент перед этим находился в правой части. Вероятность этого равна (n - (x - 1))/n. Поэтому ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x.
M = [Sx: 1 <= x <= n: (x-1)*(n-(x–1))/n]/n =
= (Su: 0 <= u <= n-1: u (n-u)]/(n*n) =
= n * (n - 1)/2n - (2n2 - Зn + 1) / 6n = (n - 1/n) / 6.
Представим себе, что мы - счастливчики и нам всегда удаётся выбрать в качестве границы медиану, в этом случае каждый процесс разделения расщепляет массив на две половины и для сортировки требуется всего log n проходов. В результате общее число сравнений равно n * log n, а общее число обменов - n * log(n)/6.
Нельзя, конечно, ожидать, что мы каждый раз будем выбирать медиану. Вероятность этого составляет только l/n. Существуют специальные алгоритмы для определения медианы. Удивительный, однако, факт: средняя производительность QuickSort при случайном выборе границы отличается от упомянутого оптимального варианта только лишь коэффициентом 2*In(2).
2. Быстрая сортировка (quick sort).
