Algoritem za dvojiško vstavljanje

Izboljšava postopka navadnega vstavljanja (Binary insertion):

• mesto za vstavljanje elementa poiščemo z bisekcijo

Algoritem v Javi

public static void binaryinsertion(Element[] a,int atr) //dvojisko vstavljanje
  {
    int i,j,l,r,m;
    Element x;
    for (i=1; i<a.length; ++i)
    {
      x=a[i];
      l=0;
      r=i-1;
      while (l<=r)
      {
        m=(l+r)/2;
        if (x.manjsi(a[m],atr))
          r=m-1;
        else
          l=m+1;
      }
      for (j=i-1; j>=l; --j)
        a[j+1]=a[j];
      a[l]=x;
    }
  }

Primer delovanja

l 

leva meja

r 

desna meja

m 

sredina

 1 2 6|4 5 9 2 3   //4 se primerja
 l m r             //
    lmr
 1 2 4 6|5 9 2 3   //5 se primerja
 l m   r           //
 l   m r           //ker je 5 večja od gre pred m
 1 2 4 5 6|9 2 3   //9 se primerja
 l   m   r         //ker je 9 večja od r se leva meja nastavi na r
        lmr        //ne uspe, ostane na istem mestu
 1 2 4 5 6 9|2 3   //2 se primerja
 l   m     r
lm r
  lmr
 1 2 2 4 5 6 9|3   //3 se primerja
 l     m     r
 l m r
    lmr
 1 2 2 3 4 5 6 9

Analiza časovne kompleksnosti

Število primerjanj

Število premikov

Isto kot pri navadnem vstavljanju.

O(n2)

• število primerjav C : O(n*ln n)
• število premikov M : O(n2)

Povezave

• fejj's log: binary insertion sort