ALTE DOCUMENTE |
-Algoritmusok a programban:
A következő algoritmusok megtalálhatóak a programban. Mindegyik a rendezési algoritmusok közé tartozik, amelyekkel elsősorban az adatok közti keresést lehet le egyszerűsíteni. Mindegyikhez tartozik egy rövid magyarázat, forráskód és tesztelés:
.Csökkenő menetszámú rendezés
A módszer lényege, hogy az első elemhez hasonlítja az összes többi elemet, és ha szük 16516v216q séges cserét hajt végre. A külső ciklus indexeli az aktuális első elemet, a belső ciklusváltozó a többi elemet. A belső ciklus első teljes lefutása után az első elem a helyére kerül, így ez kimarad a további hasonlításból.
A külső ciklusváltozó kezdőértéke az első elem indexe, végsőértéke a rendezendő elemek száma -1 (az első elemtől az utolsó előttiig indexeli az elemeket).
A belső ciklusváltozó kezdőértéke a külső ciklusváltozó értéke +1, végsőértéke a rendezendő elemek száma.
4 elemű tömb rendezése (programrészlet):
for i:=1 to 3 do
begin
for j:=i+1 to 4 do
begin
if tomb[i]>tomb[j] then
begin
cs:=tomb[i];
tomb[i]:=tomb[j];
tomb[j]:=cs;
end;
end;
end
Száraz tesztelés:
4 elemű tömb rendezése:
|
I |
J |
Tömb indexedik elemének tartalma |
|||
|
i+1=2 | |||||
|
| |||||
. Buborékrendezés
A módszer lényege, hogy két szomszédos elemet hasonlít egymáshoz. A rendezés megvalósításához két egymásba ágyazott ciklusra van szükség.
A külső ciklus a végrehajtásokat számolja. A ciklusváltozó kezdőértéke 1, végsőértéke a rendezendő elemek száma -1.
A belső ciklus ciklusváltozóját a tömb elemeinek indexelésére használjuk.
Kezdőértéke, és végsőértéke megegyezik a külső ciklusváltozóéval.
A belső ciklus első lefutása után az utolsó elem a helyére kerül, de ez a módszer erről a tényről nem vesz tudomást, a helyére került elemeket is hasonlítja a további lefutások alkalmával (ez a módszer hátránya).
A buborékrendezés 4 elemű tömbnél:
for i:=1 to 3 do
begin
for j:=1 to 3 do
begin
if tomb[j]>tomb[j+1] then
begin
cs:=tomb[j];
tomb[j]:=tomb[j+1];
tomb[j+1]:=cs;
end;
end;
end
Előfordulhat, hogy a tömb elemei hamarabb kerülnek a helyes sorrendbe, mint ahogy a külső ciklus végértékéhez érne, ezért egy kapcsoló használatával ellenőrizhetjük, hogy az elemek helyes sorrendben vannak-e, és ha igen, akkor a rendezést befejezzük. Mivel a kapcsoló tájékoztat minket a rendezés sikerességéről, ezért a külső határozott menetszámú ciklust (For ciklus), lecserélhetjük egy feltétel ciklusra.
A rendezési algoritmusnak egyszer mindenképpen le kell futnia (még akkor is ha már rendezett a tömb, és cserére nincs szükség), ezért használhatjuk a hátultesztelő ciklust (Repeat-Until).
A buborékrendezés 4 elemű tömbnél kapcsolóval (programrészlet):
repeat
kapcs:=true
for j:=1 to 3 do
begin
if tomb[j]>tomb[j+1] then
begin
cs:=tomb[j];
tomb[j]:=tomb[j+1];
tomb[j+1]:=cs;
kapcs:=false;
end;
end;
until kapcs=true;
.Két elem cseréje csereterület nélkül
Csak numerikus adatoknál lehet alkalmazni, és ott is csak akkor ha biztosan tudjuk, hogy a két legnagyobb elem összege nem nagyobb a memóriában lefoglalt tárterület méreténél (különben túlcsordulás jöhet létre).
Pl. két lottószámot megtudunk cserélni csereterület nélkül, ha mondjuk byte típusú változóban tároljuk. A lottószámok 1-90-ig vannak, így a két legnagyobb szám összege 179 (89+90), byte típuson pedig 0-255-ig tárolhatunk számokat.
Cseréljük ki a két számot:
x változó értéke: 89
y változó értéke: 90
x:=x+y; x legyen egyenlő 89+90=179
y:=x-y y legyen egyenlő 179-90=89
x:=x-y x legyen egyenlő 179-89=90
.Logikai rendezés
Logikai rendezést akkor használunk, ha az eredeti (rendezés előtti) sorrendet valami miatt meg akarjuk tartani rendezés után is.
Az előző két rendezésnél a csere folyamán a memóriában ténylegesen helyet cserélt a két elem. A logikai rendezésnél a tömb elemei a helyükön maradnak, a csere egy másik úgynevezett indextömbben történik, ami a rendezetlen tömb indexeinek számait tárolja.
Példa egy logikailag rendezett 4 elemű tömbre.
t:array[1..4] of byte;
index:array[1..4] of byte;
Hivatkozás a legkisebb elemre (6): t[index[1]] tehát, ha a rendezés során cserét akarunk végrehajtani, akkor a cserét nem a t tömbben , hanem az index tömbben végezzük el, és azon keresztül hivatkozhatunk a t tömb elemeire.
Cserét, függvénybe (Function) soha ne írjunk, csak eljárásba (Procedure), mert a függvény egy értéket ad vissza, nekünk pedig két értékre van szükségünk!!!
Ha az egész rendezést egy blokkba írjuk, akkor is csak eljárást szabad használni, mert a függvény típusának csak sorszámozott (byte, char, integer, boolean, stb.), valós (real) és string típust adhatunk meg, strukturált adattípusokat (tömb, record) nem!!!
|
