Сортування злиттям

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Приклад сортування злиттям

Сортування злиттям — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй».

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

Алгоритм сортування[ред.ред. код]

Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,

Y 1 3 13 2 4 88
m m+1 m+s-1 m+s m+s+1 m+s+r

Результатом злиття повинна бути ділянка довжини r+s у масиві X:

X 1 2 3 4 13 88
m m+1 m+2 m+3 m+s+r

Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], … , A[n] копіюються в допоміжний масив B[1], … , B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1. На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=nmod4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t. Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n. Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";": < <11><10> ; <9><8> ; <7><6> ; <5><4> ; <3><2> ; <1> >, lp=1 < <10, 11><8, 9> ; <6, 7><4, 5> ; <2, 3><1> >, lp=2 < <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4 < <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp=8 <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp³ n. Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив. Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1<n, то при виконанні останнього кроку мають місце співвідношення lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp, і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив. Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ëlog2nû =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn). Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+ë log2nû ) та округлене відношення r двох останніх:

n n(n-1)/2 n(1+ë log2nû ) r
10 45 40 1
100 4950 700 7
1000 499500 10000 50
10000 49995000 140000 350

Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+ë log2nû ) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове! Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою. Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний: Ця функція набагато коротше нерекурсивної функції, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції". Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.

Псевдокод алгоритму[ред.ред. код]

Процедура \;MergeSort(A,p,q) здійснює часткове впорядкування масиву \;A, впорядковуючи його елементи з p-го по q-ий (\;MergeSort(A,1,length(A)) здійснить впорядкування всього масиву).

\;MergeSort(A,p,q)
1 if \; q-p < 1
2    then return
3  c \gets\;\lfloor\;(p+q)/2\rfloor\;  
4 if \; q-p > 1
5    \;MergeSort(A,p,c)
6    \;MergeSort(A,c+1,q)
7 \;Merge(A,p,c,q)

\;MergeSort використовує допоміжну процедуру \;Merge(A,p,c,q), що здійснює об'єднання частин масиву A з p-го по c-ий елемент і з c+1-го по q-ий елемент в один впорядкований підмасив. Для цього використовується один додатковий масив \;B такої ж довжини як і \;A (В деяких реалізаціях B\; вдвічі коротший за A\; — мінімально можлива його довжина).

Merge(A,p,c,q)\;
1 i\gets\;p
2 j\gets\;c+1
3 for k\gets\;p to q\;
4     do if \;j>q або (\;i\le\;c і \;A[i]\le\;A[j])
5           then B[k]\gets\;A[i]
6                i\gets\;i+1
7           else B[k]\gets\;A[j]
8                j\gets\;j+1
9 for k\gets\;p to q\;
10    do \;A[k]=B[k]

Аналіз алгоритму[ред.ред. код]

Час роботи алгоритму T(n)\; по впорядкуванню \;n елементів задовільняє рекурентному співвідношенню:

T(n) = 2T\left(\frac{n}{2}\right)+O(n)\;, де \;T\left(\frac{n}{2}\right) — час на впорядкування половини масиву, O(n)\; — час на злиття цих половинок.

Враховуючи, що \;T(1)=O(1), розв'язком співвідношення є \;T(n)=O(n\log\;n).

Крім того, алгоритм потребує для своєї роботи O(n)\; додаткової пам'яті.

Алгоритм не міняє порядок розташування однакових елементів, а отже він є стабільним.

Можливі оптимізації[ред.ред. код]

Швидкість алгоритму є асимптотично оптимальною. Але її можна пришвидшити в константну кількість разів.

  • Оптимізація впорядкування невеликих частин масиву — невеликі частини масиву (наприклад, при q-p<50) впорядковувати сортуванням вставкою.
  • Оптимізація кількості копіювань елементів — при злитті двох впорядкованих масивів в один, кожен елемент копіюється два рази (спочатку у тимчасовий масив, а потім знову у початковий). Кількість копіювань можна зменшити удвічі, якщо по черзі використовувати для об'єднання початковий і тимчасовий масиви. Тоді можна не виконувати зайві операції копіювання (рядки 9-10 процедури Merge).

Робота алгоритму[ред.ред. код]

Схема алгоритму для конкретного прикладу послідовності

Проілюструємо алгоритм сортування на такій послідовності: 42 5 30 36 25 10 37 49 0 0 На початку сортування відсортовані підпослідовності містять в собі по одному елементу.

Крок 1: 5 42 | 30 36 | 10 25 | 37 49 | 0 0

Крок 2: 5 30 36 42 | 10 25 37 49 | 0 0

Крок 3: 5 10 25 30 36 37 42 49 | 0 0

Крок 4: 0 0 5 10 25 30 36 37 42 49

Тестування алгоритму[ред.ред. код]

Для перевірки правильності сортування звіримо сортування проведене програмою з сортуванням за даним алгоритмом вручну.

Проведемо сортування наступної послідовності: 56 19 3 95 23 17 38 44 69 73 84

На початку сортування послідовність є розбита на відсортовані підпослідовності по одному елементу в кожній.

56 | 19 | 3 | 95 | 23 | 17 | 38 | 44 | 69 | 73 | 84

далі кожні дві підпослідовності зливаються в одну відсортовану підпослідовність : 19 56 | 3 95 | 17 23 | 38 44 | 69 73 | 84

на наступному кроці отримаємо наступний результат злиття: 3 19 56 95 | 17 23 38 44 | 69 73 84 |

потім: 3 17 19 23 38 44 56 95 | 69 73 84 |

на останньому кроці отримаємо відсортовану послідовність: 3 17 19 23 38 44 56 69 73 84 | 95

Послідовність була відсортована за 4 кроки.

Реалізація (Паскаль)[ред.ред. код]

procedure MergeSort( var ar1, ar2: array of Integer; min, max: Integer);
var
middle, int1, int2, int3: Integer;
  begin
 
  if min<max then begin //інакше массив складається 
                     //з одного елемента і є впорядкованим.
    middle:=min div 2+max div 2;
    // рекурсивно сортуєму підсписки
    MergeSort(ar1, ar2, min, middle);
    MergeSort(ar1, ar2, middle+1, max);
    int1:=min; //вказівник на 1-й массив
    int2:=middle+1; //вказівник на 2-й массив
    int3:=min; //вказівник на обєднаний масив
 
  //обєднання сортованих масивів
    while (int1<=middle) and (int2<=max) do begin
      if ar1[int1] then begin
      ar2[int3]:=ar1[int1];
      int1:=int1+1;
    end
    else begin
      ar2[int3]:=ar1[int2];
      int2:=int2+1;
    end;
    inc(int3);
  end;
  // очистка не пустого списка
    while (int1<=middle) do begin
      ar2[int3]:=ar1[int1];
      int1:=int1+1;
      int3:=int3+1;
    end;
 
    while (int2<=middle) do begin
      ar2[int3]:=ar1[int2];
      int2:=int2+1;
      int3:=int3+1;
    end;
  end;
  //прирівнювання входящих массивів
  for int1:=min to max do
    ar1[int1]:=ar2[int1];
end;

Ще один приклад:

uses SysUtils;
const n=10;
type mas=array[1..n] of integer;
var x1,x2:mas;
    i:integer;
procedure mrg(var y,x:mas; m,s,r:integer);
var mr,k,i,j:integer;
begin
 mr:=m+s;
 i:=m;
 j:=mr;
 for k:=m to m+s+r-1 do
  if i>m+s-1 then
  begin
  x[k]:=y[j];
  j:=j+1;
  end
   else
   if j>mr+r-1 then
    begin
    x[k]:=y[i];
    i:=i+1;
    end
    else if y[i]<y[j] then
    begin
    x[k]:=y[i];
    i:=i+1;
    end
    else
     begin
     x[k]:=y[j];
     j:=j+1;
     end;end;
     procedure Mrg_rec(var a,b:mas; l,r:integer);
      var m,k:integer;
     begin
     if l>=r then exit;
     m:=(l+r)div 2;
     Mrg_rec(a,b,l,m);
     Mrg_rec(a,b,m+1,r);
     mrg(a,b,l,m-l+1,r-m);
     for k:=1 to r do
     a[k]:=b[k];
     end;
begin
randomize;
for i:=1 to n do
 x1[i]:=random(10)-5;
for i:=1 to n do
 writeln(x1[i]);
mrg_rec(X1,X2,1,n);
writeln;
 for i:=1 to n do
 writeln(x1[i]);
 readln; writeln('that''s all'); readln;
end.

А це - складний приклад реалізації сортування масивів:

program SortArrays;
{$APPTYPE CONSOLE}
uses SysUtils;
type Massive=array[1..25] of integer;
var A:massive; n:integer;
procedure RndArrInput (var a1:massive; n1:integer);
var i1:integer;
begin
Randomize;
 for i1:=1 to n1 do
 a1[i1]:=20-random(20);
end;
procedure ArrOutPut(a2:massive; n2:integer);
 var i2:integer;
begin
 for i2:=1 to n2 do
 write(a2[i2],' ');
end;
procedure Annihilate(var an:massive; nn:integer);
var i_:integer;
begin
 for i_:=1 to nn do
 an[i_]:=0;
end;
procedure MergeUnion(const a:massive; N_a:integer;
  const b:massive; N_b:integer; var c:massive; {var N_c:integer}start:integer);
  var i_a,i_b,i_c:integer;
  Begin
  i_a:=1; i_b:=1; i_c:={1;}start; 
  while (i_a<=N_a)and(i_b<=N_b) do begin
 
  if a[i_a]<b[i_b] then begin
 
  c[i_c]:=a[i_a];
  inc(i_a);
  inc(i_c);
  end else
  if a[i_a]>b[i_b] then begin
 
  c[i_c]:=b[i_b];
  inc(i_b);
  inc(i_c);
  end else begin (* a[i_a]=b[i_b] *)
 
  c[i_c]:=a[i_a];
 inc(i_a);
  {inc(i_b);} //we shouldn't write the equal value only once
 inc(i_c); c[i_c]:=b[i_b]; inc(i_b); inc(i_c);
 end
 end;
 
 while (i_a<=N_a) do begin
  c[i_c]:=a[i_a];
  inc(i_a);
  inc(i_c);
 end;
 
  while (i_b<=N_b) do begin
   c[i_c]:=b[i_b];
   inc(i_b);
   inc(i_c);
   end;
   End;
procedure MergeSort(var a3:massive; n3:Integer);
var hlp1,hlp2,hlp3:massive; cnt:integer; LineChanged:Boolean;
    cur_1, cur_2:integer; i:integer;
    cur:Integer; pnt:integer; hlp_cur:integer; WtoHlp1,WtoHlp2:Boolean;
begin
 Annihilate(hlp1,n3);
 Annihilate(hlp2,n3);
 Annihilate(hlp3,n3);
 cnt:=1; LineChanged:=true;
 while LineChanged do
 begin
   pnt:=1; lineChanged:=false;
   while pnt<=n3 do
  begin
  cur:=1; WtoHlp1:=false; Wtohlp2:=false; cur_1:=0; cur_2:=0;
  while (cur<=cnt)and(pnt<=n3) do
    begin
     hlp1[cur]:=a3[pnt];
     inc(pnt);
     inc(cur); inc(cur_1);
     WtoHlp1:=true;
    end;
   cur:=1;
  while (cur<=cnt)and(pnt<=n3) do
    begin
     hlp2[cur]:=a3[pnt];
     inc(pnt);
     inc(cur); inc(cur_2);
     WtoHlp2:=true; lineChanged:=true;
    end;
    if WToHlp1 and WToHlp2 then
    MergeUnion(hlp1,cur_1,hlp2,cur_2,hlp3,pnt-{2*cnt}(cur_1+cur_2));
    if WToHlp1 and not(WtoHlp2) then
     for i:=1 to cur_1 do
       begin
      hlp3[pnt-(cur_1+cur_2)]:=hlp1[i];
      inc(pnt);
       end;
//tail-writting. cur_1 is the point, how many elements have we in hlp1.
  end;
  cnt:=cnt*2;
  a3:=hlp3;
 end;{of while LineChanged}
end;{of procedure}
begin
  writeln('enter data:');
  readln(n);
  RndArrInput(a,n);
  ArrOutput(a,n);
  readln;
  MergeSort(a,n);
  readln;
  ArrOutput(a,n);
  readln;
end.

Джерела[ред.ред. код]

  • Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1

Посилання[ред.ред. код]