Binární vkládání

 

 

Binární vkládání představuje jisté vylepšení přímého vkládání. Jestliže si uvědomíme, že zvolený prvek ukládáme do posloupnosti, která je již setříděná, můžeme zrychlit hledání místa, na které patří. Přitom nebudeme potřebovat zarážku.

Místo pro vkládaný prvek budeme zjišťovat metodou binárního vyhledávání, kterou můžeme považovat za typický příklad algoritmu vytvořeného podle modelu rozděl a panuj: cílovou posloupnost rozdělíme na dvě podposloupnosti a porovnáním zjistíme, do které z nich vkládaný prvek patří. Opakováním tohoto postupu nakonec určíme místo, na které prvek vložíme.

Přesně popíšeme tento algoritmus opět v Pascalu:

procedure BinárníVkládání;

var i,j,k,l,r,m: index;

    x:           prvek;

begin

  for i := 2 to n do begin

    x := a[i];

    l := 1; r := i-1;             {l,r jsou meze podposloupnosti}

    while l <= r do begin                       {binární hledání}

      m := (l+r) div 2;                   {rozdělíme na poloviny}

      if x.klíč < a[m].klíč then r := m-1

      else l := m+1

    end;{while}

    for j := i-1 downto l do a[j+1] := a[j];

    a[l] := x;

  end {for i}

end;

Analýza algoritmu binárního vkládání

Místo, na které uložíme nový prvek, je popsáno podmínkou

a[j].klíč <= x.klíč <= a[j+1].klíč.

Zkoumaný interval délky i přitom musíme rozdělit podle okolností buď [log2i]-krát, kde [z] označuje celou část čísla z, nebo ([log2i]+1)-krát. To znamená, že celkový počet porovnání C bude omezen součty

                               

         

Hodnotu součtu na levé straně můžeme přibližně odhadnout pomocí integrálu:                                

 

      

kde s = log2e = 1/ln 2 = 1,44269... .

Přitom počet porovnání bude prakticky nezávislý na uspořádání prvků zdrojové posloupnosti. Počet přesunů zůstane ovšem v podstatě stejný jako v případě přímého vkládání, odpadnou pouze operace se zarážkou. To znamená, že počet porovnání bude podle (2) jen O(n.log2n), avšak počet přesunů zůstane O(n2). Vzhledem k tomu, že přesuny jsou zpravidla časově náročnější než porovnání, nemusí jít o úsporu nijak významnou.

Zpět


Poslední aktualizace: 29-05-2003.