Algoritmusok Dr. Schuster György, Sándor Tamás,

Algoritmusok Dr. Schuster György, [email protected] Sándor Tamás, [email protected] 1. Algoritmus fogalma Az algoritmus olyan lépéssorozat, amely egy feladat megoldása során véges számú lépésben végeredményre jutunk. Két dolgot kell kiemelni. Az egyik, hogy véges számú lépésben jutunk eredményre. Ez azért lényeges, mert az alkalmazott algoritmust későbbiekben le is kell tudni programozni. A másik lényeges szempont, hogy eredményre jutunk, hiszen készíthetünk olyan lépéssorozatot, amely sem véges, sem végtelen lépésben nem vezet eredményre. Vannak persze olyan feladatok, amelyek nem, vagy csak korlátozott mértékben algoritmizálhatók, de ezen feladatok megoldása már a mesterséges intelligencia témakörébe tartoznak. Az algoritmusnak az alábbi feltételeket kell teljesítenie: • • •

az algoritmust alkotó utasítások legyenek egyértelműek, utasítások gépiesen végrehajthatók, és a megoldás véges számú lépésben megkapható.

Az olyan algoritmust, amelyet egy számítógép végre tud hajtani, programnak nevezzük. A számítógépi program abban különbözik egy neki megfelelő logikai algoritmustól, hogy a programnak nevezett algoritmus szigorú formai előírásokhoz, jelölésrendszerhez kötött. Ilyen lehetséges jelölésrendszer a C programozási nyelv. A feladat kidolgozásában absztrakt objektumokat, absztrakt algoritmus elemeket alkalmazunk. Ez azt jelenti, hogy nem csak a program nyelvekben előre definiált szimbólumokat használjuk fel, hanem saját magunk által definiált jelöléseket is használhatunk az általunk definiált művelet csoportok végrehajtására. Ugyanígy nemcsak a megszokott adatszerkezeteket használhatjuk, hanem létrehozhatunk újakat. Az adatok és eljárások ilyen absztrakciója lehetővé teszi, hogy adatok és eljárások felhasználásakor ne kelljen foglakoznunk az adatok felépítésével, vagy az eljárások műveletelemeivel. Ha az algoritmus elkészítésénél a top-down (felülről lefelé) történő program finomítás elvét alkalmazzuk, akkor az egyes részletek finomítása során az algoritmusainkat egyre pontosabban tudjuk megfogalmazni. A finomításnak a következő elveket célszerű betartani: • • •

adott szint részfeladatainál egyszerre végezzük el az eljárások és az adatok szükséges finomítását, ha valamilyen változtatást végeztünk, vizsgáljuk meg milyen hatása lesz a kapcsolódó eljárások művelet végrehajtására, az adatszerkezeteire. minden változtatást dokumentáljunk, hiszen ha a változtatás nem váltotta be a hozzáfűzött reményeket, akkor legyen lehetőségünk visszatérni a változtatás előtti állapothoz.

1.1. Algoritmus leíró eszközök

Az algoritmus leíró eszközök feladata, az hogy általánosan megfogalmazott feladat megoldási lépéssorozatot programozhatóság szempontjából konkrétan megadjuk. Az algoritmus leíró eszközöknek alapvetően kétfajtáját különböztethetjük meg. Az egyik ilyen módszer a szöveges, a másik a grafikus leírásmód.

1.1.1. Szöveges 1.1.1.1. Szöveges megfogalmazás A szöveges megfogalmazás során saját szavainkkal írjuk le a feladat megoldásának lépéseit. Ekkor külön előre elfogadott szabályokhoz nem kell alkalmazkodni, egyedi leírásmódot választhatunk. 1.1.1.2. Pszeudokód A pszeudokód a beszélt nyelv mondatait alkalmazó olyan utasítás sorozatból áll, amelyek egy-egy részfeladat megoldását jelentik. A pszeudokód olyan mondatszerű leírás, amely alapvetően háromféle vezérlési szerkezetet alkalmaz: • • •

felsorolást (szekvenciát), Esetszétválasztást (szelekciót, kiválasztást), Ismétlést (ciklust, iterációt).

A következőkben felsorolásszerűen megadjuk azokat a legfontosabb mondatszerű szerkezeteket, amelyek segítségével minden programnyelvtől függetlenül írhatjuk le az algoritmusainkat: 1. Beolvasó utasítás Be:[beolvasandó paraméterek jellemzői] INPUT: [beolvasandó paraméterek jellemzői] 2. Kiíró utasítás Ki:[kiíratandó paraméterek jellemzői] OUTPUT:[kiíratandó paraméterek jellemzői] 3. Értékadó utasítás := 4. Feltételes utasítások Ha akkor Feltétel vége

IF THEN Ha akkor egyébként Feltétel vége IF THEN ELSE

Esetszétválasztás <eset 1> esetén <eset 2> esetén .... <eset n> esetén máskülönben Esetszétválasztás vége SWITCH <eset 1> CASE <eset 2> CASE .... <eset n> CASE DEFAULT

Ciklusszervező utasítások Növekményes ciklus: Ciklus ciklusváltozó:=kezdőérték-től végérték-ig lépésköz-zel ciklustörzs utasításai Ciklusvég FOR ciklusváltozó:=kezdőérték TO végérték STEP ciklustörzs utasításai A lépésköz lehet állandó érték, vagy változó nagyságú érték.

Elöltesztelő ciklus: Ciklus amíg ciklustörzs utasításai Ciklus vége

WHILE BEGIN ciklustörzs utasításai END Utántesztelő ciklus: Ciklus ciklustörzs utasításai amíg Ciklus vége REPEAT BEGIN ciklustörzs utasításai END UNTIL

Eljárások Eljárásnév (eljárás bemenő paraméterek) eljárástörzs utasításai Eljárás vége Eljárásnév (eljárás bemenő paraméterek) BEGIN eljárástörzs utasításai END

Programok Program: Programutasítások Program vége Program: Programutasítások Program END Példa pszeudokód alkalmazására Írjuk ki az ASCII kód táblából a kisbetűket egymás után!

Ciklus betu:=’a’ betu<=’z’ lépésköz:=1 Ki:=betu Ciklus vége

1.1.2. Grafikus 1.1.2.1. Folyamatábra A folyamatábra esetén az egyes algoritmuslépésekhez egy-egy grafikus megjelenítő egységet lehet hozzárendelni. Az egyes elemek jelentése az alábbiakban kerül ismertetésre.

Lineáris program

Elágazások Kétirányú elágazás

Többirányú elágazás

Ciklusok Elöltesztelő ciklusok

Utántesztelő ciklusok

Számszerű végrehajtás i: ciklus számláló

1.1.1. N:

Program modul (szubrutin)

Beviteli és kiviteli eszközök

A folyamatábra lehet részletező, amikor egyes lépéseket külön folyamatábra elemként kerül megadásra, míg lehet áttekintő folyamatábrát is készíteni. Az áttekintő folyamatábrákat több szinten, hierarchikusan is megjeleníthetjük, azaz az egyes részproblémákat további részproblémákra bonthatjuk, egészen addig, amíg a részletező folyamatábrához nem jutunk.

1.1.2.2. Struktogram Feldolgozási utasítás

Egyszeri elágazás

Többszörös elágazás

Programhurok elővizsgálattal

Programhurok utóvizsgálattal

Hurok, hurkon belüli megszakítási feltétellel

A fenti hat alapelemből összetett stutúrablokkok állíthatók elő. Az elkészült programterv általában több egymással alá, vagy felérendeltségi viszonyból áll. Ezeket a kapcsolatokat fadiagrammal ábrázolják. A kötelezően előírt a pontosan egy be- és pontosan egy kimenet, valamint az az előírás, hogy az alárendelt struktúrablokkokat csak a fölérendeltségi viszonyon keresztül lehet megközelíteni, biztosítva a program áttekinthetőségét, módosíthatóságát, és az egyes modulok külön-külön tesztelhetőségét.

1.1.2.3. Állapotgráf A gráf csúcsok (csomópontok) és élek halmazából áll. Gráfot kapunk, amikor megadjuk a különféle tárgyaknak (dolgoknak), és a tárgyak közötti kapcsolatoknak a halmazait. A gráfban a dolgokat a csúcsok, a dolgok közötti kapcsolatokat az élek írják le.

2. Algoritmusok fajtái

2.1. Tömbáthelyező algoritmus A tömbáthelyezés az egyik legegyszerűbb algoritmus. A memóriában elhelyezkedő adott hosszúságú tömböt mozgatjuk egy másik, rendelkezésre álló memória területre. A tömb kétféleképpen lehet definiálva, vagy megadjuk a hosszát, vagy a tömbben van egy speciális lezáró elem. Például ilyen elem lehet a pozitív egészeket tartalmazó többen a nullaértékű elem. A kérdés az, hogy hogyan helyezhetjük át kérdéses tömbünket egy másik tömbbe. Erre is két lehetőség van. Végezhetjük a műveletet a töm elejétől a vége felé növekvő index értékek mellett és végezhetjük fordított irányban a legmagasabb indextől a legkisebb felé. Mondhatnánk azt, hogy teljesen fölösleges két algoritmust gyártani, ha a kettő azonos eredménnyel jár. Ez a kijelentés az esetek nagytöbbségében igaz, azonban van két speciális eset, mikor nem mindegy, hogy az áthelyezés milyen irányba történik. Amennyiben a tömbáthelyezés nem a fent említett két eset valamelyike általában növekvő indexek felé haladva végezzük a műveletet. Nézzük meg ezt egy példán. X X(I) Y Y(I) N I 1. 2. 3. 4. 5. 6.

a forrás tömb neve, az X tömb I-edik eleme, a cél tömb neve, az Y tömb I-edik eleme, a tömb elemeinek száma, indexváltozó (külső index),

BEGIN tömbáthelyezés FOR I:=0 Ilezáró elem 4. BEGIN 5. Y(I):=X(I); 6. I:=I+1; 7. END; 8. END. Itt nem tudjuk a tömb hosszát, így folyamatosan figyelni kell a lezáró elemet, és miután nem alkalmazhattunk számláló jellegű ciklust (FOR-t), ezért az I kezdeti értékét be kellett állítanunk. Lásd 2. sor. Ez a fajta tömbáthelyezés nem alkalmas a csökkenő indexű mozgatásra, mert nem tudjuk, hogy hol a tömb eleje. Amennyiben az az eset áll fent, hogy a mozgatandó tömbünk belelóg a cél tömb területébe, problémák adódnak. Nézzük a következő példát: adott egy tízelemű tömbünk, amelyet egy elemmel jobbra (növekvő index irányba szeretnénk mozgatni úgy, hogy az alacsony indexektől kezdjük az áthelyezést.

X(0) 1

X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) 2 3 4 5 6 7 8 9 0 üres Y(0) Y(1) Y(2) Y(3) Y(4) Y(5) Y(6) Y(7) Y(8) Y(9) Az első lépésnél fogjuk az X 0-ás indexű elemét és betesszük az Y 0-ás indexű elemébe, amely nem más, mint az X 1-es indexű eleme. X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) 1 3 4 5 6 7 8 9 0 üres 1 Y(0) Y(1) Y(2) Y(3) Y(4) Y(5) Y(6) Y(7) Y(8) Y(9) A második lépésben az X 1-es indexű elemét tesszük be az Y egyes indexű elemébe, amely megegyezik az X 2-es elemével Igen, de miután az X 1-es indexű eleme már megegyezik az X 0-ás elemével az X 2-es eleme is meg fog egyezni az X 0-as elemével. Könnyen belátható, hogy az algoritmus végén az összes érintett elem felveszi az X 0-ás elemének értékét. Így az algoritmus nem helyes. A megoldás, hogy nem növekvő, hanem csökkenő index irányokban mozgassuk a tömböt. X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) 1 2 3 4 5 6 7 8 9 Üres 0 Y(0) Y(1) Y(2) Y(3) Y(4) Y(5) Y(6) Y(7) Y(8) Y(9) Az első lépésnél a 9-es elemeket mozgatjuk át. X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) 1 2 3 4 5 6 7 8 0 0 9 Y(0) Y(1) Y(2) Y(3) Y(4) Y(5) Y(6) Y(7) Y(8) Y(9) Majd a 8-ast. X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) 1 2 3 4 5 6 7 9 9 0 8 Y(0) Y(1) Y(2) Y(3) Y(4) Y(5) Y(6) Y(7) Y(8) Y(9) Majd a hetest. X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) 1 2 3 4 5 6 8 8 9 0 7 Y(0) Y(1) Y(2) Y(3) Y(4) Y(5) Y(6) Y(7) Y(8) Y(9) Az algoritmus végén a következő képet kapjuk: X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) 1 1 2 3 4 5 6 7 8 9 0 Y(0) Y(1) Y(2) Y(3) Y(4) Y(5) Y(6) Y(7) Y(8) Y(9) Igaz, hogy az X tömb megsérült, de ez ebben az esetben nem kerülhető ki, azonban adatvesztés nem történt. Hasonló a helyzet, ha az X tömb jobbra esik az Y tömbtől és az adatmozgatás csökkenő indexek felé történik, ebben az esetben az előző példa alapján belátható, hogy az adatáthelyezés helyes módja az, ha növeljük az indexeket. Ökölszabály: Ha a forrás és a cél tömbök egymást átfedik, akkor az átfedés (adatmozgatás) irányával ellentétesnek kell lennie az indexváltoztatás irányának. Vagyis: • Ha a céltömb előrébb van, mint a forrás, akkor növekvő indexekkel kel dolgoznunk. • Ha a céltömb hátrébb van, mint a forrás, akkor csökkenő indexeket kell alkalmaznunk. 2.2. Csere algoritmus

A legegyszerűbb algoritmus, amely minden további rendező algoritmus alapja az úgynevezett csere algoritmus. Ez tulajdonképpen egy nagyon egyszerű aprócska művelet, melynek az a célja, hogy két különböző változóban lévő értéket megcseréljen. A probléma annyira egyszerű, hogy az mondhatjuk, hogy tulajdonképpen kár rá szót vesztegetni. Sajnos a tapasztalat azt mutatja, mégis megéri. Tegyük fel, hogy van két változónk, legyenek ezek a és b legyen a értéke 5, b értéke 6, a cél, hogy a-ban legyen 6 és b-ben 5. Mondhatnánk azt, hogy a-nak adjuk át b értékét és b-nek a értékét. Ez a szokásos programozási nyelveken nem valósítható egy lépésben1, hanem legalább két programsort igényel. Ekkor viszont az első lépésben a már felveszi a b értékét, amit a fordított értékadásnál csak visszaadhatunk b-nek és a eredeti értéke elvész. A problémát úgy oldhatjuk meg, hogy egy segédváltozót használunk, - nevezzük c-nek -, és első lépésként ebbe a c változóba tesszük be a értékét, - ez az érték már „biztonságban van”. A következő lépésben a-ba tesszük b értékét, így a csere első fele megvalósult. A harmadik lépésben b-be tesszük c értékét, amely ugye a eredeti értékét tartalmazta, így a telje csere megtörtént. Nézzük ezt matematikai írásmódban is: 1. c:=a; Az a eredeti értéke az átmeneti c változóba kerül. 2. a:=b; A b értéke átkerül a-ba. 3. b:=c; A c, vagyis az átmeneti változó értéke átkerül b-be. A cserét a következőkben a következő szimbólummal jelöljük:  2.3. Rendező algoritmusok A rendező algoritmusok rendezetlen tömbök valamilyen módon történő rendezésére szolgálnak. A mód lehet növekvő és csökkenő sorrend. Mint azt az előző fejezetben már elmondtuk a rendezés alapja a csere algoritmus. Cserét akkor hajtunk végre, ha az éppen aktuális két vizsgált elem nem felel meg a rendezés módjának. Azért, hogy ne kelljen két folyamatábrát, illetőleg algoritmust leírnunk a növekvő és csökkenő sorrendű rendezésre, bevezetünk egy jelölést. Ez a jelölés csak a kisebb és nagyobb relációkra igaz. A jelölés a következő: Ha ezt a jelet látjuk egy relációs kifejezésben, akkor a a>b kifejezés akkor igaz, ha az éppen aktuális reláció teljesül.

a
Érthetőbben a két lehetőség közül ez akkor igaz, ha kisebb esetben a < b, a nagyobb esetben a > b. Ez a fentivel ellentétes eset, a kifejezés akkor igaz, ha a reláció nem teljesül.

A félreértések elkerülése végett meg kell jegyeznünk, hogy ilyen műveleti jel nem létezik, csak mi vezettük be, hogy a leírást egyszerűsítsük. 2.3.1. Egyszerű buborékrendezés Az egyszerű buborékrendezés a rendezések közül a legegyszerűbb. Működése az egymást követő elemek összehasonlításán és cseréjén alapul. 1 Itt kellmegjegyeznünk, hogy ez az assembly nyelvekre nem vonatkozik. Nagy többségükben létezik elemi csere utasítás.

Vegyünk példának egy hatelemű tömböt, amely véletlenszerűen fel van töltve számokkal. A tömb: 5 4 6 1 3 9 A példánkban a rendezés növekvő-sorrendű lesz. Az algoritmus veszi az első elemet és összehasonlítja a következővel, jelen esetben az 5-öt a 4-el, miután az összehasonlítás eredménye nem kedvező cserét hajt végre. 6 1 3 9 5 4 4 1 3 9 5 6 A következő összehasonlítás az 5 és a hat között történik meg, itt az eredmény kedvező, nem történik csere 4 5 3 9 6 1 4 5 1 9 6 3 4 5 1 3 6 9 Az eredmény az első menet után: 4 5 1 3 6 9 Mint látjuk az algoritmus egyszer végigment a tömbön, de a tömb még nem rendezett, tehát a rendezést tovább kell folytatni.2 4 5 4 5 4 1 4 1 4 1 Az eredmény a második menet után:

1 1 5 3 3

3 3 3 5 5

6 6 6 6 6

9 9 9 9 9

4 1 3 5 6 9 Láthatjuk, hogy még mindig nem vagyunk készen. A kérdés az, hogy hányszor kell ezt megtennünk, hogy a tömb teljesen rendezett legyen? A válaszhoz a legrosszabb esetet kell figyelembe vennünk, ez az az eset, ha tömb nem véletlenszerűen rendezetlen, hanem ha fordított módon rendezett, mint a számunkra kedvező rendezés. Az előzőekben láthattuk, hogy a már a tömb első rendezésekor a legnagyobb (növekvő sorrendű rendezés esetén) elem kikerül a tömb végére, a következő “körben” ez elé az elem elé kerül a második legnagyobb és így tovább. Miután a legkisebb elemet már nincs értelme összehasonlítani a senkivel, mert egyedül van, ezért a tömb rendezéseinek maximális száma a tömb elemeinek a számánál egyel kevesebb. Most már megírhatjuk az algoritmust pszeudo nyelven. A kiindulási paraméterek: X X(I) N I J

a tömb neve, az X tömb I-edik eleme, a tömb elemeinek száma, index változó (külső index), index változó (belső index).

2 Azt a a művelet sort, amikor az algoritmus egyszer végigolvassa a tömböt, jobb híján rendezésnek nevezzük. Ha tehát a rendezést jelző nélkül használjuk erre gondolunk.

BEGIN buborék1 FOR I:=0 I
: : az N-3-dik futáskor N-1-(N-3), vagyis kétszer, az N-2-dik futáskor egyszer, az N-1-dik futáskor egyszer sem. Ez egy N-2 elemű számtani sorozat, melynek az első eleme N-1 az utolsó eleme 1 és a differencia értéke 1. Az elemek számának összege (N-1)N/2, tehát a futásidő O((N-1)N/2) Vegyünk példának egy 10 elemű tömböt az első, nem javított algoritmus futásideje 81, a másodiké 45. 2.3.3. Kétszeresen javított buborékrendezés A buborékrendezés tovább javítható, ha figyeljük, hogy egy rendezésen belül történt-e csere. Ennek figyelése ugyan időbe telik, mert a programnak járulékos feladatai vannak, de kedvező esetben ez a munka busásan megtérül. Vegyünk fel egy új változót és a belső ciklus előtt állítsuk hamis logikai értékre. A belső ciklus a szokott módon végig olvassa a tömböt, és ha kell, akkor végrehajtja a cseréket. Mikor egy csere bekövetkezett, a fent említett változókat állítsuk igaz értékre. Mikor a belső ciklusból kikerültünk láthatjuk, történt-e csere. Ha történt csere nem biztos, hogy készen vagyunk, viszont ha nem történt, akkor nincs értelme tovább vizsgálódnunk, mert a tömb már rendezett. A folyamat nyomon követhető a folyamatábrán BEGIN buborék3 FOR I:=0 I
probléma valós, vagy nem, minden esetben az adott programozási feladat határozza meg, azonban azt se felejtsük el, hogy egy számláló ciklus mindig hosszabb, mint egy egyszerű – csak feltételt vizsgáló ciklus. A futási időről még nem szóltunk, ebben az esetben a futási idő nem jósolható, csak korlátai adhatók meg, ezek: az alsó korlát o(1), a felső korlát O((N-1)N/2)

2.3.4. Szélsőérték kiemeléses rendezés A cím eléggé misztikus, a gyakorlatban ezt a rendezési eljárást a szakirodalom minimum, vagy maximum kiemeléses eljárásnak nevezi. Az előzőekhez hasonlóan itt is egyben tárgyaljuk a két rendezési irányt, így lett a cím. Az algoritmus működése a következő: Veszi a tömb első elemét és az utána következőket egyenként összehasonlítja vele, ha szükséges a két elemet felcseréli. A csere után már az összehasonlítás alapja az új elem. Könnyen belátható, ha mondjuk növekvő sorrendbe rendezünk, csere akkor következik be, ha a tömbből vett elem kisebb, mit az első. Az is belátható, hogy a tömb végigolvasása után a legkisebb elem lesz legelöl. A következő rendezésben már nem vizsgáljuk az első elemet, mert az már bizonyítottan kedvező (legkisebb vagy legnagyobb) számunkra, hanem a következőt kezdjük vizsgálni. Nézzük a folyamatábrát és a pszeudo kódot. Az alábbi pszeudo programban a K változót használjuk fel jelzésre. BEGIN szélső FOR I:=0 I
Az ábra mutatja a távolság változását.

A következő kérdés az, hogy milyen módon csökkentsük a távolságot. Eltekintve a matematikai bizonyítástól a következőkben az intervallumot mindig az előző felére választjuk. Az algoritmus igen bonyolultnak tűnik az első pillantásra, de rendkívül hatékony. X N I J K

a tömb neve, a tömb elemeinek száma, indexváltozó (középső index), indexváltozó (belső index), az cserélendő elemek távolsága. Nagyon lényeges, hogy a K egész típusú változó. Ez azt jelenti, ha kettővel osztjuk, akkor az osztás eredménye is egész lesz5. A program sorait megszámoztuk, hogy a magyarázatot könnyebb legyen követni. 1. BEGIN Shell 2. K:=N/2; 3. WHILE K>0 DO 4. BEGIN 5. FOR I:=K I=0 AND X(J)<X(J+K) STEP –K DO (J)X(J+K); 8. END; 9. K:=K/2; 10. END; 11. END. A program második sorában megadjuk a távolság kezdőértékét, ez tömb mértének fele lefelé „kerekítve”6.

5 Azért kell, hogy az osztás eredménye egész legyen, mert igen nehéz elképzelni tört indexű tömböket. 6 A megfogalmazás nagyon hivatalos. Itt, ha a tömb hossza páratlan, akkor az osztás után lesz egy törtrész, ezt egyszerűen elhagyjuk. Abban az esetbe, ha a tömb mérete páros nincs gond, mert a kettővel való osztás eredménye is egész.

A harmadik sor a külső ciklus feje, amely azt mondja meg, hogy meddig csökkenthetjük a távolságot. Eszerint a minimális távolság egy lehet. A középső ciklus, mely az 5. sorban kezdődik és a 8.-ban ér véget, az éppen aktuális K, vagyis a távolság értékétől az N–ig, vagyis a tömb maximális értékéig megy. A hetedik sorban kezdődik a belső ciklus ennek működése az alábbi pontokban van összefoglalva: A J változó az I-K értéket veszi fel, ami kezdetben 0. A belső ciklust egyrészt addig csinálja, míg J értéke nem negatív (J>=0), másrészt addig csinálja, míg a megfelelő tömb elemek nem felelnek meg a rendezés sorrendjének. Ha belép a ciklusba, akkor végrehajtja a cseréket. Ha program kilépett a belső ciklusból, a középső ciklusban előbbre lép egyet és a hetedik sort újra végrehajtja. Ha a középső ciklus is végetért, a K értéket megfelezi és a külső ciklust folytatja. Az algoritmust érdemes lenne egy példán lépésről lépésre végigkövetni, azonban ettől hely hiányában eltekintünk. Javasoljuk az olvasónak, hogy a jegyzet végén található C programot kövesse végig a fejlesztői környezet segítségével. Érdekés kérdés az, hogy hogyan hat a törtrészek levágása a rendezési algoritmusra. Láthattuk, hogy egyszerűen elhagytuk a törtrészeket az indexeknél, persze rá voltunk kényszerítve, mivel tört index nincs. Vajon nem keletkezik hiba? Nos a választ nem bizonyítjuk, de nem, mert nagyon röviden azt mondhatjuk, hogyha az intervallum rövidebb, akkor hosszabb szakaszon vizsgálja a tömböt a középső ciklus. A Shell rendezés futási idejével nem foglalkozunk, mert leírása túl hosszadalmas. 2.3.6. Gyors rendezés (Quick-sort) Ezt a rendezést, - hasonlóan a Shell módszerhez - akkor célszerű használni, ha nagy állományokat kell kezelnünk. Az algoritmus alapötlete a következőn alapul: tekintsük a rendezendő tömböt egy intervallumnak, felezzük meg a rendezendő tömböt, vegyük annak az elemnek az értékét, amely pont a felező ponton van (az indexek törtrészét megint elhagyjuk, vizsgáljuk az intervallum bal felét és jobb felét a középső elemhez viszonyítva úgy, hogy befelé haladunk7, ha ezek között találunk olyat, amelyek nem felelnek meg a rendezési elvnek, akkor cseréljük fel őket, ha csak az egyik oldalon találtunk, akkor a keresés végén a középső elemet is cseréljük fel, csináljuk mindezt addig, míg a jobb és balfél össze nem ér, 7 Vagyis a bal oldalon jobb felé, a jobboldalon bal felé.

a bal és a jobb oldalon külön – külön, mint új intervallumon ismételjük az eljárást, míg az intervallum hossza nagyobb, mint 0. Ezt az utolsó pontot a legegyszerűbb rekurzív módon végezni, hiszen a rendező rutin mar meg van írva és csak a paraméterezést kell helyesen megadni. Az ábra mutatja (töredékesen, hogyan alakul az intervallum hossza a rendezés során. A pszeudo kódunkban azért, hogy nem okozzon problémát csak a növekvő sorrendű rendezést vizsgáljuk, mert az eddig használt általános jelölés nagyon megnehezítené a program megértését.

Az előző példához hasonlóan itt is beszámozzuk a sorokat a könnyebb hivatkozás érdekében. A szokásostól eltérő változók: I J L R C

baloldali indexváltozó, jobboldali indexváltozó, az intervallum bal oldala, az intervallum jobb oldala, az intervallum középső eleme.

BEGIN quick_sort C:=(X(L)+X(R))/2; I:=L; J:=R; REPEAT DO WHILE X(I)C DO J:=J+1; IF I<=J THEN X(I)X(J); UNTIL(I>J) IF L<J THEN quick_sort(L,J); IF I
Ugyan ez a feltétel a hátultesztelő ciklusból történő kilépésre, ha a balodali index nagyobb, mint a jobboldali, akkor a ciklus befejeződött. Ezen a ponton az éppen aktuális C elemhez viszonyítva a tömb két részre van osztva, a balodalon csak a C-nél kisebb, vagy egyenlő elemek vannak, a jobboldalon csak a nagyobb, vagy egyenlők. A kilencedik sorban az eljárás meghívja saját magát olymódon, hogy a rendezendő intervalluma balodali indexe a régi intervallum balodali indexe, a jobboldali a középső elem indexe, vagy annál egyel nagyobb index. A tizedik sorban szintén egy rekurzív hívást látunk, ahol az balodali érték a középső elem indexe, vagy egyel kisebb érték és a jobboldali index a régi jobboldali index. Az algoritmus működését a folyamatábrán is nyomon követhetjük. Az algoritmus futási ideje hasonlóan a Shell módszerhez nagyon nehezen írható le, ezért ettől eltekintünk. 2.4. Kereső algoritmusok A kereső algoritmusok célja, hogy egy elemet keressünk meg egy halmazban valamely tulajdonsága alapján. Ebben a fejezetben tárgyaljuk a szélsőérték kereső algoritmust is. 2.4.1. Szélsőérték kereső algoritmus A feladat, hogy keressük meg egy halmazban a legnagyobb, vagy legkisebb elemet. Esetünkben legyen a kérdéses halmaz egy egydimenziós tömb. Az algoritmus működése a következő: vesszük az első elemet, és egy változóban elhelyezzük az értékét, olvassuk a tömböt, és ha találunk olyan értékű elemet a tömbben, amely a kiválasztási kritériumnak jobban megfelel beírjuk a változóba. A tömb végigolvasása után belátható, hogy a tömb kérdéses szélsőértéke a változóban lesz. Kicsit érthetőbben: szeretnénk egy tömb legkisebb elemét meghatározni, az első elemet elhelyezzük egy segédváltozóban, majd a második elemet összehasonlítjuk vele, ha az kisebb, akkor átírjuk az értéket a változóba. Ezután vesszük a harmadik eleme és így tovább. BEGIN szélső_érték C:=X(0); FOR I:=1 IX(I) THEN C:=X(I); END; END. Láthatjuk, hogy az algoritmus rendkívül egyszerű, futási ideje O(N-1). 2.4.2. Lineáris keresés A lineáris keresés nagyon hasonlít az előző szélsőérték kereső algoritmushoz. Itt azonban előre megadjuk, hogy mit keresünk a tömbben. Egyrészt arra vagyunk kíváncsiak, hogy van-e ilyen elem, másrészt arra, hogy hol található. A találat jelzésére használhatunk egy változó, de célszerűbb a találat index változóját felhasználni erre a célra. Miután az indexváltozó nem lehet negatív, ennek negatív értéke jelezheti, ha a keresés sikertelen volt. Ha ez 0 vagy pozitív, akkor volt találat és a változó a kérdéses elem helyét mutatja.

Felmerül a kérdés, hogy mi van akkor, ha több azonos elem van a tömbben. Igen könnyű meghatározni az elem első és utolsó előfordulását, erre is adunk megoldást. Az algoritmus működése a következő: a találat helyét meghatározó index változó értékét töltsük fel valamilyen negatív számmal – legyen –1 -, kezdjük olvasni a tömböt, ha van találat a tömbelem indexét írjuk be helyváltozóba és ..... Itt van a különbség, hogy az első vagy utolsó előfordulást keressük, mert ha az elsőt keressük, akkor a találat után rögtön kilépünk a ciklusból, és kész vagyunk. Ha az utolsót, akkor végigolvassuk a tömböt. Ez a program az első előfordulást keresi. 1. BEGIN lineáris_első 2. J:=-1; 3. FOR I:=0 I
1. BEGIN logaritmikus 2. WHILE LC THEN R:=M; 10. ELSE L:=M; 11. END; 12. J:=-1; 13. END.

A másik felmerülő kérdés az, hogy miért nem az L=R-ig fut a ciklus, a válasz igen egyszerű, az egészértékűség miatt a program végtelen ciklusba kerülne. Ennek bizonyítására vegyük a következő egyszerű példát: Adott egy tetszőleges K nemnegatív szám nézzük, hogy mi a következő kifejezés értéke: M=(K+K+1)/2=(2K+1)/2=K+0.5 ennek viszont az egészértéke újra K, tehát a feltétel sohasem teljesül, ha a keresett elem nincs a tömbben a program végtelenciklusba kerül. Az algoritmus futásidejének felső korlátja O(log2(N)+1). Ez azt jelenti, hogy 1024 elemből 10 lépés után megtalálja, vagy nem találja meg a keresett elemet. 2.5. Összefésülés A most következő algoritmus arra szolgál, hogy két azonos módon (növekvő, vagy csökkenő sorrendbe) rendezett tömböt összemásoljunk olymódon, hogy az eredményként kapott tömb szintén rendezett legyen. A legegyszerűbb természetesen az lenne, ha a két tömböt egymás után másolnánk, majd ezután rendeznénk. Tulajdonképpen ez a megoldás nem rossz, csak hosszadalmas. Ennek a problémának elkerülésére használjuk a klasszikus összefésülés, vagy más néven összefuttatás algoritmust. Ez az eljárás úgy másol, hogy a rendezettséget szem előtt tartja és az eredmény azonnal rendezett tömbként jelenik meg. Az algoritmus működése a következő: az első tömbből veszünk egy elemet, összehasonlítjuk a másik tömbből vett elemmel, amelyik a rendezés módjának megfelel, az kerül az eredmény tömbbe. Annak tömbnek az indexét, amelynek eleme bekerült az eredménybe, növeljük. Ha valamelyik bemeneti tömb elemei elfogytak, akkor már nem kell – nincs is mit – összehasonlítani, hanem a másik tömbből maradt elemeket az eredmény tömbbe átmásoljuk. Nézzük a pszeudo kódot. A változók magyarázata: A Az egyik bemeneti rendezett tömb, B A másik bemeneti rendezett tömb, C Az eredmény tömb, AL Az első tömb hossza, BL A második tömb hossza, I Az első tömb indexe, J A második tömb indexe, K Az eredmény tömb indexe. 1. 2. 3. 4.

BEGIN összefésül I:=0; J:=0; FOR K:=0 K<(AL+BL) STEP 1 DO BEGIN

5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32.

IF I B(J) THEN BEGIN C(K):=A(I); I:=I+1; END ELSE BEGIN C(K):=B(J); J:=J+1; END; END ELSE BEGIN IF I
A 2. sorban a két bemeneti tömb indexeinek kezdeti értékét állítjuk be. A fő ciklus a 3. sorban kezdődik és a 31. sorig tart. Az 5. sorban megvizsgáljuk, hogy kell-e még az összehasonlítással bajlódnunk. Ha mindkét indexváltozó kisebb, mint a bementi tömbök hossza, akkor még mindkét bemeneti tömbből vannak fel nem használt elemek. A 7. sorban a program megnézi, hogy melyik elem kerüljön az eredmény tömbbe. Ha a reláció megfelel a rendezés módjának, akkor a C tömbbe az A tömb eleme, ha nem a B tömb eleme kerül. A 10. és a 15. sorban láthatjuk, hogy annak a tömbnek az indexe nő, amelynek az eleme bekerült az eredménybe. A 18. sorban kezdődik a program azon része, ahol valamelyik tömb elemei elfogytak. A 20. sorban megvizsgáljuk melyik tömb tartalmaz még fel nem használt elemet. Ezután a maradékot felmásoljuk az eredmény tömb végére.