 |
|
Сортирвка с помощью прямого выбора
Сортировка с помощью прямого включения.
Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже “готовую” последовательность а1, … , аi-1 и исходную последовательность. При каждом шаге, начиная с I = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i- й элементы и перекладывается в готовую последовательность, при этом он вставляется на нужное место.
В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать x , т. е. x сравнивается с очередным элементом aj , а затем либо x вставляется на свободное место, либо aj сдвигается вправо и процесс “уходит” влево. Обратите внимание, что процесс просеивания может закончиться при выполнении одного из двух следующих различных условий:
1. Найден элемент aj с ключом, меньшим чем ключ у x.
2. Достигнут левый конец готовой последовательности
ПРОГРАММА 2.1. ССОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВКЛЮЧЕНИЯ.
PROGRAM SI;
VAR
I,J,N,X: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 BEGIN
X:=A[I];
A[0]:=X;
J:=I;
WHILE X<A[J-1] DO BEGIN
A[J]:=A[J-1];
DEC(J)
END;
A[J]:=X
END;
WRITELN('Результат:');
FOR I:=1 TO N DO WRITE(A[I],' ')
END.
Алгоритм с прямыми включениями можно легко улучшить, если обратить внимание на то, что готовая последовательность, в которую надо вставить новый элемент, сама уже упорядочена. Естественно остановиться на двоичном поиске, при котором делается попытка сравнения с серединой готовой последовательности, а затем процесс деления пополам идет до тех пор, пока не будет найдена точка включения. Такой модифицированный алгоритм сортировки называется методом с двоичным включением ( binary insertion).
ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ.
PROGRAM BI;
VAR I,J,M,L,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:=2 TO N DO BEGIN
X:=A[I];L:=1;R:=I;
WHILE L<R DO BEGIN
M:=(L+R) DIV 2;
IF A[M]<=X THEN L:=M+1 ELSE R:=M
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*log I раз. Таким образом:
C = Si: 1<=i<=n: [log I ] (2.7.)
Аппроксимируем эту сумму интегралом
Integral (1:n) log x dx = n*(log n – C) + C (2.8.)
Где C = log e = 1/ln 2 = 1.4426… . (2.9.)
Сортирвка с помощью прямого выбора
Этот прием основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом.
2. Он меняется местами с первым элементом а1.
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.
Процесс работы этим методом с теми же восемью ключами, что и в таблице 2.1., приведен в таблице 2.2. Алгоритм формулируется так:
FOR I:= 1 TO n-1 DO
Присвоить k индекс наименьшего из a[I] … a[n];
Поменять местами a[I] и a[k];
END
ПРОГРАММА 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 = ln i + 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.)