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

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

Внимание! В этой статье лишь рассказывается о принципе сортировки слиянием. Код реализации самой сортировки находится ЗДЕСЬ!

Код в конце статьи — это код для решения конкретной задачи на слияние двух массивов N и M, которые содержат соответственно n1 и n2 элементов. Конечный массив P будет содержать n1+n2 элементов.

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

Слияние имеет большое практическое применение. Например у Вас есть 2 списка номеров телефонов, отсортированных по возрастанию и их нужно объединить в один список, тоже отсортированный по возрастанию. Перейдем непосредственно к самому алгоритму. Представим, что мы имеем 2 массива M,N, содержащие упорядоченные элементы. Нужно выполнить слияние этих массивов с массивов P. Для этого: вначале сравнивается элемент M[1] с элементом N[1] и меньший из низ записывается в P[1]. Если M[1] меньше N[1], то при выполнении следующего шага сравниваться уже будут M[2] и N[1], если наоборот — сравнивать будем M[1] и N[2]. И так до тех пор, пока один из начальных массивов не опустошиться. Тогда оставшиеся элементы в другом массиве дописываются в массив P.

Попробуем алгоритм в действии. Пусть массив M содержит 3,5,8,11,16, а массив N содержит 1,5,7,9,12,13,,18,20. Смотрим на схему

Ну а теперь как всегда код. Повторюсь еще раз: это не код сортировки слиянием!!! Это код задачи на объединение двух упорядоченных массивов!

const
n1 = 5;
n2 = 8;

var
P: array [1..n1 + n2] of integer;
M: array [1..n1] of integer;
N: array [1..n2] of integer;
i, j,l, x: integer;

begin
writeln(‘Заполните массив M (ввод ‘, n1, ‘ элементов )’);
for i := 1 to n1 do
read(M[i]);
writeln(‘Заполните массив N (ввод ‘, n2, ‘ элементов )’);
for i := 1 to n2 do
read(N[i]);
j := 1;
l := 1;
for i := 1 to n1+n2 do
if j>n1
then
begin
P[i] := N[l];
l := l+1;
end
else
if l>n2
then
begin
P[i] := M[j];
j := j+1;
end
else
if M[j]<=N[l]
then
begin
P[i] := M[j];
j := j+1;
end
else
begin
P[i] := N[l];
l := l+1;
end;

for i := 1 to n1 + n2 do
write(P[i]:3);
end.

Задача решена. Следующая статья в разделе будет посвящена одной из самых эффективных сортировок — обменной сортировке с разделением.

11 комментариев

  • bigspawn

    Ответить 10.01.2012 01:50

    Ух ты! Не знал о таком методе. Однако, он не преподается ни в школах ни в университетах

  • Mr.Cheater

    Ответить 10.01.2012 01:50

    Эта сортировка рассчитана на конкретные задачи ,поэтоу нужна не всем.
    Но все же ,согласитесь, она тоже может пригодится .

  • секрет

    Ответить 13.01.2012 01:51

    Что то я не понял на картинке, там шаг четвертый 5<8 , а пятый 7<8 — ? Там же семь есть, четвертый значит должен быть 5<7 а не 8ми. И еще шаги 9 и 10 аналогично. Это из-за того, что мы берем 2 уже отсортированных массива и проверять 2 числа в одном массиве нет смысла?

  • Kiber

    Ответить 13.01.2012 20:50

    полный отстой представленный код не работает, что за лажа, собралась шайка бездельников и дурят народу голову

  • Mr.Cheater

    Ответить 16.01.2012 01:51

    Никто народу голову не дурит . А код не работал только потому,что я забыл указать ,что в начале используются константы (const).
    Попробуйте теперь , только предупреждаю : на случай если Вы невнимательно читали статью , оба вводимых массива должны быть уже упорядочены !

  • Штейн

    Ответить 16.01.2012 01:52

    «оба вводимых массива должны быть уже упорядочены ! »
    Спосощью рекурсии каждый раз когда мы возвращаемся на шаг назад, то наши 2 массива уже отсортированы, а тут бред какой-то написан, не назову это даже нормальной сортировкой слияния.

  • Topcoder

    Ответить 05.02.2012 01:52

    Штейн, то то и оно. В статье описана не сортировка слиянием массива в чистом виде, а по сути лишь одна из ее итераций, в которой происходит слияние двух упорядоченных кусков. Статья именно об этом

  • Штейн

    Ответить 05.02.2012 01:52

    Сори, я просто читал название, и в самом тексте было написано слово «Сортировка» n раз, наверно я дурак просто :3 Ну да ладно^^

  • Mr.Cheater

    Ответить 06.02.2012 01:54

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

  • Алексей

    Ответить 21.02.2012 01:54

    Полный бред. У меня, например, на ввод 30 000 элементов.

    а) это код для кол-ва элементов 5 и 8. Если изменить константы, он работать перестанет (попробуйте взять например 20 и 20). Ну или дописывать еще 100 if вложенных.

    б) Кто будет записывать даже 40 чисел, слабо было сделать randomize?

    в) Статический массив -n/c.

    Одним словом, дурите голову людям. Тут решение конкретной задачи для чисел 5 и 8, а не общий алгоритм решения.

  • Mr.Cheater

    Ответить 21.02.2012 01:54

    Алексей,

    Это не бред , а код для конкретной задачи . Повторяю еще раз : для конкретной . Здесь берется только тот случай,когда оба слияемых массива уже упорядочены . Поэтому вопрос о случайном вводе чисел отпадает .И не надо говорить,что алгоритм подходит только для массивов с колличеством элементов 5 и 8 — это не так . Я даже специально перепроверил и взял массивы по 20 элементов,как вы и говорили . Все работает .

Оставить комментарий