Binarna pretraga

Formulacija problema: Neka je dato n elemenata v[0],v[1],..,v[n-1] takvih da v[0] <= v[1] <=... <=v[n-1].
Za zadati element x ustanoviti da li se on pojavljuje u nizu v.

Rešenje:

0 <= i <= n-1, tako da v[i]=x (ako je ustanovljeno da se x pojavljuje u nizu v)

ilustracija koraka binarne pretrage

void bsearch(const void key, const void base, size_t n, size_t size, int (cmp)(const void , const void ))

Funkcija bsearch pretražuje base[0]...base[n-1] ne bi li našla element jednak sa *key. Funkcija cmp mora vratiti:

negativnu vrednost, ako je njen prvi argument (kljuc pretrage) manji od drugog agumenta
nulu, ako su jednaki prvi i drugi argument
pozitivnu vrednost, ako je prvi argument veci.

Funkcija poređenja dobija pokazivače na elemente. Svi pokazivači su deklarisani kao void * i moraju se ponovo konvertovati u svoj pravi tip (kao u primeru). Funkcija bsearch vraca pokazivač na prvi element jednak sa *key, ili NULL ako on ne postoji.


int cmp(const void *p1, const void *p2)
{  int i= *(int *)p1; /* vraca ceo broj na koji se pokazuje */
   int j= *(int *)p2;
      return ( i < j ? -1 : (i==j ? 0: 1) );
}

void main()
{
  int dNiz[]={-1, 3, 8, 26, 28, 29, 30, 35, 45};
  int i=30;
  void *p=bsearch(&i, dNiz, 9, sizeof(int), &cmp);
   if (p==NULL) printf("\nnije nadjen\n"); else printf("\nPronadjen je i\n");
}

Postupak linearnog pretraživanja

Traženi element se mogao naći i lineranim (sekvencijalnim) pretraživanjem.
Redom bi se uporedjivali elementi neopadajućeg niza v sa vrednošću od x, sve do prvog elementa v[i] za koji važli v[i] >=x.
Tada, ako je:

v[i] = = x, onda je poz=i tražena pozicija
v[i] > x, onda se x ne nalazi u nizu v

Ako je svaki element niza v manji od vrednosti od x, onda se x ne nalazi u nizu v (izvrsi se n poredjenja).

Odnos broja poredjenja kod linearne i binarne pretrage

odnos asimptotske slozenosti
linearne i binarne pretrage

Takmičenje tri algoritma za sortiranje

Formulacija problema:Zadatih n elemenata a[0],a[1],..,a[n-1] urediti u neopadajući poredak.

Rešenje: niz različitih indeksa 0<=i₁,i₂,..., i_n <=n-1 tako da vazi: a[i₁] <= a[i₂] <=... <=a[i_n]

 Bubble sort        Selection sort      Quick sort

Sortiranje (uredjivanje) niza podataka ne mora da se obavlja samo nad podacima numerickog tipa, već se mogu sortirati i niske, datumi, ...
Poredak sortiranja može biti strogo rastući, neopadajući, strogo opadajući, nerastući.
Poznat je veći broj algoritama za sortiranje. Oni se među sobom razlikuju po složenosti, efikasnosti, potrebama za memorijskim prostorom. Ako algoritam za sortiranje ne koristi dodatni memorijski prostor (sem prostora u koji je smešten niz), onda je to tzv. algoritam sortiranja u mestu.

Izvorni kôd

Selection sort
Bubble sort
Quick sort Pr1 Pr2

Funkcija qsort iz zaglavlja

void qsort (void *niz, size_t broj, size_t velicina, int (poredi) (const void *, const void *) )

Na početak niza koji se soritira pokazuje niz, broj je broj elemenata, velicina je veličina svakog elementa u bajtovima. Argument poredi je adresa funkcije za poređenje koja vraća negativan broj, nulu ili pozitivan broj zavosno da li je prva vrednost na koju se pokazuje manja, jednaka ili veća od druge vrednosti. Funkcija dobija pokazivače na elemente. Pokazivači su deklarisani kao void * da bi ponovo bili u f-ji konvertovani u pravi tip.
Primer koji sledi sortira niz celih brojeva. Funkcija cmp radi sa pokazivačima tipa int * koji se prosleđuju kao da su tipa void *. Potom se u f-ji konvertuju u tip int *, a potom derefenciraju da bi se radilo sa celobrojnim vrednostima i, j.

int cmp(const void *p1, const void *p2)
{  int i= *(int *)p1; /* vraca ceo broj na koji se pokazuje */
   int j= *(int *)p2;
      return ( i < j ? -1 : (i==j ? 0: 1) );
}

void main()
{
  int i, dNiz[]={-1, 3,-8, 26, -28, 29, -30, 35, -45};
   qsort(dNiz, 9, sizeof(int), &cmp);
   for (i=0; i < 9; i++) printf("%d  ", dNiz[i]);
}

Ako se sortira niz stringova, onda svaki eement je sam po sebi pokazivač tipa char *, te f-ja cmp tada prima podatke tipa char ** koji se konvertuju u svoj tip i derefenciraju radi dobijanja podataka tipa char *. Na primer

int cmp(const void *p1, const void *p2)
{  char *s1= *(char **)p1;  /* p1 je pokazivac na element niza stringova, tj. tipa char **, 
a f-ja cmp  mora da radi sa podatkom tipa char * tj. f-ja strcmp */
   char *s2= *(char **)p2;
      return ( strcmp (s1,s2) );
}