Полный 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;

Чтобы вы поняли каждую строчку, рассмотрим детально, как она работает на любом массиве, пусть:
Полный Merge Sort ( Сортировка Слиянием )



Изначальное а=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), мы имеем такой массив:
Полный Merge Sort ( Сортировка Слиянием )
Что за массив rez? Это временный массив, куда мы будем класть по возрастанию числа из массива mas.
А здесь:

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

Мы переносим отсортированные числа в наш массив.
Теперь как оно сортируется. Достаточно понять строчку
if (n1<x+1) and ((n2>c) or (mas[n1]<mas[n2])) then 


Если чуть-чуть подумаете, то сами легко разберётесь в этой строчке кода.
Вот, собственно, мы всё разобрали! Удачи)
Понравилась новость? Добавь в закладки!
Хочешь получать свежие новости? Подпишись на обновления с сайта!
Рекомендуем посмотреть:
#1 | написал: curash | 19 июня 2012 18:56 | ICQ: 628194130 | Пользователь offline

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

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


#2 | написал: sidrelena | 23 октября 2012 22:53 | ICQ: | Пользователь offline

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

 

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

 

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

 

 


#3 | написал: Mr.Cheater | 23 октября 2012 23:11 | ICQ: 360239964 | Пользователь offline

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

sidrelena,

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

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

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

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

 

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

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

 


#4 | написал: sidrelena | 24 октября 2012 12:01 | ICQ: | Пользователь offline

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

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


#5 | написал: Mr.Cheater | 24 октября 2012 22:04 | ICQ: 360239964 | Пользователь offline

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

sidrelena,

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

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

 

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


#6 | написал: Светлана | 21 декабря 2012 02:14 | ICQ: |

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

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

Есть претензии к оформлению и именованию переменных.
Вот так было бы более удобочитаемо и понятно. Автору просьба: используйте для обозначению конца и начала какой-либо структуры внятные имена (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 < middle) and ((ind2 > 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; 

#7 | написал: Mr.Cheater | 21 декабря 2012 07:51 | ICQ: 360239964 | Пользователь offline

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

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


#8 | написал: Вадим | 22 декабря 2012 15:19 | ICQ: |

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

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


#9 | написал: Mr.Cheater | 23 декабря 2012 18:56 | ICQ: 360239964 | Пользователь offline

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

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


#10 | написал: Анастасия | 26 декабря 2012 10:39 | ICQ: |

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

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


#11 | написал: SumanDark | 26 декабря 2012 21:19 | ICQ: | Пользователь offline

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

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

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


#12 | написал: юрий | 6 августа 2014 22:46 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
не пойму , а что такое mas и где оно объявлено

#13 | написал: Александр | 12 января 2015 18:18 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
Юрий, mas - глобальный массив, и он, видимо объявлен за пределами этой процедуры.

#14 | написал: Рустем | 28 марта 2015 21:34 | ICQ: |

Группа: Гости
Публикаций: 0
Комментариев: 0
ахаха!!!!! Зачет круто круто круто!!!!! Админ ты лучший!!!!!!!!!!

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

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

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