 |
|
сортировка с помощью разделения (быстрая)
Этот улучшенный метод сортировки основан на обмене. Это самый лучший из всех известных на данный момент методов сортировки массивов. Его производительность столь впечатляюща, что изобретатель Ч. Хоар назвал этот метод быстрой сортировкой (Quicksort) . В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, что у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно сдвигаться с двух сторон. Это возможно в том случае, когда мы знаем, что порядок действительно обратный. Однако полученный при этом алгоритм может оказаться и не удачным, что, например, происходит в случае n идентичных ключей: для разделения нужно n/2 обменов. Этих необязательных обменов можно избежать, если операторы просмотра заменить на такие:
WHILE a[i] <= x DO i := i + 1 END;
WHILE x <= a[i] DO j := j – 1 END
В этом случае x не работает как барьер для двух просмотров. В результате просмотры массива со всеми идентичными ключами приведут к переходу через границы массива.
Наша цель – не только провести разделение на части исходного массива элементов, но и отсортировать его. Будем применять процесс разделения к получившимся двум частям, до тех пор, пока каждая из частей не будет состоять из одного-единственного элемента. Эти действия описываются в программе 2.8.
ПРОГРАММА 2.8. QUICKSORT.
PROGRAM QS;
VAR N,I:INTEGER;
A:ARRAY[0..50] OF INTEGER;
PROCEDURE SORT(L,R: INTEGER);
VAR
I,J,X,W: INTEGER;
BEGIN
I:=L;
J:=R;
X:=A[(L+R) DIV 2];
REPEAT
WHILE A[I]<X DO INC(I);
WHILE X<A[J] DO DEC(J);
IF I<=J THEN BEGIN
W:=A[I];
A[I]:=A[J];
A[J]:=W;
INC(I);
DEC(J)
END
UNTIL I>J;
IF L<J THEN SORT(L,J);
IF I<R THEN SORT(I,R);
END;
BEGIN
WRITELN('Введи длину массива');
READ(N);
WRITELN('Введи массив');
FOR I:=1 TO N DO READ(A[I]);
SORT(1, N);
WRITELN('Результат:');
FOR I:=1 TO N DO WRITE(A[I],' ')
END.
Анализ Quicksort. Процесс разделения идет следующим образом: выбрав некоторое граничное значение x, мы затем проходим целиком по всему массиву. При этом выполняется точно n сравнений. Ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x.
M = [Sx:1 <= x <= n:(x-1)*(n-(x-1))/n]/n
= [Su:0 <= u <= n-1: u*(n-u)]/n2
= n*(n-1)/2n-(2n2-3n+1)/6n = (n-1/n)/6 (2.20.)
В том случае, если бы нам всегда удавалось выбирать в качестве границы медиану, то каждый процесс разделения расщеплял бы массив на две половинки, и для сортировки требовалось бы всего n*log n подходов. В результате общее число сравнений было бы равно n*log n, а общее число обменов – n*log(n) /6. Но вероятность этого составляет только 1/n.
Главный из недостатков Quicksort – недостаточно высокая производительность при небольших n, впрочем этим грешат все усовершенствованные методы, одним из достоинств является то, что для обработки небольших частей в него можно легко включить какой-либо из прямых методов сортировки.