Merge Sort

Algoritmy Třídění Merge Sort

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

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.

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (3 hlasů) :
4.666674.666674.666674.666674.66667


 


Miniatura
Předchozí článek
Heapsort
Miniatura
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Quick sort

 

 

Komentáře

Avatar
nohandle
Neregistrovaný
Avatar
nohandle:

Kamenem úrazu algoritmu je potřebná pomocná paměť. >> doporučoval bych na okraj zmínit, že je možné manipulovat pouze s pointerem na paměť, kde jsou uloženy hodnoty pole a tak snížit nároky na celkovou paměťovou režii. Otázkou je nakolik chceme používat tento algoritmus v případech kde je pro nás pamět limitujícím faktorem.

 
Odpovědět 21.10.2011 14:41
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na nohandle
David Čápka:

To je přeci jedno, jestli použijete referenční nebo hodnotový typ, jen přesouváte paměťový problém ze stacku do haldy, ale té paměti bude potřeba stále stejně. To jak je paměť spravována je vlastností jazyka, ne algoritmu. Algoritmus jí vyžaduje stále stejně bez ohledu na to, kam si ji uložím nebo jak se na ni odkazuji.

Odpovědět 21.10.2011 19:01
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Martin
Neregistrovaný
Avatar
Martin:

Mám takový menší dotaz :)
Neměl by být na obrázku ta poslední větem už setřízená ? :D

 
Odpovědět 21.7.2012 15:40
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Martin
David Čápka:

Jo, samozřejmě :) Díky, opravil jsem.

Odpovědět 21.7.2012 17:04
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Petr Nymsa
Redaktor
Avatar
Petr Nymsa:

David Čápka Máš tu menší problém s přetekáním (Chrome)

Odpovědět 25.11.2013 19:50
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovědět 25.11.2013 20:03
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
xxx
Člen
Avatar
xxx:

nie je v tom obrazku chyba (Prubeh)? lebo pole je 5295318 a potom ked sa deli tak je ze 592 a nie 529, druha cast je ok 5318
inak skvele tutorialy k algoritmom, tie videa sa mi moc pacia :)

Odpovědět 26.4.2014 17:12
kto chce hlada sposoby, kto nechce hlada dovody...
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.