1.1. Programozási tételek

(1)

Informatikai-matematika záróvizsga tankönyv

2018-2019

(2)

Informatikai-matematika szak

(a 2019. júliusi vizsgaid˝oszaktól érvényes)

Algoritmusok és programozás (4 téma)

1. Keresés (szekvenciális és bináris), rendezés (buborékrendezés, gyorsrendezés (quicksort), kiválasztásos rendezés).

2. Algoritmusok és specifikációk. Algoritmus írása egy adott specifikáció alapján.

Adott egy algoritmus, adjuk meg a végrehajtása eredményét.

3. Objektumorientált programozási fogalmak a Python, C++, Java és C# progra- mozási nyelvekben: osztályok és objektumok; egy osztály tagjai és hozzáférési módosítók; konstruktorok és destruktorok.

4. Osztályok közötti kapcsolatok: származtatott osztályok és öröklési viszony; me- tódusok felülírása; polimorfizmus; dinamikus kötés; absztrakt osztályok és in- terfészek.

(3)

1. Algoritmusok és programozás (Ionescu Klára). . . 5

1.1. Programozási tételek . . . 5

1.2. Lépések finomítása és optimalizálás . . . 21

1.3. Rendez˝o algoritmusok . . . 26

1.4. A visszalépéses keresés módszere (backtracking) . . . 29

1.5. Az oszd meg és uralkodj módszer (divide et impera) . . . 42

2. Objektumorientált programozás (Darvay Zsolt) . . . 49

2.1. Objektumorientált fogalmak . . . 49

2.2. Az objektumorientált programozási módszer . . . 64

2.3. Javasolt feladatok . . . 72

(4)

Minden jog fenntartva! E tankönyvet, illetve annak részeit tilos reprodukálni, adat- rögzít˝o rendszerben tárolni, bármilyen formában vagy eszközzel – elektronikus úton vagy más módon – közölni a szerz˝ok el˝ozetes írásbeli engedélye nélkül.

A szerz˝ok a lehet˝o legnagyobb körültekintéssel jártak el e tankönyv szerkesztése- kor. A szerz˝ok nem vállalnak semmilyen garanciát e kiadvány tartalmával, teljessé- gével kapcsolatban. A szerz˝ok nem vonhatóak felel˝osségre bármilyen baleset, vagy káresemény miatt, amely közvetlen vagy közvetett úton kapcsolatba hozható e tan- könyvvel.

(5)

5

1. fejezet Algoritmusok és programozás

1.1. Programozási tételek

A feladatok feladatosztályokba sorolhatók a jellegük szerint. E feladatosztályokhoz készí- tünk a teljes feladatosztályt megoldó algoritmusosztályt, amelyeket programozási tételeknek nevezünk. Bebizonyítható, hogy ezek a megoldások a szóban forgó feladatok garantáltan he- lyes és optimális megoldásai.

A programozási tételek a feladat bemenete és kimenete szerint négy csoportra oszthatók:

A. sorozathoz érték rendelése (1 sorozat – 1 érték) B. sorozathoz sorozat rendelése (1 sorozat – 1 sorozat) C. sorozatokhoz sorozat rendelése (több sorozat – 1 sorozat) D. sorozathoz sorozatok rendelése (1 sorozat – több sorozat) A. Sorozathoz érték rendelése

1.1.1. Sorozatszámítás

Adott az N elemű X sorozat. A sorozathoz hozzá kell rendelnünk egyetlen S értéket. Ezt az értéket egy, az egész sorozaton értelmezett f függvény (pl. elemek összege, szorzata stb.) adja.

Ezt a függvényt felbonthatjuk értékpárokon kiszámított függvények sorozatára, így a megoldás az F0 semleges elemre, valamint egy kétoperandusú műveletre épül. Az S kezdőértéke a semleges elem. A kétoperandusú műveletet végrehajtjuk minden Xi elemre és az S értékre: S ← f(Xi, S).

Összeg és szorzat

Egyetlen kimeneti adatot számítunk ki, adott számú bemeneti adat feldolgozásának eredmé- nyeként, például a bemeneti adatok összegét, esetleg szorzatát kell kiszámítanunk.

Megoldás

A feladat megoldása előtt szükséges tudni, hogy mely érték felel meg a bemeneti adatok halmazára és az elvégzendő műveletre nézve a semleges elemnek. Feltételezzük, hogy a bemeneti adatok egész számok, amelyeknek a számossága N¹.

Algoritmus Összegszámítás(N, X, S): { Sajátos eset } { Bemeneti adatok: az N elemű X sorozat, kimeneti adat: S } S  0

Minden i = 1, N végezd el: { minden adatot fel kell dolgoznunk } S  S + X_i

vége(minden) Vége(algoritmus)

1 A következőkben az algoritmusok implementálása különböző típusú függvényekként szabadon választható. Ha a függvény egyetlen értéket számít ki, akkor ezt nem kötelező kimeneti paraméterként implementálni, hanem térítheti a függvény.

(6)

Az előbbi algoritmus általánosítva:

Algoritmus Feldolgoz(N, X, S):

{ Bemeneti adatok: az N elemű X sorozat, kimeneti adat: S } S  F₀ { kezdőérték: az elvégzendő műveletre nézve semleges elem } Minden i = 1, N végezd el: { minden adatot fel kell dolgoznunk }

S  f(S, X_i) { f a művelet (funkció) }

1.1.2. Döntés

Adott az N elemű X sorozat és az elemein értelmezett T tulajdonság. Döntsük el, hogy léte- zik-e a sorozatban legalább egy T tulajdonságú elem!

Elemzés

A sorozat elemei tetszőlegesek, egyetlen jellemzőt kell feltételeznünk róluk: bármely elem- ről el lehet dönteni, hogy rendelkezik-e az adott tulajdonsággal, vagy nem. A válasz egy üzenet, amelyet az alprogram kimeneti paramétere (logikai változó) értéke alapján ír ki a hívó program- egység.

Algoritmus Döntés_1(N, X, talált):

{ Bemeneti adatok: az N elemű X sorozat. Ha az X sorozatban található } { legalább egy T tulajdonságú elem, talált értéke igaz, különben hamis }

i  1 { kezdőérték az indexnek }

talált  hamis { kezdőérték a kimeneti adatnak } Amíg nemtalált és(i  N)végezd el:

Ha nemT(Xi)akkor { amíg nem találunk egy X_i-t, amely rendelkezik } i  i + 1 { a T tulajdonsággal, haladunk előre }

különben

talált  igaz vége(ha)

vége(amíg) Vége(algoritmus)

A fenti algoritmus megírható tömörebben is:

Algoritmus Döntés_2(N, X, talált):

{ Bemeneti adatok: az N elemű X sorozat. Ha az X sorozatban } { található legalább egy T tulajdonságú elem, talált értéke igaz, különben hamis } i  1

Amíg(i  N)és nemT(X_i)végezd el: { amíg nem találunk egy Xi-t, amely } i  i + 1 { rendelkezik a T tulajdonsággal, haladunk előre } vége(amíg)

talált  i  N { kiértékelődik a relációs kifejezés; az érték talált értéke lesz } Vége(algoritmus)

(7)

Egy másik megközelítésben el kell döntenünk, hogy az adatok, teljességükben, rendelkeznek-e egy adott tulajdonsággal vagy sem. Más szóval: nem létezik egyetlen adat sem, amely ne lenne T tulajdonságú. Ekkor a bemeneti adathalmaz minden elemét meg kell vizsgálnunk.

Mivel a döntés jelentése az összes adatra érvényes, a talált változót átkereszteljük mind-re.

Algoritmus Döntés_3(N, X, mind):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: ha az X sorozatban } { minden elem T tulajdonságú, a mind értéke igaz, különben hamis } i  1

Amíg(i  N)ésT(X_i)végezd el: { a nemT(X_i) részkifejezés tagadása } i  i + 1

vége(amíg)

mind  i > N { az i  N részkifejezés tagadása } Vége(algoritmus)

1.1.3. Kiválasztás

Adott az N elemű X sorozat és az elemein értelmezett T tulajdonság. Adjuk meg a sorozat egy T tulajdonságú elemének sorszámát! (Előfeltétel: garantáltan létezik ilyen elem.)

Algoritmus Kiválasztás(N, X, hely):

{ Bemeneti adatok: az N elemű X sorozat. }

{ Kimeneti adat: hely, a legkisebb indexű T tulajdonságú elem sorszáma } hely  1

Amíg nemT(Xhely)végezd el: { nem szükséges a hely ≤ N feltétel, mivel a feladat } hely  hely + 1 { garantálja legalább egy T tulajdonságú elem létezését } vége(amíg)

Vége(algoritmus)

1.1.4. Szekvenciális (lineáris) keresés

Adott az N elemű X sorozat és az elemein értelmezett T tulajdonság. Vizsgáljuk meg, hogy létezik-e T tulajdonságú elem a sorozatban! Ha létezik, akkor adjuk meg az első ilyen elem helyét!

Algoritmus Keres_1(N, X, hely):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: hely, a legkisebb indexű T } { tulajdonságú elem indexe, illetve, sikertelen keresés esetén hely = 0 } hely  0

i  1

Amíg(hely = 0)és (i ≤ N)végezd el:

HaT(X_i) akkor hely  i különben i  i + 1 vége(ha) vége(amíg) Vége(algoritmus)

(8)

Az adott elem tulajdonságát az Amíg feltételében is ellenőrizhetjük. Más szóval: amíg az aktuális elem tulajdonsága nem megfelelő, haladunk a sorozatban előre:

Algoritmus Keres_2(N, X, hely):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: hely, a legkisebb indexű T } { tulajdonságú elem indexe, illetve, sikertelen keresés esetén hely = 0 } i  1

Amíg(i ≤ N)és nemT(Xi) végezd el:

i  i + 1 vége(amíg)

Hai ≤ Nakkor { ha kiléptünk az Amíg-ból, mielőtt i nagyobbá vált volna N-nél, } hely  i { ⇒ találtunk adott tulajdonságú elemet az i. pozición } különben

hely  0 { különben nem találtunk }

vége(ha) Vége(algoritmus)

Ha a feladat azt kéri, hogy keressünk meg minden olyan elemet, amely rendelkezik az adott tulajdonsággal, be kell járnunk a teljes adathalmazt, és vagy kiírjuk azonnal a pozíciókat, ahol megfelelő elemet találtunk, vagy megőrizzük ezeket egy másik sorozatban. Ilyenkor Minden típusú struktúrát használunk.

1.1.5. Megszámlálás

Adott, N elemű X sorozatban számoljuk meg a T tulajdonságú elemeket!

Elemzés

Nem biztos, hogy létezik legalább egy T tulajdonságú elem, tehát az is lehetséges, hogy az eredmény 0 lesz. Mivel minden elemet meg kell vizsgálnunk (bármely adat rendelkezhet a kért tulajdonsággal), Minden típusú struktúrával dolgozunk. A darabszámot a db változóban tároljuk.

Algoritmus Megszámlálás(N, X, db):

{ Bemeneti adatok: az N elemű X sorozat }

{ Kimeneti adat: db, a T tulajdonságú elemek darabszáma } db  0

Minden i = 1, N végezd el:

Ha T(X_i) akkor db  db + 1 vége(ha)

1.1.6. Maximumkiválasztás

Adott az N elemű X sorozat. Határozzuk meg a sorozat legnagyobb (vagy legkisebb) értékét!

Megoldás

A megoldásban minden adatot meg kell vizsgálnunk, ezért az algoritmus egy Minden típusú struktúrával dolgozik. A max segédváltozó a sorozat első elemétől kap kezdőértéket.

(9)

Algoritmus Maximumkiválasztás(N, X, max):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: max, a legnagyobb elem értéke } max  X₁

Minden i = 2, n végezd el:

Ha max < X_i akkor max  X_i

vége(ha) vége(minden) Vége(algoritmus)

A maximumot/minimumot tartalmazó segédváltozónak az adatok közül választunk kezdő- értéket, mivel így nem áll fenn a veszély, hogy az algoritmus eredménye egy, az adataink között nem létező érték legyen.

Ha a maximum helyét kell megadnunk, az algoritmus a következő:

Algoritmus MaximumHelye(N, X, hely):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: hely, a legnagyobb elem pozíciója }

hely  1 { hely az első elem pozíciója }

Ha X_hely < X_i akkor

hely  i { a maximális elem első előfordulásának helye (pozíciója) } vége(ha)

Ha minden olyan indexet meg kell határoznunk, amely indexű elemek egyenlők a legnagyobb elemmel és nem lehetséges/nem előnyös az adott tömböt kétszer bejárni, mert a maxi- mumhoz tartozó adatok egy másik (esetleg bonyolult) algoritmus végrehajtásának eredményei, írhatunk algoritmust, amely csak egyszer járja be a sorozatot:

Algoritmus MindenMaximumHelye(N, X, db, indexek):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: a db elemű indexek sorozat } max  X₁

db  1 indexek1  1

Ha max < X_i akkor max  X_i

db  1

indexek_db  i különben

Ha max = Xi akkor db  db + 1 indexekdb  i vége(ha)

(10)

B. Sorozathoz sorozat rendelése

1.1.7. Másolás

Adott az N elemű X sorozat és az elemein értelmezett f függvény. A bemeneti sorozat minden elemére végrehajtjuk a függvényt, az eredményét pedig a kimeneti sorozatba másoljuk.

Algoritmus Másolás(N, X, Y):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: az N elemű Y sorozat } Minden i = 1, N végezd el:

Y_i  f(X_i) vége(minden) Vége(algoritmus)

1.1.8. Kiválogatás

Adott az N elemű X sorozat és az elemein értelmezett T tulajdonság. Válogassuk ki az összes T tulajdonságú elemet!

Elemzés

Az elvárások függvényében különböző megközelítések lesznek érvényesek:

a. kiválogatás kigyűjtéssel b. kiválogatás kiírással

c. kiválogatás helyben (sorrendváltoztatással vagy megőrizve az eredeti sorrendet) d. kiválogatás kihúzással (segédsorozattal vagy helyben)

a. Kiválogatás kigyűjtéssel

A keresett elemeket (vagy sorszámaikat) kigyűjtjük egy sorozatba. A pozíciók sorozatának (vagy a kigyűjtött elemek sorozatának) hossza legfeljebb az adott sorozatéval lesz megegyező, mivel előfordulhat, hogy a bemeneti sorozat minden eleme adott tulajdonságú. A sorozat szá- mosságát a db változóban tartjuk nyilván.

Algoritmus Kiválogatás_a(N, X, db, pozíciók):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: a db elemű pozíciók sorozat } db  0

Ha T(X_i) akkor db  db + 1

pozíciók_db  i { pozíciókdb-ben tároljuk az Xi helyét } vége(ha)

vége(minden) Vége(algoritmus) b. Kiválogatás kiírással

Ha a feladat „megelégszik” a T tulajdonságú elemek kiírásával (nem kéri ezek darabszámát is), az algoritmus a következő:

(11)

Algoritmus Kiválogatás_b(N, X):

{ Bemeneti adatok: az N elemű X sorozat }

Ha T(X_i) akkor Ki: X_i

c. Kiválogatás helyben

Ha a sorozat feldolgozása közben a nem T tulajdonságú elemeket nem óhajtjuk megőrizni, hanem ki szeretnénk zárni ezeket a sorozatból, akkor a feladat specifikációitól függően, a követ- kező lehetőségek közül fogunk választani:

c1. Ha a törlés után nem kötelező, hogy az elemek az eredeti sorrendjükben maradjanak, akkor a törlendő elemre rámásoljuk a sorozat utolsó elemét és csökkentjük 1-gyel a sorozat méretét:

Algoritmus Kiválogatás_c1(N, X):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: a megváltozott elemszámú X sorozat } i  1

Amíg i ≤ N végezd el: { nem alkalmazunk Minden-t, mivel változik az N!!! } Ha nem T(Xi) akkor { a T tulajdonságú elemeket tartjuk meg } X_i  X_N { Xi-t felülírjuk XN-nel } N  N – 1 { változik a sorozat hossza } különben

i  i + 1 { i csak a különben ágon nő } vége(ha)

c2. Ha az eredeti sorozatra nincs többé szükség, de szeretnénk megőrizni az elemek eredeti sorrendjét, akkor a T tulajdonságú elemeket felsorakoztatjuk a sorozat elejétől kezdve. Így a kiválogatott elemekkel felülírjuk az eredeti adatokat. Nem használunk egy újabb sorozatot, hanem az adott sorozat számára lefoglalt tárrészt használva helyben végezzük a kiválogatást. A db változó ebben az esetben a megváltoztatott sorozatnak a számosságát tartja nyilván:

Algoritmus Kiválogatás_c2(N, X, db):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: a db elemű X sorozat } db  0

Ha T(Xi) akkor db  db + 1 Xdb  Xi

(12)

d1. Ha a törlés ideiglenes, akkor a kereséssel párhuzamosan egy logikai tömbben nyilvántartjuk a „törölt” elemeket. A törölt tömb elemeinek kezdőértéke hamis lesz, majd a törlendő elemek- nek megfelelő sorszámú elemek értéke a törölt logikai tömbben igaz lesz:

Algoritmus Kiválogatás_d1(N, X, törölt):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: az N elemű törölt sorozat } Minden i = 1, N végezd el:

törölt_i  hamis vége(minden)

Ha nem T(X_i) akkor { a T tulajdonságú elemeket tartjuk meg } törölt_i  igaz

d2. Egy másik megoldás, amely nem hoz létre új helyen, új sorozatot, helyben végzi a kiválo- gatást, anélkül, hogy elmozdítaná eredeti helyükről a T tulajdonságú elemeket, a nem T tulaj- donságú elemek helyére pedig egy speciális értéket tesz:

Algoritmus Kiválogatás_d2(N, X, törölt):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: az N elemű X sorozat } Minden i = 1, N végezd el:

Ha nem T(X_i) akkor { a T tulajdonságú elemeket tartjuk meg } X_i  speciális érték

C. Sorozatokhoz sorozat rendelése

1.1.9. Halmazok

Mielőtt egy halmazokat tartalmazó sorozatra vonatkozó műveletet alkalmaznánk, szükséges meggyőződnünk arról, hogy a sorozat valóban halmaz. Ez azt jelenti, hogy minden érték csak egyszer fordul elő. Ha kiderül, hogy a sorozat nem halmaz, halmazzá kell alakítanunk.

a. Halmaz-e?

Döntsük el, hogy az adott N elemű X sorozat halmaz-e!

Elemzés

Egy halmaz vagy üres, vagy bizonyos számú elemet tartalmaz. Ha egy halmazt sorozattal implementálunk, az elemei különbözők. A következő algoritmussal eldöntjük, hogy a sorozat csak különböző elemeket tartalmaz-e?

Algoritmus Halmaz_e(N, X, ok):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: az ok értéke igaz, } i  1 { ha a sorozat halmaz, különben hamis } ok  igaz

(13)

Amíg ok és (i < N) végezd el:

j  i + 1

Amíg (j ≤ N) és (X_i ≠ X_j) végezd el:

j  j + 1 vége(amíg)

ok  j > N { ha véget ért a sorozat, nincs két azonos elem } i  i + 1

b. Halmazzá alakítás

Alakítsuk halmazzá az N elemű X sorozatot!

Elemzés

Ha egy alkalmazásban ki kell zárnunk az adott sorozatból a másodszor (harmadszor stb.) megjelenő értékeket, akkor az előbbi algoritmust módosítjuk: amikor egy bizonyos érték meg- jelenik másodszor, felülírjuk az utolsóval.

Algoritmus HalmazzáAlakít(N, X):

{ Bemeneti adatok: az N elemű X sorozat. } {Kimeneti adatok: az új N elemű X sorozat (halmaz) } i  1

Amíg i < N végezd el:

j  i + 1

Amíg (j ≤ N) és (Xi ≠ Xj) végezd el:

j  j + 1 vége(amíg)

Ha j ≤ N akkor { találtunk egy Xj = Xi-t } Xj  XN { felülírjuk a sorozat N. elemével }

N  N – 1 { rövidítjük a sorozatot }

különben

i  i + 1 { haladunk tovább }

vége(ha) vége(amíg) Vége(algoritmus)

1.1.10. Keresztmetszet

Hozzuk létre a bemenetként kapott sorozatok keresztmetszetét!

Elemzés

Keresztmetszet alatt azt a sorozatot értjük, amely az adott sorozatok közös elemeit tartalmazza. Feltételezzük, hogy az adott sorozatok mind különböző elemeket tartalmaznak (halmazok) és nem rendezettek.

Az N elemű X és az M elemű Y sorozat keresztmetszetét a db elemű Z sorozatban hozzuk létre, tehát Z olyan elemeket tartalmaz az X sorozatból, amelyek megtalálhatók az Y-ban is.

(14)

Algoritmus Keresztmetszet(N, X, M, Y, db, Z):

{ Bemeneti adatok: az N elemű X és az M elemű Y sorozat. } db  0 { Kimeneti adatok: a db elemű Z sorozat, X és Y keresztmetszete } Minden i = 1, N végezd el:

j  1

Amíg (j ≤ M) és (X_i ≠ Y_j) végezd el:

j  j + 1 vége(amíg) Ha j ≤ M akkor db  db + 1 Z_db  X_i vége(ha) vége(minden) Vége(algoritmus)

1.1.11. Egyesítés (Unió)

Hozzuk létre az N elemű X és az M elemű Y sorozatok (halmazok) egyesített halmazát!

Elemzés

Az egyesítés algoritmusa hasonló a keresztmetszetéhez. Nem alkalmazhatunk összefésülést, mivel a sorozatok nem rendezettek! A különbség abban áll, hogy olyan elemeket helyezünk az eredménybe, amelyek legalább az egyik sorozatban megtalálhatók. Előbb a Z sorozatba másol- juk az X sorozatot, majd kiválogatjuk Y-ból azokat az elemeket, amelyeket nem találtunk meg X-ben.

Algoritmus Egyesítés(N, X, M, Y, db, Z):

{ Bemeneti adatok: az N elemű X és az M elemű Y sorozat. } { Kimeneti adatok: a db elemű Z sorozat (X és Y egyesítése) } Másolás(N, X, Z) { az X sorozat minden elemét átmásoljuk a Z sorozatba } db  N

Minden j = 1, M végezd el:

i  1

Amíg (i ≤ N) és (X_i ≠ Y_j) végezd el:

i  i + 1 vége(amíg) Ha i > N akkor db  db + 1 Zdb  Yj

1.1.12. Összefésülés

Adott két rendezett sorozatból állítsunk elő egy harmadikat, amely legyen szintén rendezett!

(15)

Elemzés

Az Egyesítés(N, X, M, Y, db, Z) és a Keresztmetszet(N, X, M, Y, db, Z) algoritmusok négyze- tes bonyolultságúak, mivel a halmazokat implementáló sorozatok nem rendezettek. Ez a két művelet megvalósítható lineáris algoritmussal, ha a sorozatok rendezettek. Így az eredményt is rendezett formában fogjuk generálni. Ezek a sorozatok nem mindig halmazok, tehát néha elő- fordulhatnak azonos értékű elemek is.

Elindulunk mindkét sorozatban és a soron következő két elem összehasonlítása révén el- döntjük, melyiket tegyük a harmadikba. Addig végezzük ezeket a műveleteket, amíg valamelyik sorozatnak a végére nem érünk. A másik sorozatban megmaradt elemeket átmásoljuk az eredménysorozatba. Mivel nem tudhatjuk előre melyik sorozat ért véget, vizsgáljuk mindkét sorozatot.

Algoritmus Összefésülés_1(N, X, M, Y, db, Z):

{ Bemeneti adatok: az N elemű X és az M elemű Y sorozat. A sorozatok nem halmazok. } { Kimeneti adatok: a db elemű Z sorozat (X és Y elemeivel) } db  0

i  1 j  1

Amíg (i ≤ N) és (j ≤ M) végezd el: { amíg sem X-nek, sem Y-nak nincs vége } db  db + 1

Ha X_i < Y_j akkor Z_db  X_i

i  i + 1 különben Z_db  Y_j j  j + 1 vége(ha) vége(amíg)

Amíg i ≤ N végezd el: { ha maradt még elem X-ben } db  db + 1

Zdb  Xi

Amíg j ≤ M végezd el: { ha maradt még elem Y-ban } db  db + 1

Z_db  Y_j j  j + 1 vége(amíg) Vége(algoritmus)

Most feltételezzük, hogy az egyes sorozatokban egy elem csak egyszer fordul elő és azt szeretnénk, hogy az összefésült új sorozatban se legyenek „duplák”. Az előző algoritmust csak annyiban módosítjuk, hogy vizsgáljuk az egyenlőséget is. Ha a két összehasonlított érték egyen- lő, mind a két sorozatban továbblépünk és az aktuális értéket csak egyszer írjuk be az eredmény- sorozatba.

(16)

Algoritmus Összefésülés_2(N, X, M, Y, db, Z):

{ Bemeneti adatok: az N elemű X és az M elemű Y sorozat. A sorozatok halmazok } { Kimeneti adatok: a db elemű Z sorozat (X és Y elemeivel) } db  0

i  1 j  1

Amíg (i ≤ N) és (j ≤ M) végezd el:

db  db + 1 Ha Xi < Yj akkor Zdb  Xi

i  i + 1 különben

Ha Xi = Yj akkor Zdb  Xi

i  i + 1 j  j + 1 különben Zdb  Yj

j  j + 1 vége(ha) vége(ha) vége(amíg)

Amíg i ≤ N végezd el: { ha maradt még elem X-ben } db  db + 1

Zdb  Xi

Amíg j ≤ m végezd el: { ha maradt még elem Y-ban } db  db + 1

Z_db  Y_j j  j + 1 vége(amíg) Vége(algoritmus)

Szerencsés esetben XN = YM. Ekkor a két utolsó Amíg struktúra nem hajtódott volna végre egyetlen egyszer sem. Kihasználva ezt az észrevételt, elhelyezünk mindkét sorozat végére egy fiktív elemet (őrszem). Tehetjük az X sorozat végére az XN+1 = YM + 1 értéket és az Y sorozat végére az YM+1 = XN + 1 értéket. Ha a két egyesítendő sorozat nem halmaz, az eredmény sem lesz halmaz. Észrevesszük, hogy ebben az esetben az eredménysorozat hossza pontosan N + M.

Az algoritmus ismétlőstruktúrája Minden típusú lesz.

Algoritmus Összefésül_3(N, X, M, Y, db, Z):

{ Bemeneti adatok: az N elemű X és az M elemű Y sorozat. A sorozatok nem halmazok } { Kimeneti adatok: a db elemű Z sorozat (X és Y elemeivel) } i  1

j  1

(17)

X_N+1  Y_M + 1 Y_M+1  X_N + 1

Minden db = 1, N + M végezd el:

Ha Xi < Yj akkor Zdb  Xi

i  i + 1 különben Z_db  Y_j j  j + 1 vége(ha) vége(minden) Vége(algoritmus)

Ha a bemeneti sorozatok halmazokat ábrázolnak és az eredménysorozatnak is halmaznak kell lennie, az algoritmus a következőképpen alakul: a Minden struktúra helyett Amíg-ot alkalmazunk, hiszen nem tudjuk hány eleme lesz az összefésült sorozatnak (az ismétlődő értékek közül csak egy kerül be az új sorozatba). Ugyanakkor, az őrszemek révén az Amíg struktúrát addig hajtjuk végre, amíg mindkét sorozat végére nem értünk.

Algoritmus Összefésül_4(N, X, M, Y, db, Z):

{ Bemeneti adatok: az N elemű X és az M elemű Y sorozat. A sorozatok halmazok } { Kimeneti adatok: a db elemű Z sorozat (X és Y elemeivel) } db  0

i  1 j  1

XN+1  Y_M + 1 Y_M+1  X_N + 1

Amíg (i ≤ N) vagy (j ≤ M) végezd el:

db  db + 1 Ha X_i < Y_j akkor Zdb  X_i

i  i + 1 különben

Ha Xi = Yj akkor Zdb  Xi

i  i + 1 j  j + 1 különben Z_db  Y_j j  j + 1 vége(ha) vége(ha) vége(amíg) Vége(algoritmus)

(18)

D. Sorozathoz sorozatok rendelése

1.1.13. Szétválogatás

Válogassuk szét az adott N elemű X sorozat elemeit adott T tulajdonság alapján!

Elemzés

A Kiválogatás(N, X) algoritmus egy sorozatot dolgoz fel, amelyből kiválogat bizonyos elemeket. Kérdés: mi történik azokkal az elemekkel, amelyeket nem válogattunk ki? Lesznek feladatok, amelyek azt kérik, hogy két vagy több sorozatba válogassuk szét az adott sorozatot.

a. Szétválogatás két új sorozatba

Az adott sorozatból létrehozunk két újat: a T tulajdonsággal rendelkező adatok sorozatát, és a megmaradtak sorozatát. Mindkét új sorozatot az eredetivel azonos méretűnek deklaráljuk, mivel nem tudhatjuk előre az új sorozatok valós méretét. (Előfordulhat, hogy valamennyi elem átvándorol valamelyik sorozatba, és a másik üres marad.) A dby és dbz a szétválogatás során létrehozott Y és Z sorozatba helyezett elemek számát jelöli.

Algoritmus Szétválogatás_1(N, X, dby, Y, dbz, Z):

dby  0 { Bemeneti adatok: az N elemű X sorozat. } dbz  0 { Kimeneti adat: a dby elemű Y és a dbz elemű Z sorozat } Minden i = 1, N végezd el:

Ha T(X_i) akkor

dby  dby + 1 { az adott tulajdonságú elemek, az Y sorozatba kerülnek } Y_dby  X_i

különben

dbz  dbz + 1 { azok, amelyek nem rendelkeznek az } Z_dbz  X_i { adott tulajdonsággal, a Z sorozatba kerülnek } vége(ha)

b. Szétválogatás egyetlen új sorozatba

A feladat megoldható egyetlen új sorozattal. A kiválogatott elemeket az új sorozat első részébe helyezzük (az elsőtől haladva a vége felé), a megmaradtakat az új sorozat végére (az utolsótól haladva az első felé). Nem fogunk ütközni, mivel pontosan N elemet fogunk N helyre

„átrendezni”. A megmaradt elemek az eredeti sorozatban elfoglalt relatív pozícióik fordított sorrendjében kerülnek az új sorozatba.

Algoritmus Szétválogatás_2(N, dby, dbz, X, Y):

dby  0{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adat: az N elemű Y sorozat; } dbz  0 { az első dby elem T tulajdonságú, dbz elem pedig nem T tulajdonságú } Minden i = 1, N végezd el:

Ha T(X_i) akkor { a T tulajdonságú elemek az Y sorozatba kerülnek } dby  dby + 1 { az első helytől kezdődően } Ydby  Xi

(19)

különben

dbz  dbz + 1 { a többi elem szintén Y-ba kerül, az utolsó helytől kezdődően } YN-dbz+1  Xi

c) Szétválogatás helyben

Ha a szétválogatás után nincs már szükségünk többé az eredeti sorozatra, a szétválogatás elvégezhető helyben. A tömb első elemét kivesszük a helyéről és megőrizzük egy segédválto- zóban. Az utolsó elemtől visszafelé megkeressük az első olyat, amely adott tulajdonságú, s ezt előre hozzuk a kivett elem helyére. Ezután a hátul felszabadult helyre elölről keresünk egy nem T tulajdonságú elemet, s ha találunk, azt hátratesszük. Mindezt addig végezzük, amíg a tömbben két irányban haladva össze nem találkozunk.

Algoritmus Szétválogatás_3(N, X, db):

{ Bemeneti adatok: az N elemű X sorozat. Kimeneti adatok: az N elemű X sorozat; } { az első e elem T tulajdonságú, n – e elem pedig nem T tulajdonságú } e  1 { balról jobbra haladva az első T tulajdonságú elem indexe } u  N { jobbról balra haladva az első nem T tulajdonságú elem indexe } segéd  X_e

Amíg e < u végezd el:

Amíg (e < u) és nem T(X_u) végezd el:

u  u – 1 vége(amíg) Ha e < u akkor Xe  Xu

e  e + 1

Amíg (e < u) és T(Xe) végezd el:

e  e + 1 vége(amíg) Ha e < u akkor X_u  X_e u  u - 1 vége(ha) vége(ha) vége(amíg)

X_e  segéd { visszahozzuk a segéd-be tett elemet } Ha T(X_e) akkor db  e

különben db  e - 1 vége(ha)

Vége(algoritmus) Megjegyzés

Ha egy sorozatot több részsorozatba szükséges szétválogatni több tulajdonság alapján, egy- más után több szétválogatást fogunk végezni, mindig a kért tulajdonság alapján.

(20)

Előbb szétválogatjuk az adott sorozatból az első tulajdonsággal rendelkezőket, majd a félretett adatokból szétválogatjuk a második tulajdonsággal rendelkezőket és így tovább.

1.1.14. Programozási tételek összeépítése

Az egészen egyszerű alapfeladatokat kivéve általában több programozási tételt kell használ- nunk. Ilyenkor – ahelyett, hogy simán egymás után alkalmazzuk ezeket, lehetséges egyszerűbb, rövidebb, hatékonyabb, gazdaságosabb algoritmust tervezni, ha összeépítjük őket.

a. Másolással összeépítés

A másolás bármelyik programozási tétellel egybeépíthető. Ilyenkor az X_i bemeneti adatra való hivatkozást f(x_i)-re cseréljük.

Példa:

Adjuk meg egy számsorozat elemeinek négyzetgyökeiből álló sorozatot!

Megoldás: másolás + sorozatszámítás b. Megszámlálással összeépítés

A megszámlálást általában egy döntéssel, kiválasztással vagy kereséssel építhetjük össze.

Példa:

Döntsük el, hogy található-e az N elemű X sorozatban legalább K darab T tulajdonságú elem?

Adjuk meg a sorozat K-dik T tulajdonságú elemét!

Megoldás: megszámlálás + döntés + kiválasztás c. Maximumkiválasztással összeépítés

A maximumkiválasztást összeépíthetjük megszámlálással, kiválogatással.

Példa:

Hány darab maximumértékű elem van az adott sorozatban? Generáljuk ezen elemek indexei- nek sorozatát!

Megoldás: Lásd a MindenMaximumHelye(N, X, db, indexek) algoritmust.

d. Kiválogatással összeépítés

Olyan feladatoknál, amelyeknek esetében a feldolgozást csak az adott sorozat T tulajdonságú elemeire kell elvégeznünk, alkalmazható a kiválogatással történő összeépítés.

(21)

1.2. Lépések finomítása és optimalizálás

Bonyolultabb feladatok esetében a megfelelő algoritmus leírása nem könnyű feladat. Ezért célszerű először a megoldást körvonalazni, és csak azután részletezni. A feladat elemzése során sor kerül a bemeneti és kimeneti adatok megállapítására, a megfelelő adatszerkezetek kiválasz- tására és megtervezésére, a feladat követelményeinek szétválasztására. Következik a megoldási módszer megállapítása, a megoldás lépéseinek leírása és a lépések finomítása, vagyis az algoritmus részletes kidolgozása. Következik a helyesség bizonyítása és a bonyolultság kiértékelése.

A program megírását (kódolást) a tesztelés követi.

A lépések finomítása az algoritmus kidolgozását jelenti, amely a kezdeti vázlattól a végleges, precízen leírt algoritmusig vezet. Kiindulunk a feladat specifikációjából és fentről lefele tartó tervezési módszert alkalmazva újabb meg újabb változatokat dolgozunk ki, amelyek eleinte még tartalmaznak bizonyos, anyanyelven leírt magyarázó sorokat, amelyeket csak később írunk át standard utasításokkal. Így, az algoritmusnak több egymás utáni változata lesz, amelyek egy- re bővülnek egyik változattól a másikig.

1.2.1. Megoldott feladatok a. Eukleidész algoritmusa

Határozzuk meg két adott természetes szám legnagyobb közös osztóját (lnko) és legkisebb közös többszörösét (lkkt) Eukleidész algoritmusával.

Algoritmus Eukleidész_1(a, b, lnko, lkkt):

@ kiszámítjuk a és b lnko-ját { Bemeneti adatok: a, b. Kimeneti adatok: lnko, lkkt }

@ kiszámítjuk a és b lkkt-ét Vége(algoritmus)

Lépések finomítása: Ki kell dolgoznunk a kiszámítások módját. Ha a két szám egyenlő, akkor lnko az a szám lesz. Ha a kisebb, mint b, nincs szükség felcserélésre: az algoritmus elvégzi ezt az első lépésében. Ezután kiszámítjuk r-ben a és b egészosztási maradékát. Ha a maradék nem 0, a következő lépésben a-t felülírjuk b-vel, b-t r-rel, és újból kiszámítjuk a maradékot. Addig dolgozunk, amíg a maradék 0-vá nem válik. Az utolsó osztó éppen az lnko lesz. Az lkkt értékét megkapjuk, ha a és b szorzatát elosztjuk az lnko-val. Az eredeti két szám értékét az algoritmus

„tönkreteszi”, ezért szükséges ezeket elmenteni két segédváltozóba (x és y).

{ Bemeneti adatok: a, b. Kimeneti adatok: lnko, lkkt } x  a { szükségünk lesz a és b értékére az lkkt kiszámításakor } y  b

r  a mod b { kiszámítjuk az első maradékot } Amíg r ≠ 0 végezd el: { amíg a maradék nem 0 } a  b { az osztandót felülírjuk az osztóval } b  r { az osztót felülírjuk a maradékkal } r  a mod b { kiszámítjuk az aktuális maradékot } vége(amíg)

lnko  b { lnko egyenlő az utolsó osztó értékével } lkkt  x*y div lnko { felhasználjuk a és b másolatait } Vége(algoritmus)

(22)

Az algoritmust megvalósíthatjuk ismételt kivonásokkal. Amíg a két szám különbözik egy- mástól, a nagyobbikból kivonjuk a kisebbiket, és megőrizzük a különbséget. Az lnko az utolsó különbség lesz. Az lkkt-t ugyanúgy számítjuk ki, mint az előző változatban.

x  a { Bemeneti adatok: a, b. Kimeneti adatok: lnko, lkkt } y  b

Amíg a ≠ b végezd el:

Ha a > b akkor a  a - b különben b  b - a vége(ha) vége(amíg) lnko  a

lkkt  [x*y/lnko]

b. Prímszámok

Adva van egy nullától különböző természetes n szám. Döntsük el, hogy az adott szám prím- szám-e vagy sem!

Algoritmus Prím(n, válasz):

{ Bemeneti adat: n. Kimeneti adat: válasz }

@ Megállapítjuk, hogy n prímszám-e Ha n prímszám akkor

válasz  igaz különben

válasz  hamis vége(ha)

Lépések finomítása: Ki kell dolgoznunk azt a módot, ahogyan megállapíthatjuk, hogy a szám prím-e. A megoldás első változatában a prímszám definíciójából indulunk ki: egy szám akkor prím, ha pontosan két osztója van: 1 és maga a szám. Első ötletünk tehát az, hogy az algoritmus számolja meg az adott n szám osztóit, elosztva ezt sorban minden számmal 1-től n-ig. A döntés- nek megfelelő üzenetet az osztók száma alapján írjuk ki.

osztók_száma  0 { Bemeneti adat: n. Kimeneti adat: válasz } Minden osztó = 1,n végezd el:

Ha n mod osztó = 0 akkor

osztók_száma  osztók_száma + 1 vége(ha)

vége(minden)

válasz  osztók_száma = 2 Vége(algoritmus)

(23)

1.2.2. Az algoritmus optimalizálása

A lépésenkénti finomításnak elvben vége van, hiszen van egy helyesen működő algoritmusunk. De, miután teszteljük és figyelmesen elemezzük, rájövünk, hogy az algoritmust lehetsé- ges optimalizálni. Észrevesszük, hogy az osztások száma fölöslegesen nagy. Ezt a számot lehet csökkenteni, mivel ha 2 és n/2 között nincs egyetlen osztó sem, akkor biztos, hogy nincs n/2 és n között sem, tehát eldönthető, hogy a szám prím. Sőt elég a szám négyzetgyökéig keresni a lehetséges osztót, hiszen ahogy az osztó értékei nőnek a négyzetgyökig, az [n/osztó] hányados értékei csökkennek szintén a négyzetgyök értékéig. Ha egy, a négyzetgyöknél nagyobb osztóval elosztjuk az adott számot, hányadosként egy kisebb osztót kapunk, amit megtaláltunk volna előbb, ha létezett volna ilyen. Továbbá, a ciklus leállítható amint találtunk egy osztót és a válasz hamissá vált. A Minden típusú ciklust Amíg vagy Ismételd típusú ciklussal helyettesítjük. Mivel n nem változik a ciklus magjában, a négyzetgyök kiszámíttatását csak egyszer végezzük el. Azt is tudjuk, hogy az egyetlen páros prímszám a 2. Így elérhetjük, hogy a páros számok lekezelése után csak páratlan számokat vizsgáljunk, és ezeket csak páratlan osztókkal próbáljuk meg el- osztani. Ahhoz, hogy az algoritmusunk tökéletesen működjön akkor is, ha n = 1, a következő- képpen járunk el:

{ Bemeneti adat: n. Kimeneti adat: válasz }

Ha n = 1 akkor prím  hamis különben

Ha n páros akkor prím  n = 2 különben

prím  igaz osztó  3

négyzetgyök  [√𝑛] { a négyzetgyök egész része } Amíg prím és (osztó ≤ négyzetgyök) végezd el:

Ha n mod osztó = 0 akkor prím  hamis

különben

osztó  osztó + 2 vége(ha)

vége(amíg) vége(ha) vége(ha) válasz  prím Vége(algoritmus)

Ha ebben az algoritmusban felhasználjuk a matematikából ismert tulajdonságot, éspedig:

minden 5-nél nagyobb prímszám 6k ± 1 alakú, akkor a vizsgálandó számok száma tovább csök- kenthető. Mivel az előbbi állításból következik, hogy prímszámokat keresni csak 6 többszörö- seinél 1-gyel kisebb, illetve 1-gyel nagyobb számok között érdemes, a fenti algoritmus a követ- kezőképpen változik:

(24)

Algoritmus Prím(határ):

Ha n = 1 akkor prím  hamis különben

Ha n páros akkor prím  n = 2 különben

Ha n ≤ 5 akkor { n = 3}

prím  igaz különben

Ha ((n - 1) mod 6 ≠ 0) és ((n + 1) mod 6 ≠ 0) akkor prím  hamis

különben osztó  3

... { tovább ugyanaz, mint az előző algoritmusban } Továbbá, ismeretes, hogy a négyzetgyököt számoló függvény ismeretlen lépésszámban ha- tározza meg az eredményt, amely valós szám. Ezt elkerülendő, lemondunk a négyzetgyök ki- számításáról és az Amíg feltételét a következőképpen írjuk:

...

Amíg prím és (osztó * osztó  n) végezd el:

...

Így, nem dolgozunk valós számokkal és nem számítjuk ki fölöslegesen a négyzetgyököt.

Ha sok számról kell eldöntenünk, hogy prím-e, érdemes előbb létrehozni Eratosztenész szita-módszerével prímszámok sorozatát (megfelelő darabszámmal) és az algoritmusban csak ennek a sorozatnak elemeivel osztani.

Algoritmus Prímek(határ, prím):

{ határ-nál kisebb számokat vizsgálunk }

{ a generált prímszámokat a prím logikai tömb alapján lehet értékesíteni } Minden i=2,határ végezd el:

prími  igaz { még nincs kihúzva egy szám sem } vége(minden)

Minden i = 2, i * i < határ végezd el:

Ha prím_i akkor { ha i még nincs kihúzva } k  2 * i { az első kihúzandó szám (i-nek többszöröse) } Amíg k ≤ határ végezd el:

prímk  hamis { kihúzzuk a k számot } k  k + i { a következő kihúzandó többszöröse i-nek } vége(amíg)

(25)

1.2.3. A moduláris programozás alapszabályai

Az eredeti feladatot részfeladatokra bontjuk. Minden rész számára megtervezzük a megol- dást jelentő algoritmust. Ezek az algoritmusok legyenek minél függetlenebbek, de álljanak jól definiált kapcsolatban egymással. A részfeladatok megoldásainak összessége tartalmazza a feladat megoldási algoritmusát.

Moduláris dekompozíció: A moduláris dekompozíció a feladat több, egyszerűbb részfeladatra bontását jelenti, amely részfeladatok megoldása már egymástól függetlenül elvégezhető. A módszert általában ismételten alkalmazzuk, azaz a részfeladatokat magukat is felbontjuk. Ezzel lehetővé tesszük azt is, hogy a feladat megoldásán egyszerre több személy is dolgozzon. A módszer egy fával ábrázolható, ahol a fa csomópontjai az egyes dekompozíciós lépéseknek felelnek meg.

Moduláris kompozíció: Olyan szoftverelemek létrehozását támogatja, amelyek szabadon kombinálhatók egymással. Algoritmusainkat a már meglévő egységekből építjük fel.

Modulok tulajdonságai

Moduláris érthetőség: A modulok önállóan is egy-egy értelmes egységet alkossanak, megérté- sükhöz minél kevesebb „szomszédos” modulra legyen szükség.

Moduláris folytonosság: A specifikáció „kis” változtatása esetén a programban is csak „kis”

változtatásra legyen szükség.

Moduláris védelem: Célunk a program egészének védelme az abnormális helyzetek hatásaitól.

Egy hiba hatása egy – esetleg néhány – modulra korlátozódjon!

A modularitás alapelvei

− A modulokat nyelvi egységek támogassák: A modulok illeszkedjenek a használt progra- mozási nyelv szintaktikai egységeihez.

− Kevés kapcsolat legyen: Minden modul minél kevesebb másik modullal kommunikáljon!

− Gyenge legyen a kapcsolat: A modulok olyan kevés információt cseréljenek, amennyi csak lehetséges!

− Explicit interface használata: Ha két modul kommunikál egymással, akkor annak ki kell derülnie legalább az egyikük szövegéből.

− Információ elrejtés: Egy modul minden információjának rejtettnek kell lennie, kivéve, amit explicit módon nyilvánosnak deklaráltunk.

− Nyitott és zárt modulok: Egy modult zártnak nevezünk, ha más modulok számára egy jól definiált felületen keresztül elérhető, a többi modul ezt változatlan formában felhasz- nálhatja. Egy modult nyitottnak nevezünk, ha még kiterjeszthető, ha az általa nyújtott szolgáltatások bővíthetők vagy, ha hozzávehetünk további mezőket a benne levő adat- szerkezetekhez, s ennek megfelelően módosíthatjuk eddigi szolgáltatásait.

Az újrafelhasználhatóság igényei

A típusok változatossága: A moduloknak többféle típusra is működniük kell, azaz a művelete- ket több különböző típusra is definiálni kellene.

Egy típus, egy modul: Egy típus műveletei kerüljenek egy modulba.

(26)

1.3. Rendező algoritmusok

Összehasonlításon alapuló rendezések

Legyen egy n elemű a sorozat. Növekvően rendezett sorozatnak nevezzük a bemeneti soro- zat olyan permutációját, amelyben a₁ ≤ a₂ ≤ ... ≤ a_n.

1.3.1. Buborékrendezés (Bubble-sort)

A rendezés során páronként összehasonlítjuk a számokat és, ha a sorrend nem megfelelő, akkor az illető két elemet felcseréljük. Ha volt csere, a vizsgálatot újrakezdjük. Az algoritmus akkor ér véget, amikor az elemek páronként a megfelelő sorrendben találhatók, vagyis a sorozat rendezett. Mivel a sorozat első bejárása után legalább az utolsó elem a helyére kerül, és a ciklus- mag minden újabb végrehajtása után, jobbról balra haladva újabb elemek kerülnek a megfelelő helyre, a ciklus lépésszáma csökkenthető. Az is előfordulhat, hogy a sorozat végén levő elemek már a megfelelő sorrendben vannak, és így azokat már nem kell rendeznünk. Tehát, elegendő a sorozatot csak az utolsó csere helyéig vizsgálni.

Algoritmus BuborékRendezés(n, a):

k  n { Bemeneti adatok: n, a. Kimeneti adat: a rendezett a sorozat } Ismételd

nn  k - 1 rendben  igaz

Minden i = 1, nn végezd el:

Ha a_i > a_{i + 1} akkor rendben  hamis a_i ↔ a_{i + 1}

k  i { az utolsó csere helye }

vége(ha) vége(minden) ameddig rendben Vége(algoritmus)

1.3.2. Egyszerű felcseréléses rendezés

Ez a rendezési módszer hasonlít a buborékrendezéshez, de kötelezően elvégez minden páron- kénti összehasonlítást (míg a buborékrendezés bonyolultsága a legjobb esetben Ω(n), ez az algoritmus mindig O(n²) bonyolultságú). Ha egy elempár sorrendje nem megfelelő, felcseréli őket.

Algoritmus FelcserélésesRendezés(n, a):

{ Bemeneti adatok: n, a; Kimeneti adat: a rendezett a sorozat } Minden i = 1, n - 1 végezd el:

Minden j = i + 1, n végezd el:

Ha ai > aj akkor a_i ↔ a_j

vége(ha) vége(minden) vége(minden) Vége(algoritmus)

(27)

1.3.3. Minimum/maximum kiválasztásra épülő rendezés

Növekvő sorrendbe rendezés esetén kiválaszthatjuk a sorozat legkisebb elemét. Ezt az első helyre tesszük úgy, hogy felcseréljük az első helyen található elemmel. A következő lépésben hasonlóan járunk el, de a minimumot a második helytől kezdődően keressük. A továbbiakban ugyanezt tesszük, míg a sorozat végére nem érünk.

Algoritmus MinimumkiválasztásosRendezés(n, a):

{ Bemeneti adatok: n, a; Kimeneti adat: a rendezett a sorozat } Minden i = 1,n-1 végezd el:

indMin  i

Minden j = i+1, n végezd el:

Ha aindMin > aj akkor indMin  j vége(ha) vége(minden) a_i ↔ a_indMin vége(minden) Vége(algoritmus)

1.3.4. Beszúró rendezés

A beszúró rendezés hatékony algoritmus kisszámú elem rendezésére. Úgy dolgozik, ahogy bridzsezés közben a kezünkben levő lapokat rendezzük: üres bal kézzel kezdünk, a lapok fejjel lefelé az asztalon vannak. Felveszünk egy lapot az asztalról, és elhelyezzük a bal kezünkben a megfelelő helyre. Ahhoz, hogy megtaláljuk a megfelelő helyet, a felvett lapot összehasonlítjuk a már kezünkben levő lapokkal, jobbról balra. A bemeneti elemek helyben rendeződnek: a szá- mokat az algoritmus az adott tömbön belül rakja a helyes sorrendbe, belőlük bármikor legfeljebb csak állandónyi tárolódik a tömbön kívül. Amikor a rendezés befejeződik, az eredeti tömb tartalmazza a rendezett elemeket.

Algoritmus BeszúróRendezés(n, a):

{ Bemeneti adatok: n, a. Kimeneti adat: a rendezett a sorozat } Minden j = 2, n végezd el:

segéd  a_j { beszúrjuk a_j-t az a₁, ..., a_j–1 rendezett sorozatba } i  j - 1

Amíg (i > 0) és (a_i > segéd) végezd el:

a_i+1  a_i i  i - 1 vége(amíg) a_i+1  segéd vége(minden) Vége(algoritmus)

(28)

Lineáris rendezések

Az eddigiekben tárgyalt algoritmusok a legrosszabb esetben O(n²) időben rendeznek n ele- met. Ezek az algoritmusok a rendezéshez csak a bemeneti tömb elemein történő összehasonlí- tásokat használják, ezért ezeket az algoritmusokat összehasonlító rendezéseknek is nevezzük.

1.3.5. Leszámláló rendezés (ládarendezés, Binsort)

A most következő rendező algoritmus lineáris idejű. Ez az algoritmus nem az összehasonlí- tást használja a rendezéshez, hanem kihasználja a rendezendő sorozat bizonyos tulajdonságait, éspedig azt, hogy az elemek sorszámozható típusúak, olyan értékekkel, amelyek egy segédtömb indexei lehetnek.

A segédtömb i-edik elemében azt tartjuk nyilván, hogy hány darab i-vel egyenlő elemet ta- láltunk az eredeti tömbben. A lineáris feldolgozás után felülírjuk az eredeti tömb elemeit a se- gédtömb elemeinek értékei alapján.

Algoritmus LádaRendezés(a, n):

Minden i = 1, k végezd el: { Bemeneti adatok: n, a; Kimeneti adat: a } segéd_i  0

vége(minden)

Minden j = 1, n végezd el:

segéd_aj  segéd_{aj + 1} vége(minden)

q  0

Minden i = 1, k végezd el: { a segéd tömbnek k eleme van } Minden j = 1, segéd_i végezd el:

q  q + 1 { a segédi elemek összege n } a_q  i { tehát a feldolgozások száma n } vége(minden)

1.3.6. Számjegyes rendezés (radixsort)

Ha egész számokat tároló sorozatot szeretnénk rendezni, elképzelhetjük a számokat egymás alá írva és alkalmazhatjuk a fenti algoritmust rendre, minden számjegy-oszlopra. Ha a legnagyobb szám számjegyeinek darabszáma d, a sorozatot d-szer vizsgáljuk. A számjegyes rendezés először a legkevésbé fontos számjegy alapján rendez. A számokat az utolsó számjegyük alapján rendezzük oly módon, hogy ha csak ezt a számjegyet tekintjük, növekvő sorrendet lássunk.

Ezután a számokat újra rendezzük a második legkevésbé értékes számjegyük alapján. Ezt mind- addig végezzük, ameddig a számokat mind a d számjegy szerint nem rendeztük.

Algoritmus SzámjegyesRendezés(a, d):

Minden i = 1, d végezd el:

stabil leszámlálással rendezzük az a tömböt az i-edik számjegy szerint vége(minden)