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

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


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

Код в конце статьи - это код для решения конкретной задачи на слияние двух массивов 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.

Задача решена . Следующая статья в разделе будет посвящена одной из самых эффективных сортировок - обменной сортировке с разделением.
Понравилась новость? Добавь в закладки!
Хочешь получать свежие новости? Подпишись на обновления с сайта!
Рекомендуем посмотреть:
#1 | написал: bigspawn | 10 января 2012 16:45 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#2 | написал: Mr.Cheater | 10 января 2012 17:03 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#3 | написал: Kiber | 13 января 2012 17:52 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#4 | написал: Mr.Cheater | 16 января 2012 10:22 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#5 | написал: секрет | 16 января 2012 14:11 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#6 | написал: Штейн | 5 февраля 2012 19:02 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#7 | написал: Topcoder | 5 февраля 2012 20:58 | ICQ: | Пользователь offline

Группа: Администраторы
Публикаций: 14
Комментариев: 9

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


#8 | написал: Штейн | 5 февраля 2012 23:45 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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


#9 | написал: Mr.Cheater | 6 февраля 2012 14:16 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


#10 | написал: Алексей | 21 февраля 2012 17:43 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0

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

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

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

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

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


#11 | написал: Mr.Cheater | 21 февраля 2012 18:59 | ICQ: 360239964 | Пользователь offline

Группа: Администраторы
Публикаций: 33
Комментариев: 68

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


Добавление комментария

Ваше Имя:
Ваш E-Mail:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Вставка исходного кода Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера

Введите два слова, показанных на изображении: