Lineáris keresés
Logaritmusos keresés
Logaritmusos keresés
Kereső algoritmusok
Keresést rendezetlen és rendezett tömbökön egyaránt végezhetünk. Rendezetlen tömb esetén a keresés nehézkesebb, lassúbb, de az egyéb tömbkezelő műveletek (pl. új elem beszúrása) egyszerűbbek. Rendezett tömb esetén gyorsabb a keresés, viszont a kapcsolódó tömbműveletek bonyolultabbak, hiszen pl. egy új elem beszúrása után is meg kell tartani a tömb rendezettségét.
Lineáris keresés
A legegyszerűbb keresési algoritmus, amely rendezetlen tömbön dolgozik. A tömb első elemétől kezdve összehasonlítjuk a tömbelemeket a keresendő elemmel. A keresési ciklus akkor ér véget, ha valamelyik tömbelem megegyezik a keresettel, vagy, ha a tömb végére érünk. Az utóbbi esetben a keresett elem nincs a tömbben. Az algoritmus onnan kapta nevét, hogy a keresések száma, és így a futási idő, lineáris függvénye a tömb elemszámának.
Megjegyzés: A n jelöli a számsorozat elemeinek számát, az a[1..n] tömb tárolja a számsorozat elemeit, x a keresett érték. Eredményként a keresett elem tömbbeli indexét írassuk ki, amennyiben az elem megtalálható.
i := 1;
while (i ≤ n) AND (a[i] ≠ x) do
i := i + 1;
endwhile
if i ≤ n then write i
else write "A keresett szám nem található meg a számsorozatban."
endif.
Logaritmikus (bináris) keresés
A logaritmikus vagy bináris keresési algoritmus rendezett tömbön működik, így az előző módszernél lényegesen gyorsabb keresést tesz lehetővé. A keresendő elemet először a tömb középső eleméhez hasonlítjuk. Ha a két elem egyezik, megtaláltuk a tömbelemet, ha nem, a keresést abban a tömbfélben folytatjuk, amelyet a középső és a keresett elem viszonya kijelöl. Ha a tömb növekvő sorrendbe rendezett és a keresendő elem nagyobb, mint a középső elem, akkor a második tömbrészben, egyébként pedig az elsőben folytatjuk a keresést. A keresést akkor fejezzük be, ha megtaláltuk a keresett tömbelemet, vagy a tömbrész elfogyott. Az összehasonlítások száma, s így a futási idő, az elemszám kettesalapú logaritmusával arányos, ami nagy elemszámok esetén lényegesen kisebb lehet, mint a lineáris keresés esetén.
Megjegyzés: A n jelöli a számsorozat elemeinek számát, az a[1..n] tömb tárolja a számsorozat elemeit, x a keresett érték. Eredményként a keresett elem tömbbeli indexét írassuk ki, amennyiben az elem megtalálható.
eleje := 1;
vége := n;
repeat
közepe := (eleje + vége) / 2;
if x < a[közepe] then vége := közepe – 1
else if x > a[közepe] then eleje := közepe + 1
endif
endif
until (x = a[közepe]) OR (eleje > vége);
if x = a[közepe] then write közepe
else write "A keresett szám nem található meg a számsorozatban."
endif.
Rendező algoritmusok
Beszúrás
Van egy n elemű rendezett tömbünk. Be akarunk szúrni egy n+1-edik elemet a rendezettség megtartásával. Egyik lehetőség, hogy végigszaladunk a halmazon, és betesszük a beszúrandó elemet az elé az elem elé, ami már nem előzi meg. Átlagosan (n+1)/2, de a legrosszabb esetben n összehasonlításra van szükség. Másik lehetőség, hogy a kérdéses elemet a középső elemmel hasonlítjuk össze. Ha az új elem megelőzi a középsőt, akkor a továbbiakban a halmaz első felében keressük a helyét, stb. A lépésszám log2n, vagy az erre következő első egész szám, azaz [log2n]+1, ha n nem 2 hatványa.
Megjegyzés: A n jelöli a számsorozat elemeinek számát, az a[1..n] tömb tárolja a számsorozat elemeit, x a beszúrandó érték. A kereséséhez a logaritmikus algoritmust használjuk.
eleje := 1;
vége := n;
repeat
közepe := (eleje + vége) / 2;
if x < a[közepe] then vége := közepe – 1
else if x > a[közepe] then eleje := közepe + 1
endif
endif
until (x = a[közepe]) OR (eleje > vége);
if x ≤ a[közepe] then helye := közepe;
else helye := közepe + 1;
endif
for i := n downto helye do
a[i+1] := a[i];
endfor
a[helye] := x.
Beszúrásos rendezés
A rendezés során sorrendbeli hibát keresünk egy tömbben. Ennek során használhatunk lineáris, illetve bináris keresést. A kialakult sorrendtől eltérő helyen levő elemet kiemeljük, majd megkeressük a sorrendnek megfelelő helyét. Amikor a helyét megtaláltuk, akkor a közbeeső elemeket eltoljuk, majd az imént kiemelt elemet a felszabaduló helyre beszúrjuk. Ez a rendezés túl sok mozgatást igényel.
Megjegyzés: A n jelöli a számsorozat hosszát, az a[1..n] tömb tárolja a számsorozat elemeit.
for i := 2 to n do
x := a[i];
eleje := 1;
vége := i - 1;
repeat
közepe := (eleje + vége) / 2;
if x < a[közepe] then vége := közepe – 1
else if x > a[közepe] then eleje := közepe + 1
endif
endif
until (x = a[közepe]) OR (eleje > vége);
if x ≤ a[közepe] then helye := közepe;
else helye := közepe + 1;
endif
for j := i-1, helye downto
a[j+1] := a[j];
endfor
a[helye] := x;
endfor.
Shell rendezés
A beszúrásos módszer lépésenként finomított változata. A tömbnek csak minden d-edik elemét vizsgáljuk, azaz d lépésközzel végezzük el a beszúrásos rendezést. Ha a rendezettség nem alakul ki, akkor csökkentjük a lépésközt, és úgy végezzük el a rendezést. A folyamat addig tart, amíg a rendezettség ki nem alakul, vagy a lépésköz 1 nem lesz.
Megjegyzés: A n jelöli a számsorozat hosszát, az a[1..n] tömb tárolja a számsorozat elemeit. A belső whileciklus lineáris beszúrást alkalmaz.
d := n / 2;
while d ≥ 1 do
for j := d + 1 to n do
i := j – d;
while (i ≥ 1) AND (a[i+d] < a[i]) do
c := a[i];
a[i] := a[i+d];
a[i+d] := c;
i := i – d;
endwhile
endfor
d := d / 2;
endwhile.
Rendezés közvetlen kiválasztással és cserével (minimum [maximum] elven alapuló rendezés)
Egy adott résztömbben (kezdetben a teljes tömb) megkeressük a legkisebb (legnagyobb) elemet, és ezt tesszük az első helyre. A következő lépésben a második elemtől kezdve vizsgáljuk és ismét a legkisebb (legnagyobb) elemet visszük előre, és így tovább. A mindenkori legkisebb elem keresése lineáris kereséssel történik.
Megjegyzés: A n jelöli a számsorozat hosszát, az a[1..n] tömb tárolja a számsorozat elemeit.
for i := 1 to n-1 do
min_index := i;
for j := i+1 to n do
if a[j] < a[min_index] then
min_index := j;
endif
endfor
c := a[i];
a[i] := a[min_index];
a[min_index] := c;
endfor
Buborékrendezés
Az egyik leggyakrabban használt rendező algoritmus. A rendezés a tömb elejéről és végéről is indulhat. Az a[1..n] tömböt legrosszabb esetben (n-1)-szer kell bejárni. A tömb elejéről induló esetben az első bejárásban összehasonlítjuk az a[1]-t az a[2]-vel, majd az a[2]-t az a[3]-mal, …, végül az a[n-1]-et az a[n]-nel. Általánosan az a[j]-t hasinlítjuk az a[j+1]-gyel, ahol j = 1, 2 … , n-1. Valahányszor úgy találjuk, hogy a[j] > a[j+1], felcseréljük őket. A tömb elejéről induló rendezésnél a legnagyobb elem biztosan a helyére fog kerülni. A többi elem azonban még nem feltétlenül került a végleges helyére. (A tömb végéről induló rendezésnél mindig a legkisebb elem kerül biztosan az adott rendezési ciklusban a helyére.) A következő bejárásokban hasonlóképpen járunk el, és további elemek kerülnek a helyükre, ahhoz hasonlóan, ahogy a levegőbuborékok szoktak feljönni a víz felszínére. A rendezést folytatni kell mindaddig, míg a teljes tömb rendezett nem lesz. Előfordulhat, hogy a tömb már menet közben, a rendezési ciklus vége előtt, rendezetté válik, esetleg eleve rendezett volt. Ezt onnan vehetjük észre, hogy az adott rendezési ciklusban nem történik csere. Ha megjegyezzük az utolsó csere helyét (ucs), akkor a következő bejárás csak addig megy.
u := n;
repeat
ucs := 0;
for j := 1 to u-1 do
if a[j] > a[j+1] then
c := a[j];
a[j] := a[j+1];
a[j+1] := c;
ucs = j;
endif
endfor
u := ucs;
until ucs=0.
Összefésülés
Van két rendezett tömbünk, a[1..n] és b[1..m]. Ezeket kell összefésülni egy c[1..n+m] tömbbe. Az i változó az a tömb, a j pedig a b tömb elemein fog lépegetni. Az a[i] és b[j] elemek közül mindig a kisebbiket tesszük a ctömbbe, majd lepünk egyet abban a tömbben, amelyből „kikerült" az az elem, amelyet a c tömbbe helyeztünk.
i := 1;
j := 1;
k := 1;
while (i ≤ n) AND (j ≤ m) do
if a[i] ≤ b[j] then
c[k] := a[i];
i := i + 1;
k := k + 1;
else
c[k] := b[j];
j := j + 1;
k := k + 1;
endif
endwhile
while i ≤ n do
c[k] := a[i];
i := i + 1;
k := k + 1;
endwhile
while j ≤ m do
c[k] := b[j];
j := j + 1;
k := k + 1;
endwhile.
Összefésüléses rendezés
Az eddig ismertetett rendező algoritmusoktól eltérő, rekurzív elven működik. A c[1..n] tömb rendezése rekurzívan visszavezethető a c[1..n/2] és a c[n/2+1..n] tömbszakaszok külön-külön történő rendezésére, és az ezt követő összefésülésükre. Az általános rendez eljárást egy c[i..j] tömbszakasz rendezésére kell megírnunk. A feladat akkor triviális, ha a rendezendő tömbszakasz egyelemű (i = j).
Megjegyzés: A rendez eljárást kezdetben a teljes tömbre hívjuk meg, rendez (c[1..n]);. Az összefésül eljárás az a és b segédtömböket használja.
procedure rendez (c[i..j]);
if i < j then
k := (i + j) / 2;
rendez (c[i..k]);
rendez (c[k+1..j]);
összefésül (c[i..j]);
endif
endprocedure
procedure összefésül (c[i..j])
k := (i + j) / 2;
for p := i to k do
a[p] := c[p];
endfor
for p := k+1 to j do
b[p] := c[p];
endfor
a[k+1] := ∞; b[j+1] := ∞; {strázsák}
ii := i; jj := k+1;
for p := i to j do
if a[ii] < b[jj] then
c[p] := a[ii];
ii := ii + 1;
else
c[p] := b[jj];
jj = jj + 1;
endif
endfor
endprocedure
Szétválogatás (előrendezés)
Az a[1..n] tömb elemeit válogassuk szét „az első eleme szerint” (az első elemnél kisebb elemek előtte, a nagyobbak mögötte legyenek). Egy i, illetve egy j változót a tömb elejére, illetve végére állítunk. Kezdetben az elem, amely szerint a szétválogatás történik (továbbiakban kulcselem), nyilván az i-edik pozícióban van. Miközben i áll, jövünk előre j-vel (magunk mögött hagyva a kulcselemnél nagyobb elemeket), míg nem találunk egy a[j]-t, ami kisebb, mint az a[i]. Felcserélve egymás közt az a[i]-t és az a[j]-t, a kulcselem hátra kerül a j-edik pozícióba, a nála kisebb elem pedig előre az i-edikbe. Ekkor „váltás” történik. Miközben j áll, i-vel megyünk hátrafele (magunk mögött hagyva a kulcselemnél kisebb elemeket), míg nem találunk egy a[i]–t, ami nagyobb, mint az a[j]. Ismét felcserélve egymás közt az a[i]-t és az a[j]-t, a kulcselem visszakerül az i-edik pozícióba, a nála nagyobb elem pedig hátra a j-edikbe. Most újra j-vel jövünk előre (1. eset), majd ismét i-vel megyünk hátra (2. eset) mindaddig, amíg i és j találkozik. A kulcselem mindig az álló index irányában van, az előre lepegető j a kulcselemnél nagyobb, a hátrafele mozgó i pedig a kulcselemnél kisebb elemeket hagyja maga mögött. A kulcselem a helyét, amelyet a rendezett számsorozatban foglalna el, ott találja meg, ahol találkoznak az i es j indexek.
i := 1; j := n;
eset := 1;
while i < j do
if a[i] ≤ a[j] then
if eset = 1 then j := j – 1
else i := i + 1
endif
else
c := a[i]; a[i] := a[j]; a[j] := c;
if eset = 1 then eset := 2
else eset := 1
endif
endif
endwhile.
Gyorsrendezés (quick-sort)
Ez az algoritmus is rekurzív elven működik. Szétválogatjuk az aktuális tömbszakasz (a[i..j]) elemeit a szakasz első eleme (az a[i] kulcselem) szerint, majd folytatjuk a rendezést a szakasz kulcselem előtti, illetve mögötti elemei rendezésével.
Megjegyzés: A rendez eljárást kezdetben a teljes tömbre hívjuk meg, a szétválogat függvény adja vissza a helyére került kulcselem pozícióját.
procedure rendez (a[i..j])
if i < j then
k := szétválogat (a[i..j]);
rendez (a[i..k-1]);
rendez (a[k+1..j]);
endif
endprocedure
function szétválogat (a[i..j])
ii := i;
jj := j;
üzemmód := 1;
while ii < jj do
if a[ii] ≤ a[jj] then
if üzemmód = 1 then jj := jj – 1
else ii := ii + 1
endif
else
veder=a[ii]; a[ii]=a[jj]; a[jj]=veder;
if üzemmód = 1 then üzemmód := 2
else üzemmód := 1
endif
endif
endwhile
return ii;
endfunction.
