Задача 18.
Есть два отсортированных в порядке неубывания массива A[1,N] и B[1,M]. Получить отсортированный по неубыванию массив C[1,N+M], состоящий из элементов массивов A и B ("слить" вместе массивы A и B).
|
Решение задачи 18.
Можно в массив C записать сначала элементы массива A, затем массива B, затем применить любой алгоритм сортировки. Но в этом случае мы не используем того, что A и B уже отсортированы. Будем просматривать элементы массивов A и B начиная с A[1] и B[1]. Если, например, A[1]>B[1], то C[1]:=B[1], и на следующем шаге сравниваем уже A[1] и B[2], занося меньший элемент пары в ячейку C[2] и т.д.
Запись алгоритма на языке Паскаль:
{Ввод массивов A и B}
Ai:=1; Bi:=1; Ci:=1; {текущие индексы в массивах A,B,C}
while Ci<=N+M do begin
if A[Ai]>B[Bi]
then begin
C[Ci]:=B[Bi];
Bi:=Bi+1
end
else begin
C[Ci]:=A[Ai]; Ai:=Ai+1;
end
Ci:=Ci+1;
{Проверка окончания одного из массивов}
if Ai>N then for i:=Bi to M do
begin
C[Ci]:=B[Bi];
Bi:=Bi+1;
Ci:=Ci+1;
end;
if Bi>N then for i:=Ai to N do
begin
C[Ci]:=A[Ai];
Ai:=Ai+1;
Ci:=Ci+1;
end;
end; {while}
|
