Сортировка слиянием

Алгоритм сортировки слиянием используется в тех случаях, когда данные расположены на внешних носителях информации или сортируется данные очень большого объема, которые невозможно расположить в оперативной памяти целиком. В этом случае данные могут быть сохранены, например, в отдельных файлах, таких размеров, которые могут быть помещены в оперативную память, например в массивы. Производится загрузка данных из файлов в массивы и сортировка данных каждого из массивов отдельно. Упорядоченные данные снова записываются в файлы. Затем производится сортировка слиянием уже упорядоченных данных, расположенных в отдельных файлах.

Поскольку мы пока не знакомы с работой с файлами в ТР, рассмотрим алгоритм сортировки слиянием на примере слияния двух предварительно упорядоченных массивов Х и Y в один массив Z. Данные в массивах расположены в порядке возрастания их значений.

Обзначим через переменные dx, dy - длину (размер) массивов X, Y соответственно. Переменные ix, iy - счетчики (адреса) тех же массивов. Переменная iz - счетчик числа элементов нового массива Z.

Схема алгоритма сортировки слиянием

нет

да

да да

нет нет

Текст программы сортировки слиянием

Uses crt;

Var { Описание массивов и переменных}

X, Y: array[1..1000] of integer;

Z: array[1..2000] of integer;

dx,dy,ix,iy,iz,i:integer;

Begin Clrscr; { Ввод данных}

Write(' Введите длину массива Х '); readln(dx);

Writeln(' Введите упорядоченный по возрастанию массив Х');

For i:=1 to dx do read(X[i]); readln;

Write(' Введите длину массива Y '); readln(dy);

Writeln(' Введите упорядоченный по возрастанию массив Y');

For i:=1 to dy do read(Y[i]); readln;

ix:=1; iy:=1; iz:=0;

While (ix<=dx) and (iy<=dy) do

if X[ix]<Y[iy] then

begin {Перезапись значения из массива Х в массив Z}

inc(iz); Z[iz]:=X[ix]; inc(ix);

end

else

begin {Перзапись значения из массива Y в массив Z}

inc(iz); Z[iz]:=Y[iy]; inc(iy);

end;

{ Один из массивов полностью переписан }

if ix>dx then { Переписан массив Х, дописываем все оставшееся из Y}

for i:=iy to dy do

begin

inc(iz); Z[iz]:=Y[i];

end

else { Переписан массив Y, дописываем все оставшееся из X }

for i:=ix to dx do

begin

inc(iz); Z[iz]:=X[i];

end;

{ Вывод результата слияния на экран}

writeln(' Полученный массив Z');

for i:=1 to iz do write(Z[i],' '); readln;

End.

18 Задача поиска: алгоритмы и программы

Наряду с задачей сортировки актуальной при работе с данными является поиск данных по заданному признаку. Если данные не упорядочены, то для поиска приходится просматрить весь объем информации. В том случае, если данные упорядочены, для поиска используют один из двух известных алгоритмов поиска: линейный или двоичный поиск. Рассмотрим эти алгоритмы и реализующие их программы.

Пусть задан массив Х, содержащий n целых чисел, расположенных в порядке возрастания значений. Требуется найти заданное число isk.