Merge Sort

Triedenie zlučovaním je algoritmus, založený na tzv. Princípe rozdeľuj a panuj (latinsky divide et impera, anglicky divide and conquer). To znamená, že ak nejaký problém nevieme vyriešiť v celku, rozložíme si ho na viac menších a jednoduchších problémov. Ten istý postup aplikujeme aj na tieto problémy (opäť je rozdelíme na ešte menšie, mimochodom veľmi sa tu ponúka rekurzívne riešenie) až sa dostaneme na takú úroveň, ktorú sme schopní bez problému riešiť. V problému triedenia sa často chceme dostať až k poľu veľkosti 1, ktoré považujeme automaticky za zotriedené.

Triedenie zlučovaním operuje s myšlienkou, že dokážeme veľmi rýchlo a v lineárnom čase zliať (spojiť, anglicky merge) dve už zotriedená polia do jedného tak, aby výsledné pole bolo opäť zotriedené. Na začiatku samozrejme máme len jedno pole a to zotriedené nie je. My si ho však môžeme rekurzívne rozdeliť na 2 polovice, každú polovicu opäť rozdeliť na ďalšie polovice a tak ďalej. V najhlbšej hladine rekurzia sa nutne dostaneme do fázy, kedy nám ostanú už len samá jednoprvková poľa. Jednoprvkové poľa môžeme považovať za zotriedené, hovorí sa o ňom, že je zotriedené triviálne. Ako sa postupne vynárame z rekurzia, zlievame táto jednoprvková poľa na dvojprvková, tá na štvorprvková a tak pokračujeme, kým nám neostanú dve veľké polia, ktoré keď zlejeme, dostaneme naše pôvodné pole zotriedené. Pretože zlievame vždy po rozdelení na polovice, budeme to iste robiť log n krát (kde základom logaritmy je 2, pretože delíme na 2 polovice). Samotné zlievania zvládneme v čase O (n), výsledná časová zložitosť algoritmu teda bude O (n log n). Najprv si ukážeme, ako sa pole zlievajú.

Zlievanie

Majme 2 polia, ktoré sú už zotriedená:

2	3	5
1	4	7	8

Všimnite si, že pole nemusí mať rovnakú veľkosť. Keď budeme v Merge sortu deliť na polovicu poľa veľkosti 7, dostaneme presne takáto poľa. Úskalím Merge sortu je fakt, že budeme potrebovať pomocnú pamäť, tá bude zatiaľ prázdna.

2	3	5
1	4	7	8

Pomocná pamäť:

Začneme teda zlievať. V každom poli budeme potrebovať 2 indexy, ktoré budú spočiatku na prvom indexu. Tu budú zobrazené tučne.

2	3	5
1	4	7	8

Pomocná pamäť:

Porovnáme prvky na indexoch a ten menší prvok vložíme do pomocného poľa na pozícii, ktorá je súčtom indexov. Obaja indexy máme teraz na pozícii 0 (prvé pozície), pozície v pomocnom poli teda bude 0 + 0 = 0. porovnáme a zistíme, že 1 <2, vložíme teda jedničku na pozíciu 0 do pomocného poľa a index u jedničky zväčšíme o 1.

2	3	5
1	4	7	8

Pomocná pamäť:

2 <4, vložíme teda dvojku na 0 + 1 = 1 a posunieme sa s indexom.

2	3	5
1	4	7	8

Pomocná pamäť:

3 <4, vložíme 3 na pozícii 1 + 1 = 2, posunieme sa s indexom.

2	3	5
1	4	7	8

Pomocná pamäť:

Pokračujeme ďalej ...

2	3	5
1	4	7	8

Pomocná pamäť:

2	3	5
1	4	7	8

Pomocná pamäť:

Teraz sme sa dostali do fázy, kedy sme aspoň s jedným indexov už vyšli z poľa. Teraz sa pozrieme, či druhý index nie je ešte v poli (tu je) a dolejeme zvyšné prvky.

2	3	5
1	4	7	8

Pomocná pamäť:

Máme hotovo, výsledné poľa je zotriedené. V praxi samozrejme nedostaneme poľa už takto pripravené na 2 zotriedené polovice, ale poriadne rozhádzané. Musíme sa teda rekurzia dostať až na jednotková pole a tie potom začať zlievať.

Priebeh

Priebeh označuje nasledujúce diagram:

triedenie zlučovaním - Triediace / radiacej algoritmy

Možná vylepšenia

Kameňom úrazu algoritmu je potrebná pomocná pamäť. Keď sa pozriete na diagram vyššie, vidíte, čo všetko si musí funkcie držať v pamäti. Mohli by sme však triediť naopak, teda brať pôvodnú poľa ako už rozdelené na pole jednotková a tá rovno zlievať na pole veľkosti 2, tie potom na pole veľkosti 4 a podobne. Pomocné pamäti by sme sa nezbavili, ale pri troche práce by stačilo len jedno pomocné pole, ktoré by bolo rovnako veľké, ako pole pôvodné. Do neho by sme si uložili výsledok po zliatie a potom zlievali do poľa pôvodného a zas naopak. Prelievali by sme teda dáta striedavo medzi týmito poľami.

Vizualizácia

Video ukážka

Vlastnosti algoritmu

časová zložitosť	O (n log n)
stabilita	áno
rýchlosť	Rýchly

Pozn. je myslená časová zložitosť priemerného prípadu a rýchlosť vzhľadom ku všetkým triediacim algoritmom

// sliti dvou setridenych poli do jednoho
public static void merge(int[] list, int[] left, int[] right) {
  int i = 0;
  int j = 0;
  // dokud nevyjedeme z jednoho z poli
  while ((i < left.length) && (j < right.length)) {
    // dosazeni toho mensiho prvku z obou poli a posunuti indexu
    if (left[i] < right[j]) {
      list[i + j] = left[i];
      i++;
    }
    else {
      list[i + j] = right[j];
      j++;
    }
  }
  // doliti zbytku z nevyprazdneneho pole
  if (i < left.length) {
    while (i < left.length) {
      list[i + j] = left[i];
      i++;
    }
  }
  else {
    while (j < right.length) {
      list[i + j] = right[j];
      j++;
    }
  }
}

// samotne trideni
public static void merge_sort(int[] list) {
  if (list.length <= 1) //podmínka rekurze
  return ;
  int center = list.length / 2; //stred pole
  int[] left = new int[center]; //vytvoreni a naplneni leveho pole
  for (int i = 0; i < center; i++)
  left[i] = list[i];
  int[] right = new int[list.length - center]; //vytvoreni a naplneni praveho pole
  for (int i = center; i < list.length; i++)  //vytvoreni a naplneni praveho pole
  right[i - center] = list[i];
  merge_sort(left); // rekurzivni zavolani na obe nova pole
  merge_sort(right);
  merge(list, left, right); //sliti poli
}

// sliti dvou setridenych poli do jednoho
public static void merge(int[] list, int[] left, int[] right) {
  int i = 0;
  int j = 0;
  // dokud nevyjedeme z jednoho z poli
  while ((i < left.Length) && (j < right.Length)) {
    // dosazeni toho mensiho prvku z obou poli a posunuti indexu
    if (left[i] < right[j]) {
      list[i + j] = left[i];
      i++;
    }
    else {
      list[i + j] = right[j];
      j++;
    }
  }
  // doliti zbytku z nevyprazdneneho pole
  if (i < left.Length) {
    while (i < left.Length) {
      list[i + j] = left[i];
      i++;
    }
  }
  else {
    while (j < right.Length) {
      list[i + j] = right[j];
      j++;
    }
  }
}

// samotne trideni
public static void merge_sort(int[] list) {
  if (list.Length <= 1) //podmínka rekurze
  return ;
  int center = list.Length / 2; //stred pole
  int[] left = new int[center]; //vytvoreni a naplneni leveho pole
  for (int i = 0; i < center; i++)
  left[i] = list[i];
  int[] right = new int[list.Length - center]; //vytvoreni a naplneni praveho pole
  for (int i = center; i < list.Length; i++) //vytvoreni a naplneni praveho pole
  right[i - center] = list[i];
  merge_sort(left); // rekurzivni zavolani na obe nova pole
  merge_sort(right);
  merge(list, left, right); //sliti poli
}

// sliti dvou setridenych poli do jednoho
procedure merge(var list, left, right: array of integer);
var i, j: integer;
begin
  i:=0;
  j:=0;
  // dokud nevyjedeme z jednoho z poli
  while ((i < length(left)) and (j < length(right))) do begin
    // dosazeni toho mensiho prvku z obou poli a posunuti indexu
    if (left[i] < right[j]) then begin
      list[i + j]:=left[i];
      inc(i);
    end else begin
      list[i + j]:=right[j];
      inc(j);
    end;
  end;
  // doliti zbytku z nevyprazdneneho pole
  if (i < length(left)) then begin
    while (i < length(left)) do begin
      list[i + j]:=left[i];
      inc(i);
    end;
  end else begin
    while (j < length(right)) do begin
      list[i + j]:=right[j];
      inc(j);
    end;
  end;
end;

// samotne trideni
procedure merge_sort(var list: array of integer);
var center, i: integer;
    left, right: array of integer;
begin
  if (length(list) <= 1) then exit; // podminka rekurze
  center:=length(list) div 2; // stred pole
  setlength(left, center); // vytvoreni a naplneni leveho pole
  for i:=0 to (center - 1) do
  left[i]:=list[i];
  setlength(right, length(list) - center); // vytvoreni a naplneni praveho pole
  for i:=center to (length(list) - 1) do
  right[i - center]:=list[i];
  merge_sort(left); // rekurzivni zavolani na obe nova pole
  merge_sort(right);
  merge(list, left, right); // sliti poli
end;

# sliti dvou setridenych poli do jednoho
def merge(list, left, right)
  i = 0
  j = 0
  # dokud nevyjedeme z jednoho z poli
  while ((i < left.length) && (j < right.length))
    # dosazeni toho mensiho prvku z obou poli a posunuti indexu
    if (left[i] < right[j])
      list[i + j] = left[i]
      i += 1
    else
      list[i + j] = right[j]
      j += 1
    end
  end
  # doliti zbytku z nevyprazdneneho pole
  if (i < left.length)
    while (i < left.length)
      list[i + j] = left[i]
      i += 1
    end
  else
    while (j < right.length)
      list[i + j] = right[j]
      j += 1
    end
  end
end

# samotne trideni
def merge_sort(list)
  return if (list.length <= 1) # podminka rekurze
  center = list.length / 2 # stred pole
  left = Array.new(center) # vytvoreni a naplneni leveho pole
  center.times { |i| left[i] = list[i] }
  right = Array.new(list.length - center) # vytvoreni a naplneni praveho pole
  center.upto(list.length - 1) { |i| right[i - center] = list[i] }
  merge_sort(left) # rekurzivni zavolani na obe nova pole
  merge_sort(right)
  merge(list, left, right) # sliti poli
end

Článok pre vás napísal David Hartinger

Užívateľské hodnotenie:

Ešte nikto nehodnotil, buď prvý!

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.

Aktivity