Algoritmai

-1-

PAIEŠKA PAPRASTAME SĄRAŠE

1.1. Nuosekli paieška

Tegu įrašai išdėstyti atsitiktinai kaip buvo įrašyti. Reikia surasti duotą įrašą pagal raktą. Nuosekliai ieškant reikia peržiūrėti visus įrašus nuosekliai.Vid.peržiūrėų įrašų sk. ieškant yra Lap =L/2. Jei įrašo nėra teks peržiūrėti visus įrašus L. Tarkim ieškomo įrašo su tikimybe p0 nėra sąraše, tada vid. peržiūrėtų įrašų sk. Lap=L*p0+i1L (i*pi ); pi=1-p0/L. Ieškant įrašo sutvarkytame faile(įrašai išdėstyti pagal raktą) reikia peržiūrėti iš eilės, todėl vid. peržiūrėtų įrašų sk. tas pats: Lsp=L/2. Jei ieškomo įrašo nėra, tai paieška nutraukiama kai eilinis raktas bus didesnis už užduotą. Atliekant k įrašų paiešką nesutvarkytame faile vid. peržiūrėtų įrašų sk. Lkap = k * L / 2.

1.2. Paieška interpoliavimas

Jei sąrašai surušiuoti ir žinomas pirmo irašo raktas K(1) ir paskutinio K(n) tai galima apskaičiuoti p=X-K(1)/K(n)-K(1). X-ieškomo įrašo raktas.Paiešką pradedam nuo įrašo kurio numeris p*n.

1.3. Binarinė paieška

Naudojama surūšiuotame masyve. Jis dalinamas pusiau ir ieškomas raktas lyginamas su vidurio raktu ir t.t.. Idealus masyvo dydis 2n-1.Jei 31 įrašas reikės 5 žingsnių, kad surasti įrašą 3125-1. Bendru atveju 2n-1-1< N  2n-1. Kai įrašų sk. bet koks, tai naudojami tokie alg.:

-9-

RŪŠIAVIMO ALGORITMAI

K-mačių kortežų rūšiavimas

Tegul mes turime seką A1 A2 … An k-mačių kortežų, t.y., A erdvinis Ai elementas, sudarytas iš ai1 ai2 … aik.Reikia šią seką rušiuoti taip: B1 B2 … Bn, kad visiem i Bi  Bi+1. Rūšiavimas atliekamas k kartų pereinant per duotą seką. Pirmą kartą atliekamas rūšiavimas pagal k-ąją komponentę. Antrą kartą pagal (k-1) komponentę ir t.t. Prėjus pagal i-ąją, turėsim sūrušiuotą seką. Kiekviena skiltis ai j yra nuo 0 iki m-1. Reikia organizuoti m pagalbinių eilių Q(j), kur j  0,…,m-1, kurios iš pradžiu turi buti tuščios. Duomenis A1 A2 … An iš pradžiu surašom i sąrašą EILE. Paimam eilini kortežą Ai iš EILĖS ir patalpinam į pagalbinę eilę Q(j) pagal analizuojamos komponentės reikšmę. Taip darom tol, kol bendra EILĖ ištuštėja. Visi kortežai atsiduria pagalbinėse eilėse. Po to jie suduriami: Q(0) Q(1)…Q(m-1) ir jie sudaro vieną bendrą eilę EILĖ. Kai praeinam pro visas komponentes, tai EILĖ bus surūšiuota. Algoritmo sudėtingumas yra tiesinis [(n+m)/k]. Naudoti šį metodą neverta, kai n yra mažas.

-17-