Programozás | Programozás-elmélet » Rendezési algoritmusok

Rendezési algoritmusok 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üksé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 redezé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 redezése: 9 8 7 6 1. 2. 3. 4. I 1 J Tömb indexedik elemének tartalma

1. 2. 3. 4. i+1=2 8 9 7 6 3 7 9 8 6 4 6 9 8 7 3 6 8 9 7 4 6 7 9 8 4 6 7 8 9 2 3 Buborék rendezé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ék rendezé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 (RepeatUntil). A buborék rendezé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; y:=x-y; x:=x-y; x legyen egyenlő 89+90=179 y legyen egyenlő 179-90=89 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 helyetcseré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; 9 8 7 6 1. 2. 3. 4. index:array[1.4] of byte; 4 3 2 1 1. 2. 3. 4. Hivatkozás a legkissebb 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!!!