END;
FOR J:=I DOWNTO R+1 DO A[J]:=A[J-1];
A[R]:=X
END;
WRITELN('Результат:');
FOR I:=1 TO N DO WRITE(A[I],' ')
END.
Анализ двоичного включения. Место включения обнаружено, если L=R. Таким образом, в конце поиска интервал должен быть единичной длины; значит, деление его пополам происходит I*logI раз. Таким образом:
C = Si: 1<=i<=n: [logI ] (2.7.)
Аппроксимируем эту сумму интегралом
Integral (1:n) log x dx = n*(log n – C) + C (2.8.)
Где C = loge = 1/ln 2 = 1.4426… . (2.9.)
Этот прием основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом
2. Он меняется местами с первым элементом а1.
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.
ПРОГРАММА 2.3. СОРТИРВКА С ПОМОЩЬЮ ПРЯМОГО ВЫБОРА.
PROGRAM SS;
VAR
I,J,R,X,N:INTEGER;
A:ARRAY[0..50] OF INTEGER;
BEGIN
WRITELN('Введи длину массива');
READ(N);
WRITELN('Введи массив');
FOR I:=1 TO N DO READ(A[I]);
FOR I:=1 TO N-1 DO
BEGIN
R:=I;
X:=A[I];
FOR J:=I+1 TO N DO IF A[J]<X THEN
BEGIN
R:=J;
X:=A[R]
END;
A[R]:=A[I];
A[I]:=X
END;
WRITELN('Результат:');
FOR I:=1 TO N DO WRITE(A[I],' ')
END.
Анализ прямого выбора. Число сравнений ключей (С), очевидно не зависит от начального порядка ключей. Для С мы имеем C = (n2 – n)/2 (2.10.).
Число перестановок минимально: Mmin = 3*(n-1) (2.11.).
В случае изначально упорядоченных ключей и максимально Mmax = n2/4 + 3*(n-1) (2.12.)
Определим Мavg . Для достаточно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-м просмотре выражением Fi = lni + g + 1 (2.13.), где g = 0.577216… - константа Эйлера.
Среднее число пересылок Mavg в сортировке с выбором есть сумма Fiс i от 1 до n
Mavg = n*(g + 1) + (Si: 1<=i<=n: ln i) (2.14.)
Вновь аппроксимируя эту сумму дискретных членов интегралом
Integral (1:n) ln x dx = x*(ln x – 1) = n*ln (n) – n + 1 (2.15.)
Получаем приблизительное значение
Mavg = n*(ln (n) + g) . (2.16.)
2.1.3. Сортировка с помощью прямого обмена.
Как и в методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу.
ПРОГРАММА 2.4. ПУЗЫРЬКОВАЯ СОРТИРОВКА.
PROGRAMBS;
VAR
I,J,X,N:INTEGER;
A:ARRAY[0..50] OF INTEGER;
BEGIN
WRITELN('Введи длину массива');
READ(N);
WRITELN('Введи массив');
FOR I:=1 TO N DO READ(A[I]);
FOR I:=2 TO N DO
FOR J:=N DOWNTO I DO
IF A[J-1]>A[J] THEN
BEGIN
X:=A[J-1];
A[J-1]:=A[J];
A[J]:=X
END;
WRITELN('Результат:');
FOR I:=1 TO N DO
WRITE(A[I],' ')
END.
Улучшения этого алгоритма напрашиваются сами собой:
1. Запоминать, были или не были перестановки в процессе
некоторого прохода.
2. Запоминать не только сам факт, что обмен имел место, но и
положение (индекс) последнего обмена.
3. Чередовать направление последовательных просмотров.
Получающийся при этом алгоритм мы назовем “шейкерной” сортировкой (ShakerSoft).
Анализ пузырьковой и шейкерной сортировок. Число сравнений в строго обменном алгоритме C = (n2 – n)/2, (2.17.), а минимальное, среднее и максимальное число перемещений элементов (присваиваний) равно соответственно M = 0, Mavg = 3*(n2 – n)/2, Mmax = 3*(n2 – n)/4 (2.18.)
Анализ же улучшенных методов, особенно шейкерной сортировки довольно сложен. Минимальное число сравнений Cmin = n – 1. Кнут считает, что улучшенной пузырьковой сортировки среднее число проходов пропорционально n – k1n1/2, а среднее число сравнений пропорционально ½(n2 – n(k2 +lnn)).
ПРОГРАММА 2.5. ШЕЙКЕРНАЯ СОРТИРОВКА.
PROGRAMSS;
VAR
J,L,K,R,X,N,I:INTEGER;
A:ARRAY[0..50] OF INTEGER;
BEGIN
WRITELN('Введи длину массива’);
READ(N);
WRITELN('Введи массив');
FOR I:=1 TO N DO
READ(A[I]);
L:=2;
R:=N;
K:=N;
REPEAT
FOR J:=R DOWNTO L DO
IF A[J-1]>A[J] THEN
BEGIN
X:=A[J-1];
A[J-1]:=A[J];
A[J]:=X;
K:=J
END;
L:=K+1;
FOR J:=L TO R DO
IF A[J-1]>A[J] THEN
BEGIN
X:=A[J-1];
A[J-1]:=A[J];
A[J]:=X;
K:=J
END;
R:=K-1
UNTIL L>R;
WRITELN('Результат:');
FOR I:=1 TO N DO
WRITE(A[I],' ')
END.
Фактически в пузырьковой сортировке нет ничего ценного, кроме ее привлекательного названия. Шейкерная же сортировка широко используется в тех случаях, когда известно, что элементы почти упорядочены – на практике это бывает весьма редко.
В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сначала отдельно сортируются и группируются элементы, отстоящие друг от друга на расстояние 4. Такой процесс называется четверной сортировкой. В нашем примере восемь элементов и каждая группа состоит из двух элементов. После первого прохода элементы перегруппировываются – теперь каждый элемент группы отстоит от другого на две позиции – и вновь сортируются. Это называется двойной сортировкой. На третьем подходе идет обычная или одинарная сортировка. На каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок.
ПРОГРАММА 2.6. СОРТИРОВКА ШЕЛЛА..
PROGRAMSHELLS;
CONST T=4;
H: ARRAY[1..4] OF INTEGER = (15,7,3,1);
VAR
I,J,K,S,X,N,M:INTEGER;
A:ARRAY[-16..50] OF INTEGER;
BEGIN
WRITELN('Введи длину массива');
READ(N);
WRITELN('Введи массив');
FOR I:=1 TO N DO
READ(A[I]);
FOR M:=1 TO T DO
BEGIN
K:=H[M];
S:=-K;
FOR I:=K+1 TO N DO
BEGIN
X:=A[I];
J:=I-K;
IF S=0 THEN S:=-K;
INC(S);
A[S]:=X;
WHILE X<A[J] DO
BEGIN
A[J+K]:=A[J];
J:=J-K
END;
A[J+K]:=X;
END;
END;
WRITELN('Результат:');
FOR I:=1 TO N DO
WRITE(A[I],' ')
END.
Анализ сортировки Шелла. Нам не известно, какие расстояния дают наилучший результат. Но они не должны быть множителями один другого. Справедлива такая теорема: если k-отсортированную последовательность i-отсортировать, то она остается k-отсортированной. Кнут показывает, что имеет смысл использовать такую последовательность, в которой hk-1 = 3hk + 1, ht = 1 и t = [log2 n] – 1. (2.19.)
2.2.2.Сортировка с помощью дерева.
Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди n-1 оставшихся элементов и т. д. Как же усовершенствовать упомянутый метод сортировки? Этого можно добиться, действуя согласно следующим этапам сортировки:
1. Оставлять после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Проделав n-1 сравнений, мы можем построить дерево выбора вроде представленного на рисунке 2.1.
06
12
06
44 12 18 06
44 55 12 42 94 18 06 67
РИСУНОК 2.1. ПОВТОРЯЮЩИЙСЯ ВЫБОР СРЕДИ ДВУХ КЛЮЧЕЙ.
2. Спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путем замены либо на пустой элемент в самом низу, либо на элемент из соседний ветви в промежуточных вершинах (см. рисунки 2.2 и 2.3.).
Д. Уилльямсом был изобретен метод Heapsort, в котором было получено существенное улучшение традиционных сортировок с помощью деревьев. Пирамида определяется как последовательность ключей a[L], a[L+1], … , a[R], такая, что a[i] <= a[2i] и a[i] <= a[2i+1] для i=L…R/2.
Р. Флойдом был предложен некий “лаконичный” способ построения пирамиды на ”том же месте”. Здесь a[1] … a[n] – некий массив, причем a[m]…a[n] (m = [nDIV 2] + 1 ) уже образуют пирамиду, поскольку индексов i и j, удовлетворяющих соотношению j = 2i (или j = 2i + 1), просто не существует.
12
44 12 18
44 55 12 42 94 18 67
РИСУНОК 2.2.ВЫБОР НАИМЕНЬШЕГО КЛЮЧА.
06
12 18
44 12 18 67
44 55 12 42 94 18 67
РИСУНОК 2.3. ЗАПОЛНЕНИЕ ДЫРОК.
Эти элементы образуют как бы нижний слой соответствующего двоичного дерева (см. рисунок 2.4.), для них никакой упорядоченности не требуется. Теперь пирамида расширяется влево; каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Получающаяся пирамида показана на рисунке 2.4.
a[1]
a[2] a[3]
a[4] a[5] a[6] a[7]
a[8] a[9] a[10] a[11] a[12] a[13] a[14] a[15]
РИСУНОК 2.4.МАССИВ, ПРЕДСТАВЛЕННЫЙВВИДЕДВОИЧНОГОДЕРЕВА.
ПРОГРАММА 2.7. HEARSORT.
PROGRAM HS;
VAR
I,X,L,N,R:INTEGER;
A:ARRAY[0..50] OF INTEGER;
PROCEDURE SIFT(L,R: INTEGER);
VAR
I,J,X: INTEGER;
BEGIN
I:=L;
J:=2*L;
X:=A[L];
IF (J<R)AND(A[J]<A[J+1]) THEN INC(J);
WHILE (J<=R)AND(X<A[J]) DO
BEGIN
A[I]:=A[J];
A[J]:=X;
I:=J;
J:=2*J;
IF (J<R)AND(A[J]<A[J+1]) THEN INC(J);
END;
END;
BEGIN
WRITELN('Введи длину массива');
READ(N);
WRITELN('Введи массив');
FOR I:=1 TO N DO
READ(A[I]);
L:=(N DIV 2)+1;
R:=N;
WHILE L>1 DO
BEGIN
DEC(L);
SIFT(L,N)
END;
WHILE R>1 DO
BEGIN
X:=A[1];
A[1]:=A[R];
A[R]:=X;
DEC(R);
SIFT(1,R);
END;
WRITELN(‘Результат:');
FOR I:=1 TO N DO
WRITE(A[I],' ')
END.
Анализ Heapsort. Heapsort очень эффективна для большого числа элементов n; чем больше n, тем лучше она работает.
В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log(n/2), log(n/2 – 1), … ,log(n – 1) позиций (логарифм по [основанию 2] «обрубается» до следующего меньшего целого). Следовательно фаза сортировки будет n – 1 сдвигов с самое большое log(n-1), log(n-2), … , 1 перемещениями. Можно сделать вывод, что даже в самом плохом из возможных случаев Heapsort потребуется n*logn шагов. Великолепная производительность в таких случаях – одно из привлекательных свойств Heapsort.
2.2.3. Сортировка с помощью разделения.
Этот улучшенный метод сортировки основан на обмене. Это самый лучший из всех известных на данный момент методов сортировки массивов. Его производительность столь впечатляюща, что изобретатель Ч. Хоар назвал этот метод быстрой сортировкой (Quicksort) . В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, что у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно сдвигаться с двух сторон. Это возможно в том случае, когда мы знаем, что порядок действительно обратный. Однако полученный при этом алгоритм может оказаться и не удачным, что, например, происходит в случае n идентичных ключей: для разделения нужно n/2 обменов. Этих необязательных обменов можно избежать, если операторы просмотра заменить на такие: