Osnovni algortimi za rad sa nizovima - drugi deo

Preostalo je da objasnimo

• izdvajanje elemenata niza koji ispunjavaju neki uslov u drugi niz
• pretraživanje niza
• promena redosleda elemenata niza (sortiranje)

IZDVAJANJE elemenata koji ispunjavaju neki uslov u novi niz radimo tako što koristimo posebnu promenljivu za praćenje koliko je elemenata novog niza popunjeno. Na primer, ako želimo da odvojimo pozitivne članove niza a (koji ima na elemenata) u niz b onda to radimo ovako

nb=0;

for(i=0; i<na; i++)

   if(a[i]>0)

   {

      b[nb]=a[i];

      nb++;

   }

Zamenom uslova (a[i]>0) nekim drugim postižemo da se odvajaju drugačiji elementi niza a.

PRETRAŽIVANJE niza ima više varijatni:

• tarženje jednog podatka u datom nizu podataka
• traženje jedog niza (podniza) u drugom nizu  

Traženje jednog podatka se može realizovati proverom svakog elementa (to zovemo linearnim pretraživanjem) ili određivanjem dela sortiranog niza u kome se mora nalaziti zadati element (to zovemo binarnim pretraživanjem).

Linearno je, naravno, sporije ali ne zahteva nikakav poseban niz i može se koristiti ako niz nema mnogo elemenata. Provera da li se u datom nizu a sa na elemenata pojavljuje dati broj x radi se ovako

nadjen=0;
for(i=0; i<na; i++)
   if(a[i]==x)
   {
      nadjen = 1;
      break;
   }

Rezultat: ako posle gornjeg dela programa promenljiva nadjen ima vrednost 0 element nije pronadjen a ako ima vrednost 1  onda je pronadjen.
Sličan postupak može se koristiti i za određivanje pozicije pojavljivanja traženog elemenenta u nizu (umesto "nadjen =1" treba stavitit "nadjen = i"), ili broj pojavljivanja traženog elementa u nizu (umesto "nadjen = 1" treba staviti "nadjen++")

Binarno zahteva da niz bude sortiran rastuće (od manjih ka većim) ili opadajuće (od većih ka manjim) i sastoji se u tome da se traženi element uporedjuje da elementom koji je približno u sredini datog niza. Može se desiti jedna od tri situacije

• traženi element je isti kao taj član niza koji analiziramo => element je pronadjen i postupak se završava
• traženi element je manji od člana niza koji analiziramo => traženje elementa nastavljamo u prvoj polovini niza (ako je sortiran rastuće tj. drugoj ako je sortiran opadajuće)
• traženi element je veći od člana niza koji analiziramo => traženje elementa nastavljamo u drugoj polovini niza (ako je sortiran rastuće tj. prvojoj ako je sortiran opadajuće)

Ako na kraju dođemo do niza koji nema elemenata onda je postupak okončan i element nije pronadjen. Ovakav način je mnogo brži. Program koji traži dati element x binarno u nizu a sa na elemenata (koji je sortiran rastuće) izgleda ovako:

nadjen=0;

pocetak=0;

kraj=na-1;

while(pocetak<=kraj)

{

    sredina=(pocetak+kraj)/2;

    if(a[sredina]==x)

    {

        nadjen=1;

        break;

    }

    if(a[sredina]<x)

        pocetak=sredina+1;

    else

        kraj=sredina-1;

}

Traženje jednog niza u drugom je komplikovanije naročito ako su nizovi dugački (zbog velikog broja provera koje treba obaviti da bi se došlo do rešenja). Klasično rešenje: ako tražimo niz b u nizu a onda tražimo prvo slovo od b u a pa kada ga nadjemo pokušavamo da nađemo i ostala. Ako uspemo - postupak je završen. Ako ne uspemo tražimo sledeću pojavu prvog slova b u a... Ako stignemo do kraja a onda niz b nije pronadjen. Rezultat je pozija u a na kojoj je nadjen niz b. Program koji koristi ovaj algoritam izgleda ovako:


for(i=0; i<na; i++)
{
   if(a[i]==b[0])
      for(j=1; j<nb; j++)
          if(a[i+j]!=b[j]) break;
      if(j==nb)
          printf("%d", i);
}

Ovaj program može da ima dugo vreme izvršavanja jer se prilikom neuspeha vraća na mesto od kojeg je počeo pa pokušava sa sledećim što je vrlo često nepotrebno. Algoritam KMP (Knut-Moris-Prat) predlaže bolje rešenje - pre traženja konstruisati pomoćni niz (kmpNext) koji sadrži informaciju na kojoj poziciji se nalazi sledeća pojava slova do koga smo stigli. 

Sortiranje ćemo ipak ostaviti za sledeći članak.