Lekce 5 - Merge Sort

V minulé lekci, Heapsort, jsme si ukázali algoritmus Heapsort i se zdrojovými kódy.

Merge sort je algoritmus, založený na tzv. principu rozděl a panuj (latinsky divide et impera, anglicky divide and conquer). To znamená, že pokud nějaký problém neumíme vyřešit v celku, rozložíme si ho na více menších a jednodušších problémů. Ten samý postup aplikujeme i na tyto problémy (opět je rozdělíme na ještě menší, mimochodem velmi se zde nabízí rekurzivní řešení) až se dostaneme na takovou úroveň, kterou jsme schopni bez problému řešit. V problému třídění se často chceme dostat až k poli velikosti 1, které považujeme automaticky za setříděné.

Merge sort operuje s myšlenkou, že dokážeme velmi rychle a v lineárním čase slít (spojit, anglicky merge) dvě již setříděná pole do jednoho tak, aby výsledné pole bylo opět setříděné. Na začátku samozřejmě máme jen jedno pole a to setříděné není. My si ho však můžeme rekurzivně rozdělit na 2 poloviny, každou polovinu opět rozdělit na další poloviny a tak dále. V nejhlubší hladině rekurze se nutně dostaneme do fáze, kdy nám zbydou už jen samá jednoprvková pole. Jednoprvkové pole můžeme považovat za setříděné, říká se o něm, že je setříděné triviálně. Jak se postupně vynořujeme z rekurze, sléváme tato jednoprvková pole na dvouprvková, ta na čtyřprvková a tak pokračujeme, dokud nám nezbydou dvě velká pole, která když slijeme, dostaneme naše původní pole setříděné. Protože sléváme vždy po rozdělení na poloviny, budeme to jistě dělat log n krát (kde základem logaritmu je 2, protože dělíme na 2 poloviny). Samotné slévání zvládneme v čase O(n), výsledná časová složitost algoritmu tedy bude O(n log n). Nejprve si ukážeme, jak se pole slévají.

Slévání

Mějme 2 pole, která jsou již setříděná:

2 3 5
1 4 7 8

Všimněte si, že pole nemusí mít stejnou velikost. Když budeme v Merge sortu dělit na polovinu pole o velikosti 7, dostaneme přesně takováto pole. Úskalím Merge sortu je fakt, že budeme potřebovat pomocnou paměť, ta bude zatím prázdná.

2 3 5
1 4 7 8

Pomocná paměť:

             

Začneme tedy slévat. V každém poli budeme potřebovat 2 indexy, které budou zpočátku na prvním indexu. Zde budou zobrazeny tučně.

2 3 5
1 4 7 8

Pomocná paměť:

             

Porovnáme prvky na indexech a ten menší prvek vložíme do pomocného pole na pozici, která je součtem indexů. Oba indexy máme nyní na pozici 0 (první pozice), pozice v pomocném poli tedy bude 0 + 0 = 0. Porovnáme a zjistíme, že 1 < 2, vložíme tedy jedničku na pozici 0 do pomocného pole a index u jedničky zvětšíme o 1.

2 3 5
1 4 7 8

Pomocná paměť:

1            

2 < 4, vložíme tedy dvojku na 0 + 1 = 1 a posuneme se s indexem.

2 3 5
1 4 7 8

Pomocná paměť:

1 2          

3 < 4, vložíme 3 na pozici 1 + 1 = 2, posuneme se s indexem.

2 3 5
1 4 7 8

Pomocná paměť:

1 2 3        

Pokračujeme dále...

2 3 5
1 4 7 8

Pomocná paměť:

1 2 3 4      

 

2 3 5
1 4 7 8

Pomocná paměť:

1 2 3 4 5    

Nyní jsme se dostali do fáze, kdy jsme alespoň s jedním indexů již vyjeli z pole. Nyní se podíváme, zda druhý index není ještě v poli (zde je) a dolijeme zbylé prvky.

2 3 5
1 4 7 8

Pomocná paměť:

1 2 3 4 5 7 8

Máme hotovo, výsledné pole je setříděné. V praxi samozřejmě nedostaneme pole už takto připravené na 2 setříděné poloviny, ale pořádně rozházené. Musíme se tedy rekurzí dostat až na jednotková pole a ty poté začít slévat.

Průběh

Průběh označuje následující diagram:

Merge sort - Třídicí/řadicí algoritmy

Možná vylepšení

Kamenem úrazu algoritmu je potřebná pomocná paměť. Když se podíváte na diagram výše, vidíte, co všechno si musí funkce držet v paměti. Mohli bychom ovšem třídit naopak, tedy brát původní pole jako již rozdělené na pole jednotková a ta rovnou slévat na pole velikosti 2, ty pak na pole velikosti 4 a podobně. Pomocné paměti bychom se nezbavili, ale při troše práce by stačilo jen jedno pomocné pole, které by bylo stejně velké, jako pole původní. Do něj bychom si uložili výsledek po slití a potom slévali do pole původního a zas naopak. Přelévali bychom tedy data střídavě mezi těmito poli.

Vizualizace

Video ukázka

Vlastnosti algoritmu

Časová složitost O(n log n)
Stabilita Ano
Rychlost Rychlý

Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům

Zdrojový kód

  • // 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
  • // sliti dvou setridenych poli do jednoho
    function merge(array &$list, array $left, array $right) {
      $i = 0;
      $j = 0;
      // dokud nevyjedeme z jednoho z poli
      while (($i < count($left)) && ($j < count($right))) {
        // 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 < count($left)) {
        while ($i < count($left)) {
          $list[$i + $j] = $left[$i];
          $i++;
        }
      }
      else {
        while ($j < count($right)) {
          $list[$i + $j] = $right[$j];
          $j++;
        }
      }
    }
    
    // samotne trideni
    function merge_sort(array &$list) {
      if (count($list) <= 1) // podmínka rekurze
      return ;
      $center = count($list) / 2; // stred pole
      $left = []; // vytvoreni a naplneni leveho pole
      for ($i = 0; $i < $center; $i++)
        $left[$i] = $list[$i];
      $right = []; // vytvoreni a naplneni praveho pole
      for ($i = $center; $i < count($list); $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
    }
    

V další lekci, Quick sort, si ukážeme algoritmus Quick sort i se zdrojovými kódy.


 

Předchozí článek
Heapsort
Všechny články v sekci
Třídicí/řadicí algoritmy
Přeskočit článek
(nedoporučujeme)
Quick sort
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
60 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity