Сортировка через два массива

Задача

Даны два массива с различным количеством элементов. Перераспределить их элементы так, чтобы в первом массиве были наименьшие из двух массивов, а во втором - наибольшие.

Решение

 

Задача решается сортировкой через два массива. В коде ниже выбран метод пузырька.

В результате в одном массиве оказываются наименьшие элементы, а во втором - наибольшие. Причем в каждом массиве элементы отсортированы по возрастанию.

Отличие от сортировки по одному массиву в следующем. Общее количество элементов равно сумме элементов двух массивов. Если за номер элемента в "двойном массиве" отвечает переменная j, то пока j меньше количества элементов первого массива, при необходимости обмен происходит в нем. Если j равна номеру последнего элемента первого массива, то при необходимости обмен происходит между последним элементом первого массива и первым второго. Если j больше количества элементов первого массива, то при необходимости обмен происходит только во втором массиве. При этом номер элемента во втором массиве определяется как j - M (где M - кол-во элементов первого массива).

Программа на языке Паскаль: 

 

const
    M = 20;
    N = 15;
 
var
    a1: array[1..M] of word;
    a2: array[1..N] of word;
    i, j, k: byte;
 
begin
    randomize;
    write ('Исходный массив №1: ');
    for i := 1 to M do begin
        a1[i] := random(256);
        write (a1[i],' ');
    end;
    writeln;
    write ('Исходный массив №2: ');
    for i := 1 to N do begin
        a2[i] := random(256);
        write (a2[i],' ');
    end;
    writeln;
 
    for i := 1 to M+N-1 do begin
        for j := 1 to M+N-i do begin
            if j < M then begin
                if a1[j] > a1[j+1] then begin
                    k := a1[j];
                    a1[j] := a1[j+1];
                    a1[j+1] := k
                end;
            end 
            else begin
                if j = M then begin
                    if a1[j] > a2[1] then begin
                        k := a1[j];
                        a1[j] := a2[1];
                        a2[1] := k
                    end;
                end 
                else begin
                    k := a2[j-M];
                    a2[j-M] := a2[j-M+1];
                    a2[j-M+1] := k
                end;
            end;
        end;
    end;
 
 
    write ('Отсортированный №1: ');
    for i := 1 to M do
        write (a1[i],' ');
    writeln;
    write ('Отсортированный №2: ');
    for i := 1 to N do
        write (a2[i],' ');
    writeln;
 
end.

 

Пример выполнения программы:

Исходный массив №1: 39 97 59 249 165 250 214 43 112 147 4 55 210 63 182 173 151 39 99 147 
Исходный массив №2: 208 24 241 148 135 188 208 116 70 152 75 51 22 213 111 
Отсортированный №1: 4 22 24 39 39 43 51 55 59 63 70 75 97 99 111 112 116 135 147 147 
Отсортированный №2: 148 213 151 152 165 173 182 188 208 208 210 214 241 249 250 

 

Тема

Одномерные массивы

Уровень

Сложные задачи

Теги

Добавить комментарий