Metode de sortare – insertie binara (Binary Insertion Sort)

Se deosebeşte de inserţia directă doar prin modul de căutare a poziţiei de inserare. Presupunem că căutăm poziţia de inserare a elementului cu valoarea 20 în secvenţa:
1 4 7 9 10 12 15 18 21 23 26 28 33

0 1 2 3 4 5 6 7 8 9 10 11 12
1 4 7 9 10 12 15 18 21 23 26 28 33
S=0 M=6 D=12

Se calculeaza M=(Standa+Dreapta)/2=(0+12)/2=6

1 4 7 9 10 12 15 18 21 23 26 28 33
S=0 M=6 D=12

a[M]=a[6]=15, 20>15 deci cautam in dreapta, noul interval este S=7, D=12

1 4 7 9 10 12 15 18 21 23 26 28 33
S=7 M=9 D=12

M=(7+12)/2=9, a[9]=23, 20<23 deci cautam in stanga, noul interval este S=6 D=8

1 4 7 9 10 12 15 18 21 23 26 28 33
S=6 M=7 D=8

M=(6+8)/2=7 a[7]=18, 20>18 deci cautam in dreapta, noul interval este S=8, D=8

1 4 7 9 10 12 15 18 21 23 26 28 33
S=M=D=8

M=(8+8)/2=8, a[8]=21, 20<21 deci cautam in stanga, noul interval este S=8, D=7

1 4 7 9 10 12 15 18 21 23 26 28 33

Conform algoritmului ne oprim cand S>D iar pozitia de inserat este S=8; inainte de inserare, elementele a[12] -> a[8] se declara spre dreapta cu o pozitie


#include "stdio.h"
#include "conio.h"
//functie care intoarce pozitie in care trebuie inserat
//a[i] in secventa a[1]...a[i-1]
int insertie_binara(int a[], int i)

{
  int stanga,dreapta,m;
  stanga=0;
  dreapta=i-1;
  while(stanga <=dreapta)   {     //m va fi la mijlocul intervalului     m=(stanga+dreapta)/2;     //a[i] poate fi în a[m+i]...a [dreapta]     if(a[m]a[i])
        dreapta=m-1;
      else
        //a[i] este egal cu a[m] deci poate fi inserat pe poziţia m
        return(m);
  }
  return(stanga);
}

void main(void)
{
  int n,a[100],i,j,elem, index;
  printf("Introdu dim şirului:");
  scanf("%d",&n);
  printf("Intrody elem şirului: \n");
  for(i=0;i= index;j--)
      a[j+i]=a[j];
    a[index]=elem;
  }
  printf("Sirul sortat este:");
  for(i=0;i

Leave a Reply

Your email address will not be published. Required fields are marked *

4 + eleven =

Time limit is exhausted. Please reload CAPTCHA.