|
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. |
|