Merge Sort (или Сортировка слиянием) — одна из самых популярных методов сортирования данных в массиве. Эта устойчивая сортировка не уступает по скорости Quick Sort, к тому же она использует меньший объём памяти. В общем, её использует только тот, кому она по вкусу (точно так же с Quick Sort).
Вот так выглядит пример работы Merge Sort. Итак, мы видим, что работа данной сортировки заключена в двух частях:
- Разбивание массива ещё на две части (фиолетовые стрелки)
- Постепенная сортировка уже двух отсортированных ранее частей (красные стрелки)
Рассмотрим принцип работы. Каждый раз мы делим массив на 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]
Если чуть-чуть подумаете, то сами легко разберётесь в этой строчке кода. Вот, собственно, мы всё разобрали! Удачи)
ОТЛИЧНАЯ СТАТЬЯ Я все думал когда норм писать юудут уже хотедл уйти с сайта а вот он ГЕНИЙ
при активации кода выдал
Program1.pas(13) : Ожидался оператор
sidrelena,
Говорю еще раз
Читате внимательно условие
Это код процедуры сортировки
А не код какой либо задачи в целом
Это последнее предупреждение
Следующий Ваш комментарий подобного типа будет удален без объяснения
Ну и ладно. Удаляйте. Когда вас в сортировке шарлотанами называли оттого что невнимательно читали про слияние упорядоченных массивов ….вы что-то их не удаляли, а спокойно орали им читать.
sidrelena,
Пожалуйста не надо ссылатьсян а других. Никто ни на кого не орал.
Им все объяснили — они все поняли. Вы же продолжили оставлять комментарии, в которых Вам ничего не понятно, из-за того,что Вы не прочитали статью.
Вот представьте себя на нашем месте : Вы написали статью, старались изложить ее простым языком, не мудренно. Вы потратили на это свое время,расписывыя моменты, которые могут вызвать затруднение у читателей. И тут один из читателей говорит, что программа не работает. Вы откладываете все дела и скорей бежите смотреть,что да как. И хорошо, если действительно ошибка в коде. Это хорошо, потому что мы тоже не можем мониторить все. Но когда выясняется, что ошибка заключается в том. что человек просто поленился прочесть статью, то это как минимум проявление неуважения к тем, кто эту статью писал.
Спасибо за код. Как ни странно для форума, но он заработал с первого раза.
Есть претензии к оформлению и именованию переменных.
Вот так было бы более удобочитаемо и понятно. Автору просьба: используйте для обозначению конца и начала какой-либо структуры внятные имена (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;
Светлана,
Мы рады, что данная статья была для вас полезна.
Но это вовсе не форум, убедиться в этом можно,если посмотреть на лого сайта
Думаю,автор учтет ваши пожелания. Однако хотел бы заметить, что с rez здесь все правильно т.к это сокращение от rezul’tat,а не от result.
Очень хорошая статья) Оъясните мне, пожалуйста, как массив попадает в процедуру, я только учу паскаль, не могу понять как заставить сортировать на практике, как процедура получает массив, а потом выводит массив?:)
Вадим,
Все это будет объяснено в отдельно статье про процедуры и функции, которая будет написана скорее всего после нового года
А вот у меня список нужно отсортировать слиянием! как это сделать?
Светлана, ммммм… Я прекрасно хорошо понимаю прекрасный тон программирования, дело в том, что при надобности имена переменных пользователю поменять не сложно, а если честно, то мне mergesort легче читать с короткими именами, как ни есьм странно, мне мой код легче читается, чем ваш =). А вообще молодец, что исправили))
Анастасия, я пока занят сессией, так что как будет время отвечу.
не пойму , а что такое mas и где оно объявлено
Юрий, mas — глобальный массив, и он, видимо объявлен за пределами этой процедуры.
ахаха!!!!! Зачет круто круто круто!!!!! Админ ты лучший!!!!!!!!!!