Полный Merge Sort ( Сортировка Слиянием )

Полный Merge Sort (Сортировка Слиянием)

Merge Sort (или Сортировка слиянием) — одна из самых популярных методов сортирования данных в массиве. Эта устойчивая сортировка не уступает по скорости Quick Sort, к тому же она использует меньший объём памяти. В общем, её использует только тот, кому она по вкусу (точно так же с Quick Sort).

Вот так выглядит пример работы Merge Sort. Итак, мы видим, что работа данной сортировки заключена в двух частях:

  1. Разбивание массива ещё на две части (фиолетовые стрелки)
  2. Постепенная сортировка уже двух отсортированных ранее частей (красные стрелки)

Рассмотрим принцип работы. Каждый раз мы делим массив на 2 части, и в конце, когда делить уже нечего, мы идём в обратном порядке, сливая два разделенных ранее частей в единую целую, и в то же время, сортируя их (причём 2 части которые сливаем уже отсортированы).

Сама процедура Merge Sort.

Procedure MergeSort(a,c:integer);
var x,j,i,n1,n2:integer; rez:array[1..1000] of integer;
begin
if c<=a then exit else begin
x:=(a+c) div 2;
MergeSort(a,x);MergeSort(x+1,c);
n1:=a; n2:=x+1;
for i:=a to c do begin
if (n1<x+1)and((n2>c)or(mas[n1]<mas[n2])) then
begin
rez[i]:=mas[n1]; inc(n1);
end else begin
rez[i]:=mas[n2]; inc(n2);
end;
end;
for j:=a to c do
mas[j]:=rez[j];
end; end;

Чтобы вы поняли каждую строчку, рассмотрим детально, как она работает на любом массиве, пусть:

Изначальное а=1 с=7, значит х=4.

Мы разбиваем всё это ещё на две процедуры 1)MergeSort(1,4) 2)MergeSort(5,7)

1) В MergeSort(1,4) а=1 с=4, значит х=2

Запускается ещё две процедуры a)MergeSort(1,2) б)MergeSort(3,4)

а) В MergeSort(1,2) a=1 c=2, значит х=1

Запускаются 2 процедуры MergeSort(1,1) MergeSort(2,2)

В обоих из них а=с и выполняется условие для exit, мы сразу же выходим из этих процедур и возвращаемся сюда.

*Дальше весь фрагмент — это сортировка 2-х отсортированных массивов. Рассмотрим его чуть позже.

Две части , на которые мы делили — это были: с 1 по 1 номер и со 2 по 2 номер. Теперь мы отсортировали с 1 по 2 номер. Делаем шаг назад в 1.

б) Пункт а закончился и запускается MergeSort(3,4).

Здесь а=3 с=5, значит х=4.

Здесь Запускаются две процедуры MergeSort(3,3) MergeSort(4,4);

Аналогично из каждого программа выходит сразу exit‘ом, т.к. с=а.

Дальше идёт сортировка с номера 3 по 4. Отсортировали.

Итак, теперь 1 по 2 элемент отсортированы между собой. Точно также отсортированы 3 по 4 элемент.

Дальше мы сортируем эти две части и превращаем в один отсортированный массив . Итак, 1 по 4 элемент отсортированы.

2) В MergeSort(5,7) а=5 с=7, значит х=6.

Здесь Запускаются две процедуры MergeSort(5,6) MergeSort(7,7); работа с MergeSort(5,6) абсолютно аналогична с пунктом 1)а) и номера с 5 по 6 отсортированы. из MergeSort(7,7) выходим сразу, т.к. с=а и выполняется exit.

Дальше идет сортировка с 5 по 7 номер. Отсортировали =)

Итак, после этих двух пунктов, точнее вызовов процедур MergeSort(1,4) и MergeSort(5,7), мы имеем такой массив:

Что за массив rez? Это временный массив, куда мы будем класть по возрастанию числа из массива mas. А здесь:

for j:=a to c do
mas[j]:=rez[j];

Мы переносим отсортированные числа в наш массив. Теперь как оно сортируется. Достаточно понять строчку

if (n1<x+1) and ((n2>c) or (mas[n1]

Если чуть-чуть подумаете, то сами легко разберётесь в этой строчке кода. Вот, собственно, мы всё разобрали! Удачи)

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

  • curash

    Ответить 09.06.2012 04:56

    ОТЛИЧНАЯ СТАТЬЯ Я все думал когда норм писать юудут уже хотедл уйти с сайта а вот он ГЕНИЙ

  • sidrelena

    Ответить 23.10.2012 20:56

    при активации кода выдал

    Program1.pas(13) : Ожидался оператор

  • Mr.Cheater

    Ответить 23.10.2012 23:57

    sidrelena,

    Говорю еще раз

    Читате внимательно условие

    Это код процедуры сортировки

    А не код какой либо задачи в целом

    Это последнее предупреждение

    Следующий Ваш комментарий подобного типа будет удален без объяснения

  • sidrelena

    Ответить 24.10.2012 09:42

    Ну и ладно. Удаляйте. Когда вас в сортировке шарлотанами называли оттого что невнимательно читали про слияние упорядоченных массивов ….вы что-то их не удаляли, а спокойно орали им читать.

  • Mr.Cheater

    Ответить 24.10.2012 12:59

    sidrelena,

    Пожалуйста не надо ссылатьсян а других. Никто ни на кого не орал.

    Им все объяснили — они все поняли. Вы же продолжили оставлять комментарии, в которых Вам ничего не понятно, из-за того,что Вы не прочитали статью.

    Вот представьте себя на нашем месте : Вы написали статью, старались изложить ее простым языком, не мудренно. Вы потратили на это свое время,расписывыя моменты, которые могут вызвать затруднение у читателей. И тут один из читателей говорит, что программа не работает. Вы откладываете все дела и скорей бежите смотреть,что да как. И хорошо, если действительно ошибка в коде. Это хорошо, потому что мы тоже не можем мониторить все. Но когда выясняется, что ошибка заключается в том. что человек просто поленился прочесть статью, то это как минимум проявление неуважения к тем, кто эту статью писал.

  • Светлана

    Ответить 21.12.2012 02:07

    Спасибо за код. Как ни странно для форума, но он заработал с первого раза.

    Есть претензии к оформлению и именованию переменных.
    Вот так было бы более удобочитаемо и понятно. Автору просьба: используйте для обозначению конца и начала какой-либо структуры внятные имена (left, right вполне подойдёт). И rez — отнюдь не сокращение от result. Скорее уж res. Это не укор в Вашу сторону как программиста. Просто правило хорошего тона. Спасибо ещё раз.

    procedure MergeSort(left, right: integer);

    var

    middle, i, j, ind1, ind2: integer;

    res: TArr;

    begin

    if right <= left then

    exit

    else

    begin

    middle := (left+right) div 2;

    MergeSort(left, middle);

    Inc(middle);

    MergeSort(middle, right);

    ind1 := left;

    ind2 := middle;

    for i := left to right do

    begin

    Inc(CounterComp);
    if (ind1 right) or (a[ind1] < a[ind2])) then

    begin

    res[i] := a[ind1];

    Inc(CounterPer);

    Inc(ind1);

    end

    else

    begin

    res[i] := a[ind2];

    Inc(CounterPer);

    Inc(ind2);

    end;

    end;

    for j := left to right do

    a[j] := res[j];

    end;
    end;

  • Mr.Cheater

    Ответить 21.12.2012 07:51

    Светлана,
    Мы рады, что данная статья была для вас полезна.
    Но это вовсе не форум, убедиться в этом можно,если посмотреть на лого сайта
    Думаю,автор учтет ваши пожелания. Однако хотел бы заметить, что с rez здесь все правильно т.к это сокращение от rezul’tat,а не от result.

  • Вадим

    Ответить 22.12.2012 01:01

    Очень хорошая статья) Оъясните мне, пожалуйста, как массив попадает в процедуру, я только учу паскаль, не могу понять как заставить сортировать на практике, как процедура получает массив, а потом выводит массив?:)

  • Mr.Cheater

    Ответить 23.12.2012 18:51

    Вадим,
    Все это будет объяснено в отдельно статье про процедуры и функции, которая будет написана скорее всего после нового года

  • Анастасия

    Ответить 26.12.2012 15:01

    А вот у меня список нужно отсортировать слиянием! как это сделать?

  • SumanDark

    Ответить 26.12.2012 21:07

    Светлана, ммммм… Я прекрасно хорошо понимаю прекрасный тон программирования, дело в том, что при надобности имена переменных пользователю поменять не сложно, а если честно, то мне mergesort легче читать с короткими именами, как ни есьм странно, мне мой код легче читается, чем ваш =). А вообще молодец, что исправили))

    Анастасия, я пока занят сессией, так что как будет время отвечу.

  • юрий

    Ответить 06.08.2014 15:02

    не пойму , а что такое mas и где оно объявлено

  • Александр

    Ответить 12.01.2015 18:18

    Юрий, mas — глобальный массив, и он, видимо объявлен за пределами этой процедуры.

  • Рустем

    Ответить 28.03.2015 21:03

    ахаха!!!!! Зачет круто круто круто!!!!! Админ ты лучший!!!!!!!!!!

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