 |
|
Сортировка с помощью простого обмена
Как и в методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу
Такой метод сортировки известен под именем “пузырьковая сортировка”
ПРОГРАММА 2.4. ПУЗЫРЬКОВАЯ СОРТИРОВКА.
PROGRAM BS;
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 +ln n)).
ПРОГРАММА 2.5. ШЕЙКЕРНАЯ СОРТИРОВКА.
PROGRAM SS;
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. СОРТИРОВКА ШЕЛЛА..
PROGRAM SHELLS;
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.