Szakdolgozat. Miskolci Egyetem. Rendezési algoritmusok szemléltetése. Készítette: Fekete Enikő Programtervező informatikus szak

Szakdolgozat

Miskolci Egyetem

Rendezési algoritmusok szemléltetése

Készítette: Fekete Enikő Programtervező informatikus szak Témavezető: Dr. Házy Attila, egyetemi docens

Miskolc, 2013

Miskolci Egyetem Gépészmérnöki és Informatikai Kar Alkalmazott Matematikai Tanszék

Szám:

Szakdolgozat Feladat Fekete Enikő (YO0ILW) programtervező informatikus jelölt részére. A szakdolgozat tárgyköre: Tömb elemeinek rendezése a rendező algoritmusok segítségével, rendezési algoritmusok szemléltetése. A szakdolgozat címe: Rendezési algoritmusok szemléltetése A feladat részletezése: Rendezés tömbben, fontosabb definíciók ismertetése. Rendező algoritmusok leírása, tulajdonságaik vizsgálata. Néhány rendező algoritmus szemléltetése Java nyelven megírt program segítségével.

Témavezető(k): Dr. Házy Attila, egyetemi docens. A feladat kiadásának ideje: 2012. szeptember 26.

................................. szakfelelős 2

1. szükséges (módosítás külön lapon) A szakdolgozat feladat módosítása nem szükséges ......................

...........................

dátum

témavezető(k)

2. A feladat kidolgozását ellenőriztem: témavezető (dátum, aláírás):

konzulens (dátum, aláírás):

..............

.............

..............

.............

..............

.............

3. A szakdolgozat beadható: ......................

...........................

dátum

témavezető(k)

4. A szakdolgozat . . . . . . . . . . . . . . . . . . . szövegoldalt . . . . . . . . . . . . . . . . . . . program protokollt (listát, felhasználói leírást) . . . . . . . . . . . . . . . . . . . elektronikus adathordozót (részletezve) ................... . . . . . . . . . . . . . . . . . . . egyéb mellékletet (részletezve) ................... tartalmaz. ......................

...........................

dátum

témavezető(k)

5. bocsátható A szakdolgozat bírálatra nem bocsátható A bíráló neve: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................

...........................

dátum

szakfelelős

6. A szakdolgozat osztályzata a témavezető javaslata:

................

a bíráló javaslata:

................

a szakdolgozat végleges eredménye: . . . . . . . . . . . . . . . . Miskolc, . . . . . . . . . . . . . . . . . . . . . . . .

................................. a Záróvizsga Bizottság Elnöke 3

Tartalomjegyzék 1. Bevezetés 2. A rendező algoritmusok 2.1. Az algoritmusok és a rendező algoritmusok elmélete . . . . . . . 2.2. Beszúró rendezés . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1. A beszúró rendezés algoritmusának leírása . . . . . . . . 2.2.2. A beszúró rendezés struktogramja . . . . . . . . . . . . . 2.2.3. A beszúró rendezés folyamatábrája . . . . . . . . . . . . 2.2.4. A beszúró rendezés vizsgálata . . . . . . . . . . . . . . . 2.2.5. Példa a beszúró rendezésre . . . . . . . . . . . . . . . . . 2.3. Összefésülő rendezés . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Az összefésülő rendezés algoritmusának leírása . . . . . . 2.3.2. Az összefésülő rendezés struktogramja . . . . . . . . . . 2.3.3. Az összefésülő rendezés vizsgálata . . . . . . . . . . . . . 2.4. Gyorsrendezés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1. A gyorsrendezés algoritmusának leírása . . . . . . . . . . 2.4.2. A gyorsrendezés struktogramja . . . . . . . . . . . . . . 2.4.3. A gyorsrendezés vizsgálata . . . . . . . . . . . . . . . . . 2.5. Buborékrendezés . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1. A buborékrendezés algoritmusának leírása . . . . . . . . 2.5.2. A buborékrendezés struktogramja . . . . . . . . . . . . . 2.5.3. A buborékrendezés folyamatábrája . . . . . . . . . . . . 2.5.4. A buborékrendezés vizsgálata . . . . . . . . . . . . . . . 2.5.5. Példa a buborékrendezésre . . . . . . . . . . . . . . . . . 2.6. Javított Buborékrendezés . . . . . . . . . . . . . . . . . . . . . . 2.6.1. A javított buborékrendezés algoritmusának leírása . . . . 2.6.2. A javított buborékrendezés struktogramja . . . . . . . . 2.6.3. A javított buborékrendezés folyamatábrája . . . . . . . . 2.6.4. A javított buborékrendezés vizsgálata . . . . . . . . . . . 2.6.5. Példa a javított buborék rendezésre . . . . . . . . . . . . 2.7. Shell rendezés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7.1. A shell rendezés algoritmusának leírása . . . . . . . . . . 2.7.2. A shell rendezés struktogramja . . . . . . . . . . . . . . 2.7.3. A shell rendezés vizsgálata . . . . . . . . . . . . . . . . . 2.8. Minimum kiválasztásos rendezés . . . . . . . . . . . . . . . . . . 2.8.1. A minimum kiválasztásos rendezés algoritmusának leírása 2.8.2. A minimum kiválasztásos rendezés struktogramja . . . . 2.8.3. A minimumkiválasztásos rendezés folyamatábrája . . . .

6

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 10 11 11 12 12 13 14 14 15 15 15 16 17 18 18 18 19 19 20 20 21 21 22 23 23 23 25 25 26 26 26 27 27 28

4

2.8.4. A minimum kiválasztásos rendezés vizsgálata . 2.8.5. Példa a minimum kiválasztásos rendezésre . . 2.9. Leszámláló rendezés . . . . . . . . . . . . . . . . . . . 2.9.1. A Leszámláló rendezés algorimusának leírása . 2.9.2. A leszámláló rendezés struktogramja . . . . . 2.9.3. A leszámláló rendezés vizsgálata . . . . . . . . 2.10. Edényrendezés . . . . . . . . . . . . . . . . . . . . . . 2.10.1. A edényrendezés algoritmusának leírása . . . . 2.10.2. Az edényrendezés struktogramja . . . . . . . . 2.10.3. Az edényrendezés vizsgálata . . . . . . . . . . 3. Fejlesztői dokumentáció 3.1. A rendezőalgoritmusok megvalósítása java-ban 3.2. A rendező algoritmusok implementációja . . . 3.2.1. Beszúró rendezés . . . . . . . . . . . . 3.2.2. Minimumkiválasztásos rendezés . . . . 3.2.3. Buborékrendezés . . . . . . . . . . . . 3.2.4. Javított buborékrendezés . . . . . . . . 3.3. A program bemutatása . . . . . . . . . . . . . 3.3.1. Kezdő ablak . . . . . . . . . . . . . . . 3.3.2. Beszúró rendezés . . . . . . . . . . . . 3.3.3. Minimumkiválasztásos rendezés . . . . 3.3.4. Buborékrendezés . . . . . . . . . . . . 3.3.5. Javított buborékrendezés . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

28 28 30 30 31 31 31 32 32 32

. . . . . . . . . . . .

33 33 34 34 35 35 36 36 36 37 39 40 42

4. Összefoglalás

44

Irodalomjegyzék

45

Adathordozó használati útmutató

46

5

1. fejezet Bevezetés Az algoritmusokat nem csupán a számítástechnikában használjuk, hanem nélkülözhetetlenek a matematikában, sőt a mindennapi életünkben is. De mi is az az algoritmus? Egyszerűen egy feladat megoldásához szükséges, meghatározott lépések sorozataként fogalmazhatjuk meg. A mindennapi életünkben használt algoritmus lehet például kávéfőzés, sütés-főzés során követett recept utasításainak végrehajtása. A matematikában is jelentős szerepe van az algoritmusoknak. Egy-egy feladatot különböző algoritmusok alkalmazásával oldhatunk meg, tehát a matematikában az algoritmusok megadják, hogy milyen módon és sorrendben végezzük el a számolási eljárásokat, hogy megkapjuk a helyes végeredményt. Természetesen, egy feladat megoldásához, lehet hogy több algoritmust is fel kell használnunk hozzá. Az algoritmusok az informatikában: A számítógépes programok is algoritmusokkal vezérlik a számítógépeket. A számítógépes szoftverek mindegyike algoritmusok, illetve az ezekhez kapcsolódó adatok sokaságából áll. Az algoritmusokat különbözőképpen is csoportosíthatjuk. Például végesség szerint léteznek véges algoritmusok, illetve nem véges (nemdeterminisztikus) algoritmusok. A gyakorlati életben a véges számú lépések sorozataként kifejezett algoritmusokat használjuk, mivel ezek vezetnek egy-egy feladat elvégzéséhez, a megoldás megtalálásához. De hogyan írhatunk le egy-egy algoritmust? Az algoritmusok leírásánál nincsenek kötött szabályok, mert nincs egységes kódrendszere. Akár természetes, emberi nyelven mondatszerűen is leírhatunk egy-egy algoritmust, de rögtön le is programozhatjuk egy adott programozási nyelven. Megadhatjuk az algoritmusokat pszeudokód "álkód" formájában is. Ez egy mesterséges formális nyelv, amely hasonlít a programozási nyelvekhez, de nem konkrét programozási nyelv. Átmenetet képez a mondatszerű leírás és a ténylegesen használt programkód között. Ezek közül lényegtelen, hogy hogyan írjuk le az algoritmusokat, viszont egyértelműnek kell lenniük minden kérdés tekintetében, és előre meghatározott bemeneti és kimeneti ponttal/pontokkal kell rendelkezniük. Algoritmus leíró eszközök lehetnek továbbá a folyamatábrák és a struktogramok is. A folyamatábrával (flowchart)részletesen tudjuk ábrázolni a program folyamatát, viselkedését. Struktogramal (Chapin-chart, alkotójáról kapta a nevét) struktúrált programokat tu-

6

dunk ábrázolni. Az algoritmusokkal kapcsolatban meg kell említenünk a hatékonyságukat is, hogy ennek tudatában válasszuk ki, hogy melyik algoritmus lesz nekünk a megfelelő a programozás során. Egy algoritmus hatékonyságát a lépésszám és a memóriaigény határozza meg. Az algoritmus lépésszáma alatt az algoritmust meghatározó műveletek számát értjük, a bemenet hosszának függvényében. Egy program/szoftver megírása során is szükségünk van az algoritmusok alapos ismeretére. Alkalmazásukkal nem csupán helyes, hanem megfelelő teljesítményű lehet a programunk/szoftverünk. Amikor programot írunk, alkothatunk saját algoritmusokat egy-egy probléma megoldására, illetve alkalmazhatunk ismert algoritmusokat, amelyeket már korábban megalkottak az adott problémára. Természetesen, ha nincs ilyen, vagy nem elérhető, akkor ezt nekünk kell megoldanunk. Az előre megalkotott algoritmusok általában alap problémákat oldanak meg, amelyek sokszor előfordulnak programok írása során. Ilyen alap probléma lehet például, amikor szükségünk van egy rendezett tömbre a programozás során, amely eddig még rendezetlen volt. Ekkor használnunk kell valamelyik rendező algoritmust. Ezeknek az algoritmusoknak a lépései ismertek, már megalkották őket. Többféle rendező/rendezési algoritmusokat alkottak meg. Ezek az algoritmusok eltérő módszerrel rendezik az input tömböt, ezért a futásidejük, lépésszámuk illetve a memóriaigényük eltér/eltérhet. A szakdolgozatom feltételez némi előismeretet a pszeudokódokkal, a struktogramokkal és a folyamatábrákkal kapcsolatban, mivel feladatomként a rendezőalgoritmusokat választottam, ezért az előbb említett eszközök általános megalkotásának módját nem fogom ismertetni, csak felhasználom őket a rendezések bemutatása során. A szakdolgozatomat úgy írtam meg, hogy minél jobban a rendezőalgoritmusok témakörére koncentrálódjon. Az elkövetkező témakifejtésben ismertetni fogom a rendező/rendezési algoritmusokat, különböző leíró eszközök segítségével, használatukat, hatékonyságukat. Ezek közül pedig néhány rendező algoritmust szemléltetek JAVA nyelven megírt program segítségével.

A kutató munka a Miskolci Egyetem stratégiai kutatási területén működő Mechatronikai és Logisztikai Kiválósági Központ keretében valósult meg.

7

2. fejezet A rendező algoritmusok A bevezetés után ebben a fejezetben olyan rendező algoritmusokat ismertetek, amelyek inputként tömböt kapnak, és az elemeit növekvő sorrendben rendezik, majd visszaadják a rendezett tömböt. Ismertetni fogom a jellemzőiket, pszeudokódjukat, elkészítem a struktogramjukat, néhány algoritmusnak a folyamatábráját is, és megvizsgálom a tulajdonságaikat. Először azokat a fontos definíciókat, meghatározásokat és leírásokat ismertetem, amelyek elengedhetetlenek ha a rendező algoritmusokkal foglalkozunk. Ezeket és a pszeudokódokat a Házy Attila, Nagy Ferenc - Adatstruktúrák és algoritmusok (2011) című jegyzet alapján ismertetem.

2.1. Az algoritmusok és a rendező algoritmusok elmélete Az algoritmusok olyan eszközök, amelyekkel pontosan meghatározott számítási feladatokat oldhatunk meg. Az algoritmusok előre meghatározott bemeneti és kimeneti ponttal/pontokkal rendelkeznek tehát az algoritmusokat felfoghatjuk az ezek közötti kívánt kapcsolat leírásaként. Például a rendező algoritmusok esetén a bemeneti és kimeneti pont közötti kívánt kapcsolat a rendezés művelete. Egy rendezett tömbre a gyakorlatban sokszor van szükség, ezért találkozhatunk olyan sokféle, már megalkotott rendező algoritmussal. Ezek közül nem választhatunk optimálisat, mivel különböző tömbök esetén különböző rendezési algoritmusok lehetnek a leghatékonyabbak. Néhány definíció és leírás, amelyekre a rendező algoritmusok ismertetése során szükségünk lesz: 2.1. definíció. Az algoritmus: Az algoritmus egy meghatározott számítási eljárás, a számítási probléma megoldásieszköze. Az algoritmus tulajdonságai: Az algoritmus bemenetére/inputjára adjuk a problémát, a feladat kiinduló adatait, a 8

2.1. Az algoritmusok és a rendező algoritmusok elmélete kimenetén pedig megkapjuk a végeredményt. Outputként megjelenhet az is, hogy nincs végeredmény (néhány probléma esetén az is lehet megoldás, hogy nincs eredmény). Az algoritmus leírja a megfelelő műveleteket, megfelelő sorrendben, a kívánt eredmény eléréséhez. Az algoritmusnak véges idő alatt, vagyis véges sok lépésben véget kell érnie. Az algoritmust megadhatjuk pszeudokóddal vagy folyamatábrával, de akár szemléltethetjük struktogrammal is. Az algoritmus jellemző vonásai: - A kiinduló adatok lehetséges halmaza: az input adatok halmaza. - A lehetséges eredmények halmaza: az output adatok halmaza (az input határozza meg). - A lehetséges közbenső eredmények halmaza: az algoritmus futása során keletkező adatok halmaza. - A kezdési szabály: az algoritmus első műveletét határozza meg. - A közvetlen átalakítási szabályok: azokat a szabályokat tartalmazza, amelyeket az algoritmus futása során felhasználhat. - A befejezési szabály: az a szabály, ami meghatározza az algoritmus végét. - Az eredmény kiolvasási szabálya: az a szabály, amiből kiderül az eredmény helye és típusa. 2.2. definíció. A reláció: Valamely A halmaz esetén a ρ ⊂ A × A részhalmazt az A halmazon értelmezett relációnak nevezzük. Azt mondjuk, hogy az A halmaz a és b eleme a ρ relációban van, ha (a, b) ∈ ρ. Röviden ezt így írjuk: aρb. 2.3. definíció. A rendezési reláció: A ρ relációt rendezési relációnak nevezük, ha 1. Reflexív, azaz aρa ∀a ∈ A esetén; 2. Ha aρb és bρa, akkor a = b; 3. Tranzitív, azaz ha aρb és bρc, akkor aρc; 4. Antiszimmetrikus, azaz vagy az aρb vagy a bρa áll fenn ∀a, b ∈ A esetén. Olyan adattípusokat tudunk rendezni, amelyeknél értelmezve van egy rendezési reláció. A rendező algoritmusok valós számokon (általában egészeken) hajtanak végre kisebb egyenlő relációt, azaz a bemenő tömb elemeit rendezi növekvő sorrendbe. A rendező algoritmusokat különböző igények szerint alkották/alkothatjuk meg. Ezek az igények lehetnek például: - Helyben rendezés: Az algoritmus outputja az input helyén jelenik meg, legfeljebb konstans méretű többletmemóriát igénybevéve. - Értelemszerűen a rendezési idő legyen minél rövidebb, azaz az algoritmus minél kevesebb lépésszámmal érjen véget. - Adaptivitás: az algoritmus használja ki a input elemek között már meglévő rendezettséget. - Stabilitás: az azonos elemek esetén az algoritmus őrizze meg az eredeti sorrendet. - Az összehasonlítás műveletén alapuljon, de az is lehet elvárás, hogy az algoritmus ne 9

2.2. Beszúró rendezés használja az összehasonlítás műveletét. 2.4. definíció. Oszd meg és uralkodj elv: Az oszd meg és uralkodj elv egy algoritmus tervezési stratégia. Ez a stratégia a kiinduló problémát kisebb méretű, független, hasonló részproblémákra bontja, amelyeket rekurzívan old meg. A kisebb méretű részproblémák megoldásait egyesítve kapja meg az eredeti probléma megoldását. Pszeudokód ("álkód"): A pszeudokód az algoritmusok leírására használt mesterséges formális nyelv. Változókból és néhány állandó jelentésű szóból áll. Mivel a szerkezete hasonlít a számítógépes programozási nyelvekre, ezért ez alapján már könnyebb lehet az algoritmus implementálása. Bármilyen leíró eszközt alkalmazhatunk, amely világosan, tömören megadja az algoritmust. Folyamatábra (flowchart): Az algoritmust egy irányított gráfként írja le, amely csomópontokból (utasítás, döntés, gyűjtő) és a csomópontokat összekötő élekből áll. Egyetlen induló éllel és egyetlen befejezőéllel rendelkezik, illetve az induló élből bármelyik csomópont és a befejező él is elérhető. Előnye: az algoritmus lépéseinek követésére jól használható eszköz. Hátránya: nagy terjedelmű, javítása nehézkes. Struktogram(Chapin-chart): A struktogrammal szemléletesen ábrázolhatóak az algoritmusok. A struktogram egymáshoz illesztett téglalapokból áll, nincsenek nyilak. Felülről lefelé haladva olvassuk. Utasításokból, ciklusokból és feltételekből épül fel. Hátránya: csak struktúrált programok írásásra alkalmas. A folyamatábrához hasonlóan az ábrázolása terjedelmes, és a javítása is nehézkes.

2.2. Beszúró rendezés Bemenet: n számot tartalmazó sorozat (n hosszúságú tömb): (a1 , a2 , ..., an ) Kimenet: A bemenő sorozat olyan (a01 , a02 , ..., a0n ) permutációja, amelyre teljesül, hogy: a01 ≤ a02 ≤ ... ≤ a0n . A beszúró rendezés alapelve az, hogy veszük sorba a bemeneti tömb elemeit (kulcsokat) a második elemtől kezdve (az első elem önmagában már rendezett) egyenként, és a sorozat eleje felé haladva összehasonlítások révén beszúrja a megfelelő helyre. Tehát az algoritmus során az i-edik (2 ≤ i ≤ n) kulcs helyének megkeresése esetén a sorozat első része az a01 kulcstól az a0i−1 kulcsig rendezett.

10

2.2. Beszúró rendezés

2.2.1. A beszúró rendezés algoritmusának leírása A beszúró rendezés pszeudokódját a Beszúró-Rendezés eljárásban írom le, amelynek paramétere (bemenete) egy n hosszúságú, a rendezendő elemek sorozatát tartalmazó A[1...n] tömb. A kódban a hossz[A] kifejezés az A tömb elemeinek száma, ami pontosan n. Az algoritmus az elemeket helyben rendezi, tehát a kimenet az A tömb lesz, csak rendezett elemekkel. Beszúró-Rendezés(A) //Input paraméter: A - a rendezendő tömb //Output paraméter: A - a rendezett tömb 1. 2. 3. 4. 5. 6. 7. 7. 8.

FOR j ← 2 TO hossz[A] DO kulcs ← Aj //Beszúrás az A1...j−1 rendezett sorozatba. i←j−1 WHILE i > 0 és Ai > kulcs DO Ai+1 ← Ai DEC(i) Ai+1 ← kulcs RETURN (A)

2.2.2. A beszúró rendezés struktogramja

2.1. ábra. A beszúró rendezés struktogramja

11

2.2. Beszúró rendezés

2.2.3. A beszúró rendezés folyamatábrája

2.2. ábra. A beszúró rendezés folyamatábrája

2.2.4. A beszúró rendezés vizsgálata A beszúró rendezés helyben rendező eljárás, mert a bemenő adatok tömbjén kívül csak állandó számú változókra van szüksége a rendezéshez. Hatékonyság: egy algoritmus futási idejétt a meghatározó műveleteinek száma határozza meg. A rendező algorimusok esetén ez általában az összehasonlítások és cserék száma. A beszúró rendezés futásideje függ a bemeneti tömb rendezettségétől, tehát 2 egyenlő nagyságú tömb rendezése eltérő futásidőt eredményezhet. Ennél a rendezésnél az összehasolítások száma állandó (a tömb méretétől függ). A cserék száma függ a bemeneti tömb rendezettségétől. A legjobb eset, amikor a bemenő tömb már rendezett, a legrosszabb eset, pedig értelemszerűen, ha a tömb fordított sorrendben rendezett, ugyanis ekkor (n ∗ (n − 1))/2 a cserék száma, mert az elemek úgy kerülnek a helyükre, hogy a többit jobbra toljuk a sorozatban. Tehát a beszúró rendezés időigénye T (n) = Θ(n2 ).

12

2.3. Összefésülő rendezés

2.2.5. Példa a beszúró rendezésre Vegyünk egy n elemszámú tömböt. Esetünkben legyen n = 5. És a tömb, amit beszúró rendezéssel rendezünk az legyen: A = (9, 15, 6, 11, 6). 1. lépés: Az első lépésben a vizsgált kulcs a tömb 2. eleme, azaz a 15-ös. Összehasonlítjuk az előtte álló elemmel, ami esetünkben a 9-es. Mivel a kulcs nem kisebb mint 9, ezért a helyén hagyjuk és vizsgáljuk a következő kulcsot. A tömbünk tehát az 1.lépés után: A = (9, 15, 6, 11, 6) . 2. lépés: A vizsgált kulcsunk a tömb 3. eleme, azaz a 6-os. A tömb eleje felé haladva összehasonlítjuk a 2. elemmel, ami a 15-ös. 3.lépés: Mivel a kulcs kisebb mint a 15 ezért felcseréljük, és haladunk tovább az összehasonlítással. 4.lépés: A kulcs még mindig a 6-os. Összehasonlítjuk a tömb 1. elemével, ami a 9-es. 5.lépés: Mivel a 6-os kisebb, mint a 9-es, ezért felcseréljük. Mivel elértük a tömb elejét, ezért vesszük a következő kulcsot. A tömbünk tehát a 5.lépés után: A = (6, 9, 15, 11, 6). 6.lépés: A következő vizsgált kulcsunk a tömb 4. eleme, azaz a 11-es. A tömb eleje felé haladva összehasonlítjuk az elemekkel. Először a 3. elemmel a 15-tel hasonlítjuk össze. 7.lépés: Mivel a kulcs kisebb a 15-nél, ezért felcseréljük, és haladunk tovább. 8.lépés: A kulcsot (11-et) összehasonlítjuk a tömb 2. elemével a 9-el. Mivel a kulcs nem kisebb mint a tömb 2. eleme, ezért megtaláltuk a helyét. Tehát vesszük a következő kulcsot. A tömbünk tehát a 10.lépés után: A = (6, 9, 11, 15, 6). 9.lépés: A következő vizsgált kulcsunk a tömb 5. (utolsó) eleme a 6-os. A tömb eleje felé haladva összehasonlítjuk az elemekkel. Először a 4. elemmel a 15-tel hasonlítjuk össze. 10.lépés: Mivel a kulcs kisebb, mint a tömb 4. eleme, felcseréljük őket, és haladunk tovább az összehasonlítással. 11.lépés: A kulcsot (6-ot) tehát összehasonlítjuk a 3. elemmel a 11-el hasonlítjuk össze. 12. lépés: Mivel a kulcs kisebb, mint a tömb 3. eleme, ezért felcseréljük, és haladunk tovább és a 2. elemmel hasonlítjuk össze. 13.lépés: A kulcsot (6-ot) tehát összehasonlítjuk a 2. elemmel a 9-el hasonlítjuk össze. 14.lépés: Mivel a kulcs kisebb, mint a tömb 2. eleme, ezért felcsréljük őket, és haladunk tovább és az 1. elemmel hasonlítjuk össze. 15.lépés: A kulcsot (6-ot) tehát összehasonlítjuk a 1. elemmel a 6-al hasonlítjuk össze. Mivel a kulcs nem kisebb, mint a tömb 1. eleme, ezért megtaláltuk a helyét és nem haladunk tovább. A tömbünk tehát a 15.lépés után: A = (6, 6, 9, 11, 15). Mivel az utolsó kulcsot is beszúrtuk a tömbbe, ezért megkaptuk a rendezett tömböt.

13

2.3. Összefésülő rendezés

2.3. Összefésülő rendezés Az összefésülő rendezés két rendezett tömbből indul ki. A két rendezett tömbből az összefésülés műveletével egy új rendezett tömböt állít elő. Az összefésülés művelete: Mindkét tömbből vesszük az első elemet. Összehasonlítjuk ezt a két elemet, majd a kisebbet beírjuk az eredménytömb első szabad helyére. Azt az elemet, amelyik a nagyobb volt még nem írjuk be, hanem a másik tömbből vesszük hozzá a soron következő elemet, és ezzel újra összehasonlítjuk, majd a kisebbet beírjuk az eredménytömb következő üres helyére. Ezt a folyamatot addig ismételjük, ameddig az egyik tömbünk ki nem ürül. A másik tömb fennmaradó elemeit pedig sorra beírjuk az eredménytömb végéhez. Ha két nem üres tömb a bemeneti tömb, akkor eredménytömb nem lehet azonos egyikkel sem, tehát ez az eljárás nem helyben végzi a tömbök összefésülését. Az összefésülő rendezés során használt ÖSSZEFÉSÜL (A, p, q, r) algoritmus a következő: Összefésüli az Ap...q és az Aq+1...r résztömböket, és ezt visszamásolja az Ap...r helyre.

2.3.1. Az összefésülő rendezés algoritmusának leírása

Összefésülő Rendezés (A, p, r) //Input paraméter: A - a tömb, melynek egy részét, vagy égészét rendezni kell // p - a rendezendő rész kezdőindexe, // r - a rendezendő rész végindexe. // Output paraméter: A - a rendezett réssze rendelkező tömb 1. 2. 3. 4. 5. 6.

IF p < r   THEN q ← p+r 2 Összefésülő Rendezés (A, p, q) Összefésülő Rendezés (A, q + 1, r) Összefésül (A, p, q, r) RETURN (A)

2.5. megjegyzés. Ha ezzel az algorimussal az egész tömböt rendezni akarjuk, akkor a következű utasítással hívjuk meg: Összefésülő Rendezés (A, 1, hossz[A]) .

14

2.4. Gyorsrendezés

2.3.2. Az összefésülő rendezés struktogramja

2.3. ábra. Összefésülő rendezés struktogramja

2.3.3. Az összefésülő rendezés vizsgálata Az összefésülő rendezés oszd meg és uralkodj típusú algoritmus. Felosztás: A tömböt két egyenlő elemszámú résztömbre osztja,  az eredeti tömb páros  p+r elemszá p+rha mú. Ha páratlan, akkor az első rész elemszáma: 2 , a második részé: 2 + 1. Uralkodás: Rekurzív összefésüléses módon mindkét résztömböt rendezzük. Egyesítés: a két részsorozatot összefésüljük. Az összefésülő rendezés időigénye: T (n) = Θ(n · logn). Előnye, hogy nagyon nagy sorozatokra is alkalmazható. Hátránya, hogy helyben nem végezhető. Az algoritmus gyakorlati használatakor a valóságban nem csak két bemenő sort használunk, hanem több bemenő sort, amelyek mindegyikét egyszerre, egy menetben fésüljük össze.

2.4. Gyorsrendezés A gyorsrendezést C. A. R. Hoare fejlesztette ki 1960-ban az Elliott Brothers angol számítógépgyártónak. A gyorsrendezés rekurzív algoritmus. Az egyik legnépszerűbb rendezési algoritmus, amely átlagos esetben gyorsabb, a többi algoritmusnál, viszont hátránya hogy a legrosszabb esetben lassú, és nem stabil rendezés. Rekurzív algoritmus, kettéosztja (egy feloszt algoritmussal) a rendezendő listát egy 15

2.4. Gyorsrendezés adott elemnél kisebb és nagyobb elemekre, majd a részekre külön-külön meghívja a gyorsrendezést. Bemenet: A - a rendezendő tömb, amelynek egy részét (vagy egészét) rendezni kell, p - a rendezendő rész kezdőindexe, r - a rendezendő rész végindexe. Kimenet: A a rendezett résszel rendelkező tömb.

2.4.1. A gyorsrendezés algoritmusának leírása Gyorsrendezés eljárás a bemenő tömb egy részét, vagy egészét rendezi. Ha az egész bemenő tömböt rendezni szeretnénk, akkor a kezdőhívás: Gyorsrendezés(A, 1, hossz[A]). Gyorsrendezés(A, p, r) 1. 2. 3. 4.

IF p < r THEN q ← Feloszt(A, p, r) Gyorsrendezés(A, p, q − 1) Gyorsrendezés(A, q + 1, r)

A tömb felosztása a Feloszt eljárással: Feloszt (A, p, r, x, q) // Input paraméter: A - a tömb, // p - a felosztandó rész kezdőindexe, // r - a felosztandó rész végindexe, // x - előre megadott érték, a felosztást szabályozza. // Output paraméter: A - a megváltozott tömb, // q - a felosztás határa Ap...q , Aq+1...r . 1. i ← p − 1 2. j ← r + 1 3. WHILE igaz DO 4. REPEAT j ← j − 1 5. UNTIL Aj ≤ x 6. REPEAT i ← i + 1 7. UNTIL Ai ≥ x 8. IF i < j 9. THEN Csere Ai ↔ Aj 10. ELSE q ← j 11. RETURN (A, q)

16

2.4. Gyorsrendezés

2.4. ábra. Gyorsrendezés struktogramja

2.4.2. A gyorsrendezés struktogramja A gyorsrendezésnél használt FELOSZT algoritmus struktogramja:

2.5. ábra. A feloszt algoritmus struktogramja

17

2.5. Buborékrendezés

2.4.3. A gyorsrendezés vizsgálata A gyorsrendezés helyben rendező eljárás, mert a bemenő adatok tömbjén kívül csak állandó számú változókra van szüksége a rendezéshez. A beszúró rendezéshez hasonlóan a legrosszabb esetben az időigénye Θ(n2 ), átlagosan azonban Θ(n · log n) futási idejű, ami miatt népszerű algoritmus nagy adathalmazok rendezéséhez. A gyorsrendezés összehasonlító, de nem stabil rendezés. A gyorsrendezés átlagos lépésigénye Θ(n · log n), ami megegyezik a kupacrendezés és az összefésülő rendezés átlagos, illetve legrosszabb lépésigényével.

2.5. Buborékrendezés A buborékrendezést főleg oktatásban használjuk, mivel a sok összehasonlítás és csere miatt lassú. A tömb első két elemétől kiindulva minden lépésben egymás mellett álló 2 elemet veszünk egy „buborékba” és ezeket hasonlítjuk össze, és ha nem megfelelő sorrendben vannak, akkor felcseréljük őket. Majd minden lépésben egy elemmel jobbra tolva, újabb 2 elemet teszünk a "buborékunkba" és így hasonlítgatjuk össze kettesével az elemeket. A "buborék" jobbra tolását addig ismételjük, míg a "buborékban" megvizsgált 2 elem a tömb utolsó 2 eleme nem lesz. Ha ez megtörtént, akkor a tömb első két elemétől kezdve újra elindítjuk a "buborékot", de már nem a tömb végéig, hanem az (n − 1). elemig (n a tömb elemszáma). Tehát az algoritmus során többször is végigmegyünk a tömbön,a második körben, már csak az (n − 1). elemig haladunk, a harmadik körben pedig az (n − 2). Az algoritmus ezt addig ismétli, amíg el nem értük az utolsó (n − 1). kört. Ekkor a tömb már rendezett, tehát az algoritmus leáll.

2.5.1. A buborékrendezés algoritmusának leírása Buborékrendezés(A) //Input paraméter: A - a rendezendő tömb (N elemszámú) //Output paraméter: A - A rendezett tömb 1. 2. 3. 4. 5.

FOR i ← N DOWNTO 2 DO FOR j ← 1 TO i − 1 DO IF A[j] > A[j+1] THEN Csere (A[j], A[j+1]) RETURN (A)

18

2.5. Buborékrendezés

2.5.2. A buborékrendezés struktogramja

2.6. ábra. A buborékrendezés struktogramja

2.5.3. A buborékrendezés folyamatábrája

2.7. ábra. A buborékrendezés folyamatábrája

19

2.5. Buborékrendezés

2.5.4. A buborékrendezés vizsgálata Ha jól megfigyeljük az eljárást, akkor először a legnagyobb elem kerül a helyére, majd a második legnagyobb, és így tovább. Az algoritmusnak nagy az időigénye, mivel sok összehasonlítást kell elvégeznünk. Egy n elemű tömb esetén az összehasonlítások száma minden esetben: n(n−1)/2. A cserék száma pedig függ a bemeneti tömb rendezettségétől. A legrosszabb eset, hogyha a tömb fordítva rendezett, ekkor minden összehasonlításnál szükség van cserére, ebben az esetben a cserék száma is n(n−1)/2. Az algoritmus műveletigénye, az összehasonlítások és cserék összege: (n(n − 1)/2) + (n(n − 1)/2) = n(n − 1) Tehát T (n) = Θ(n2 ).

2.5.5. Példa a buborékrendezésre Vegyünk egy n elemszámú tömböt. Esetünkben legyen n = 5. És a tömb, amit buborékrendezéssel rendezünk az legyen: A = (5, 8, 3, 5, 9). 1. lépés: A" buborékunkal" elindulunk a tömb elejétől és elvégezzük az összehasonlításokat, és a szükséges cseréket. Tehát először az első két elemet hasonlítjuk össze. Tehát a "buborékunk" jelenleg így néz ki (5, 8). Ezek megfelelő sorrendben vannak úgyhogy továbblépünk. 2. lépés: A következő két elem, amit összehasonlítunk a 2. és a 3. elem. Tehát a "buborék": (8, 3). Ezek nincsenek megfelelő sorrendben. 3. lépés: Csere. A "buborék" két elemét felcseréljük egymással: így a "buborék":(3, 8) lesz. Így már megfelelő a sorrend, tehát továbbvisszük a "buborékot". A tömbünk tehát az 3.lépés után: A = (5, 3, 8, 5, 9) 4. lépés: A következő két elem, amit összehasonlítunk a 3. és a 4. elem. Tehát a "buborék": (8, 5). Ezek nincsenek megfelelő sorrendben. 5. lépés: Csere. A "buborék" két elemét felcseréljük egymással: így a "buborék":(5, 8) lesz. Így már megfelelő a sorrend, tehát továbbvisszük a "buborékot". A tömbünk tehát az 5.lépés után: A = (5, 3, 5, 8, 9) 6.lépés: A következő két elem, amit összehasonlítunk a 4. és a 5. elem. Tehát a "buborék": (8, 9). Ezek megfelelő sorrendben vannak. Elértük az utolsó elemet, és kezdjük előről az algoritmust, de mostmár a "buborékkal" csak az utolsó előtti elemig megyünk. Mert az, hogy végighaladtunk egyszer a tömbön azt eredményezi, hogy az utolsó elem (a legnagyobb) helyre került. 7.lépés: Mivel ez még csak a 2. kör, ezért a " buborékunkal" újra elindulunk a tömb elejétől. Tehát a két elem, amit összehasonlítunk a 1. és a 2. elem. Tehát a "buborék": (5, 3). Ezek nincsenek megfelelő sorrendben. 8. lépés: Csere. A "buborék" két elemét felcseréljük egymással: így a "buborék":(3, 5) lesz. Így már megfelelő a sorrend, tehát továbbvisszük a "buborékot". A tömbünk tehát az 8.lépés után: A = (3, 5, 5, 8, 9)

20

2.6. Javított Buborékrendezés 9. lépés: A következő két elem, amit összehasonlítunk a 2. és a 3. elem. Tehát a "buborék": (5, 5). Ezek megfelelő sorrendben vannak, úgyhogy továbblépünk. 10. lépés: A következő két elem, amit összehasonlítunk a 3. és a 4. elem. Tehát a "buborék": (5, 8). Ezek megfelelő sorrendben vannak. Mivel elértük az utolsó előtti (4.) elemet, ezért újra elindítjuk a "buborékot" a tömb elejétől, de már csak a 3. elemig haladunk vele, mivel 2-szor végighaladt a "buborék" a tömbön, ezért az utolsó előtti elem is a helyére került. 11. lépés: Mivel ez még csak a 3. kör, ezért a " buborékunkal" újra elindulunk a tömb elejétől. Tehát a két elem, amit összehasonlítunk a 1. és a 2. elem. Tehát a "buborék": (3, 5). Ezek megfelelő sorrendben vannak, úgyhogy továbblépünk. 12. lépés: A következő két elem, amit összehasonlítunk a 2. és a 3. elem. Tehát a "buborék": (5, 5). Ezek megfelelő sorrendben vannak. Mivel ez még csak a 3. kör volt, ezért újból elindulunk a tömb elejétől. 13. lépés: Elértük az utolsó (n − 1). kört, tehát a 4, kört. Ebben az első 2 elem kerül a buborékba, tehát a "buborék": (3, 5). Ezek megfelelő sorrendben vannak, ezért nem kell felcserélni őket. Az algoritmus itt véget is ér. Tehát a 13. lépés után megkapjuk a redezett tömböt: A = (3, 5, 5, 8, 9)

2.6. Javított Buborékrendezés Bemenet: A - a rendezendő tömb. Kimenet: A - a rendezett tömb. A javított buborékrendezés annyiban tér el a sima buborékrendezéstől, hogy figyeli, hogy a belső ciklusban történt-e csere, és ha nem, akkor megszakítja az algoritmust, mert nincs szükség további összehasonlításra, illetve cserére sem, ugyanis a tömb ekkor már rendezett. Az algoritmus tömb első két elemétől kiindulva minden lépésben egymás mellett álló 2 elemet veszünk egy „buborékba” és ezeket hasonlítjuk össze, és ha nem megfelelő sorrendben vannak, akkor felcseréljük őket. Majd minden lépésben egy elemmel jobbra tolva, újabb 2 elemet teszünk a "buborékunkba" és így hasonlítgatjuk össze kettesével az elemeket. A "buborék" jobbra tolását addig ismételjük, míg a "buborékban" megvizsgált 2 elem a tömb utolsó 2 eleme nem lesz. Ha ez megtörtént, akkor a tömb első két elemétől kezdve újra elindítjuk a "buborékot", de már nem a tömb végéig, hanem az (n − 1). elemig (n a tömb elemszáma). Tehát az algoritmus során többször is végigmegyünk a tömbön, a második körben, már csak az (n − 1). elemig haladunk, a harmadik körben pedig az (n − 2). elemig, és ezt folytatjuk addig, amíg szükség van cserére. Az algoritmus ezt addig ismétli, amíg az egyik körben nem volt szükség cserére, vagy elértük az utolsó (n − 1). kört. Ekkor a tömb már rendezett, tehát az algoritmus leáll.

2.6.1. A javított buborékrendezés algoritmusának leírása Javított Buborékrendezés(A)

21

2.6. Javított Buborékrendezés //Input paraméter: A - a rendezendő tömb //Output paraméter: A - A rendezett tömb 1. 2. 3. 4. 5. 6. 7. 8. 9.

j←2 REPEAT nemvoltcsere ← igaz FOR i ← hossz[A] DOWNTO j DO IF A[i] < A[i − 1] THEN csere A[i] ↔ A[i − 1] nemvoltcsere ← hamis INC(j) UNTIL nemvoltcsere RETURN (A)

2.6.2. A javított buborékrendezés struktogramja

2.8. ábra. A javított buborékrendezés struktogramja

22

2.6. Javított Buborékrendezés

2.6.3. A javított buborékrendezés folyamatábrája

2.9. ábra. A javított buborékrendezés folyamatábrája

2.6.4. A javított buborékrendezés vizsgálata Ha jól megfigyeljük az eljárást, akkor először a legnagyobb elem kerül a helyére, majd a második legnagyobb, és így tovább. Az algoritmusnak nagy az időigénye, mivel sok összehasonlítást kell elvégeznünk. Egy n elemű tömb esetén az összehasonlítások száma legrosszabb esetben: n(n − 1)/2. Tehát T (n) = Θ(n2 ).

2.6.5. Példa a javított buborék rendezésre Vegyünk egy n elemszámú tömböt. Esetünkben legyen n = 5. És a tömb, amit buborékrendezéssel rendezünk az legyen: A = (5, 8, 3, 5, 9). 23

2.6. Javított Buborékrendezés

1. lépés: A" buborékunkal" elindulunk a tömb elejétől és elvégezzük az összehasonlításokat, és a szükséges cseréket. Tehát először az első két elemet hasonlítjuk össze. Tehát a "buborékunk" jelenleg így néz ki (5, 8). Ezek megfelelő sorrendben vannak úgyhogy továbblépünk. 2. lépés: A következő két elem, amit összehasonlítunk a 2. és a 3. elem. Tehát a "buborék": (8, 3). Ezek nincsenek megfelelő sorrendben. 3. lépés: Csere. A "buborék" két elemét felcseréljük egymással: így a "buborék":(3, 8) lesz. Így már megfelelő a sorrend, tehát továbbvisszük a "buborékot". A tömbünk tehát az 3.lépés után: A = (5, 3, 8, 5, 9) 4. lépés: A következő két elem, amit összehasonlítunk a 3. és a 4. elem. Tehát a "buborék": (8, 5). Ezek nincsenek megfelelő sorrendben. 5. lépés: Csere. A "buborék" két elemét felcseréljük egymással: így a "buborék":(5, 8) lesz. Így már megfelelő a sorrend, tehát továbbvisszük a "buborékot". A tömbünk tehát az 5.lépés után: A = (5, 3, 5, 8, 9) 6.lépés: A következő két elem, amit összehasonlítunk a 4. és a 5. elem. Tehát a "buborék": (8, 9). Ezek megfelelő sorrendben vannak. Elértük az utolsó elemet, és kezdjük előről az algoritmust, de mostmár a "buborékkal" csak az utolsó előtti elemig megyünk. Mert az, hogy végighaladtunk egyszer a tömbön azt eredményezi, hogy az utolsó elem (a legnagyobb) helyre került. 7.lépés: Mivel a "buborék" utolsó előről való elindítása óta volt csere, ezért a " buborékunkal" újra elindulunk a tömb elejétől. Tehát a két elem, amit összehasonlítunk a 1. és a 2. elem. Tehát a "buborék": (5, 3). Ezek nincsenek megfelelő sorrendben. 8. lépés: Csere. A "buborék" két elemét felcseréljük egymással: így a "buborék":(3, 5) lesz. Így már megfelelő a sorrend, tehát továbbvisszük a "buborékot". A tömbünk tehát az 8.lépés után: A = (3, 5, 5, 8, 9) 9. lépés: A következő két elem, amit összehasonlítunk a 2. és a 3. elem. Tehát a "buborék": (5, 5). Ezek megfelelő sorrendben vannak, úgyhogy továbblépünk. 10. lépés: A következő két elem, amit összehasonlítunk a 3. és a 4. elem. Tehát a "buborék": (5, 8). Ezek megfelelő sorrendben vannak. Mivel elértük az utolsó előtti (4.) elemet, ezért újra elindítjuk a "buborékot" a tömb elejétől, de már csak a 3. elemig haladunk vele, mivel 2-szor végighaladt a "buborék" a tömbön, ezért az utolsó előtti elem is a helyére került. 11. lépés: Mivel a "buborék" utolsó előről való elindítása óta volt csere, ezért a " buborékunkal" újra elindulunk a tömb elejétől. Tehát a két elem, amit összehasonlítunk a 1. és a 2. elem. Tehát a "buborék": (3, 5). Ezek megfelelő sorrendben vannak, úgyhogy továbblépünk. 12. lépés: A következő két elem, amit összehasonlítunk a 2. és a 3. elem. Tehát a "buborék": (5, 5). Ezek megfelelő sorrendben vannak. Mivel elértük a 3. elemet, ezért nem haladunk tovább a "buborékkal". Az algoritmus megáll, mert a "buborék" utolsó előről való elindítása óta nem volt szükség cserére.

24

2.7. Shell rendezés Tehát a 12. lépés után megkapjuk a redezett tömböt: A = (3, 5, 5, 8, 9) 2.6. megjegyzés. Láthatjuk, hogy a belső ciklus vizsgálata miatt, ugyanarra a bemeneti tömbre a javított buborékrendezés, a sima buborékrendezéshez képest kevesebb lépésszámmal ér véget. Természetesen, ez nem minden bemenet esetén igaz, vannak olyan rendezetlen tömbök, amelyeket mindkét algoritmussal rendezve egyenlő lépésszámot kapunk.

2.7. Shell rendezés A shell rendezés a buborérendezés mintájára alkották meg. A buborékrendezésenél tapasztalt lassú helyrekerülést gyorsíthatja fel, azzal, hogy egymástól távol álló elemeket hasonlít össze. 2 elem távolsága a növekmény. Ez az algoritmus során csökken, addig, amíg az értéke 1 nem lesz. Minden növekmény esetén beszúrásos rendezést végez az adott növekménynek megfelelő távolságra álló elemekre. Mikor a növekmény=1-el, akkor sok elem már majdnem a helyére kerül.

2.7.1. A shell rendezés algoritmusának leírása Shell Rendezés (A) //Input paraméter: A - a rendezendő tömb //Output paraméter: A - A rendezett tömb 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

for s ← 1 to t do m ← hs for j ← m + 1 to hossz[A] do i←j−m k ← kulcs[Aj ] r ← Aj while i > 0 és k < Aj do Ai+m ← Ai i←i−m Ai+m ← r return (A)

Az algoritmus forrása: Házy Attila, Nagy Ferenc - Adatstruktúrák és algoritmusok (2011)

25

2.8. Minimum kiválasztásos rendezés

2.7.2. A shell rendezés struktogramja

2.10. ábra. Shell rendezés struktogramja

2.7.3. A shell rendezés vizsgálata A Shell Rendezés időigénye megfelelő növekmény megválasztásával leszorítható T (n) = Θ(n + 1, 2)-re.

2.8. Minimum kiválasztásos rendezés Ebben a rendező algoritmusban (n − 1)-szer megyünk végig a tömbön (n a tömb elemszáma). Első lépésben végigmegyünk a tömbön, és megkeressük a tömb legkisebb elemét, és mivel ez az első kör, ezért a tömb első elemével cseréljük fel (ha ez a minimumelem a tömb 1. eleme, akkor természetesen nincs szükség cserére). A második körben a tömb második elemétől indulva megyünk végig a tömbön és megkeressük a második elemtől kezdődő tömb legkisebb elemét, majd ezt az elemet a tömb 2. elemével cseréljük fel (ha ez a minimumelem a tömb 2. eleme, akkor természetesen nincs szükség cserére). Mindezt addig folytatjuk, ameddig el nem jutunk az (n − 1). lépésig, amelyben az 26

2.8. Minimum kiválasztásos rendezés (n − 1). és az n. elemet hasonlítjuk össze, és cseréljük fel, ha nincsenek a megfelelő sorrendben.

2.8.1. A minimum kiválasztásos rendezés algoritmusának leírása Minimum Kiválasztásos Rendezés //Input paraméter: A - a rendezendő tömb //Output paraméter: A - a rendezett tömb 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

for i ← 1 to hossz[A] − 1do k←i x ← Ai for j ← i + 1 to hossz[A] do if Aj < x then k ← j x ← Aj Ak ← Ai Ai ← x return (A)

2.8.2. A minimum kiválasztásos rendezés struktogramja

2.11. ábra. Minimumkiválasztásos rendezés struktogramja

27

2.8. Minimum kiválasztásos rendezés

2.8.3. A minimumkiválasztásos rendezés folyamatábrája

2.12. ábra. A minimumkiválasztásos rendezés folyamatábrája

2.8.4. A minimum kiválasztásos rendezés vizsgálata A minimum kiválasztásos rendezés futási ideje: T (n) = Θ(n2 ), mert az összehasonlítások száma: n(n − 1)/2. Ha nagyobb adathalmazt kell rendeznünk akkor általában -futási idő szempontjábólkedvezőbb ha bonyolultabb, de gyorsabb rendező algoritmust választunk. Ilyen például a gyorsrendezés vagy az összefésülő rendezés.

2.8.5. Példa a minimum kiválasztásos rendezésre Vegyünk egy n elemszámú tömböt. Esetünkben legyen n = 5. És a tömb, amit minimum kiválasztásosl rendezéssel rendezünk az legyen: A = (5, 8, 1, 9, 2).

28

2.8. Minimum kiválasztásos rendezés 1. lépés: A minimumkeresést elindítjuk a tömb 1. elemétől. Vesszük a tömb első elemét, az 5-öst legyen ez a kulcs. Összehasonlítjuk a 2. elemmel, a 8-al. Mivel nem kisebb a kulcsnál, ezért továbbhaladunk a tömb vége felé, és a többi elemmel is összehasonlítjuk a kulcsot. 2. lépés: Vesszük a tömb 3. elemét, az 1-et. Összehasonlítjuk a kulccsal. Mivel kisebb, mint a kulcs, ezért ki kell cserélnünk a kulcsot. Kicseréljük a kulcsot, tehát mostmár a kulcs az 1-es. Továbbhaladunk a tömb vége felé, és a többi elemmel is összehasonlítjuk a kulcsot. 3. lépés: Vesszük a tömb 4. elemét, a 9-et. Összehasonlítjuk a kulccsal. Mivel nem kisebb a kulcsnál, ezért továbbhaladunk a tömb vége felé, és a többi elemmel is összehasonlítjuk a kulcsot. 4. lépés: Vesszük a tömb 5. elemét, a 2-t. Összehasonlítjuk a kulccsal. Mivel nem kisebb a kulcsnál, és elértük a tömb végét, ezért az 1-et a tömb 1. elemével, az 5-el fel kell cserélni. A tömbünk tehát az 4.lépés után: A = (1, 8, 5, 9, 2) 5. lépés: A minimumkeresést újra elindítjuk a tömb 2. elemétől. Tehát vesszük a tömb 2. elemét, a 8-at és ez lesz a kulcs. Összehasonlítjuk a tömb 3. elemével, az 5-el. Mivel kisebb, mint a kulcs, ezért ki kell cserélnünk a kulcsot. Kicseréljük a kulcsot, tehát mostmár a kulcs az 5-ös. Továbbhaladunk a tömb vége felé, és a többi elemmel is összehasonlítjuk a kulcsot. 6. lépés: Vesszük a tömb 4. elemét, a 9-et. Összehasonlítjuk a kulccsal. Mivel nem kisebb a kulcsnál, ezért továbbhaladunk a tömb vége felé, és a többi elemmel is összehasonlítjuk a kulcsot. 7. lépés: Vesszük a tömb 5. elemét, a 2-t. Összehasonlítjuk a kulccsal. Mivel kisebb, mint a kulcs, ezért ki kell cserélnünk a kulcsot. Kicseréljük a kulcsot, tehát mostmár a kulcs a 2-es. 8. lépés: Mivel elértük a tömb végét, ezért a 2-t a tömb 2. elemével fel kell cserélnünk. A tömbünk tehát az 8.lépés után: A = (1, 2, 5, 9, 8) 9. lépés: A minimumkeresést újra elindítjuk a tömb 3. elemétől. Tehát vesszük a tömb 3. elemét, az 5-öt és ez lesz a kulcs. Összehasonlítjuk a tömb 4. elemével, az 9-el. Mivel nem kisebb a kulcsnál, ezért továbbhaladunk a tömb vége felé, és a többi elemmel is összehasonlítjuk a kulcsot. 10. lépés: Vesszük a tömb 5. elemét, a 8-at. Összehasonlítjuk a kulccsal. Mivel nem kisebb a kulcsnál, ezért nincs szükség cserére. Elértük a tömb végét, ezért megvan a minimum, amit nem kell felcserélnünk a 3. elemmel, mert ez a minimum a 3. elem, tehát az 5-öt a helyén hagyjuk. A tömbünk tehát az 10.lépés után: A = (1, 2, 5, 9, 8) 11. lépés: A minimumkeresést újra elindítjuk a tömb 4. elemétől. Tehát vesszük a tömb 4. elemét, a 9-et és ez lesz a kulcs. Összehasonlítjuk a tömb 5. elemével, ami a 8. Mivel 8 kisebb a kulcsnál, ezért ki kell cserélni. Kicseréljük a kulcsot, tehát mostmár a kulcs a 8-as 12. lépés: Elértük a tömb végét, ezért nincs szükség további összehasonlításra. A kul29

2.9. Leszámláló rendezés csot tehát felcseréljük a tömb 4. elemével, a 9-el. És mivel (n − 1)-szer végighaladtunk a tömbön a minimumkereséssel, ezért már rendezett lesz a tömbünk, tehát a minimum kiválasztásos rendezés algoritmusa megáll. Tehát a 12. lépés után megkapjuk a rendezett tömböt: A = (1, 2, 5, 8, 9)

2.9. Leszámláló rendezés A leszámláló rendezés bemenete az A rendezendő tömb, aminek minden eleme 0 és k közötti egész szám, egy B tömb, amibe a rendezett elemeket kapjuk vissza az eljárás végén, illetve a k szám. A leszámláló rendezésben sorra vesszük az elemeket és mindegyik elemnél megállapítjuk a nála kisebb elemek számát a tömbben. Ez alapján állapítja meg az adott elem helyét a kimeneti tömbben. Az eljárás során szükségünk van egy k elemű segédtömbre is. Jelölje ezt C. Stabil eljárás, mivel ha az eredeti tömbben előfordultak azonos értékű elemek, azokat az eredeti sorrendjükben kapjuk vissza.

2.9.1. A Leszámláló rendezés algorimusának leírása Leszámláló rendezés //Input paraméter: A - a rendezendő tömb, //k - kulcs felső korlát, pozitív egész. //Output paraméter: B - a rendezett tömb 1. for i ← 1 to k do 2. Ci ← 0 3. for j ← 1 to hossz[A] do 4. inc (CAj ) 5. //Ci aztmutatja, hogyhnyirtkszmunkvan 6. for i ← 2 to k do 7. Ci ← Ci + Ci−1 8. Ci mostazmutatja, hogyhnyi − tlnemnagyobbszmunkvan 9. for j ← hossz[A] downto 1 do 10. BCAj ← Aj 11. dec (CAj ) 12.return(B)

30

2.10. Edényrendezés

2.9.2. A leszámláló rendezés struktogramja

2.13. ábra. Leszámláló rendezés struktogramja

2.9.3. A leszámláló rendezés vizsgálata A leszámláló rendezés lineáris idejű rendező algoritmus. A lineáris futásidő a leszámláló rendezésnél annak köszönhető, hogy feltételezi, hogy a bemenő elemek egészek, és egy kis intervallumba ( [0, k] ) tartoznak. A leszámláló rendezés nem használja az összehasonlítást a tömb elemein. Időigénye: T (n) = Θ(n + k). n a rendezendő tömb elemszáma (hossza), k a felső korlát, pozitív egész. Ha k = Θ(n), akkor T (n) = Θ(n).

2.10. Edényrendezés Az edényrendezésnél feltesszük, hogy a bemenet[0, 1) intervallumon egyenletes eloszlású számok sorozata. Az intervallumot felosztjuk n egyenlő részre. Ezek lesznek az "edények". Az n bemenő számot szétosztjuk az edényekbe. Azzal, hogy feltettük, hogy a bemenet egyenletes eloszlású, azt garantáltuk, hogy egyetlen edénybe sem került túl sok elem. 31

2.10. Edényrendezés Ahhoz, hogy a megkapjuk az elemek rendezett sorozatát, edényenként rendezzük az elemeket beszúrásos módon, majd egybefűzzük őket.

2.10.1. A edényrendezés algoritmusának leírása Edényrendezés(A, L) // Input paraméter: A - a rendezendő tömb, n elemű. //Output paraméter: L - A rendezett elemek listája. 1. 2. 3. 4. 5. 6. 7.

n ← hossz[A] for i ← 1 to n do Beszúrjuk az Ai elemet a Bn·Ai listába. for i ← 0 to n − 1 do Rendezzük a Bi listát beszúrásos rendezéssel. Sorba összefűzzük a B0 , B1 , ..., Bn−1 listákat. Képezve az L listát. return (L)

2.10.2. Az edényrendezés struktogramja

2.14. ábra. Edényrendezés struktogramja

2.10.3. Az edényrendezés vizsgálata Az edényrendezés lineáris idejű rendezés, tehát: T (n) = Θ(n).

32

3. fejezet Fejlesztői dokumentáció A bemutatott rendező algoritmusokhoz elkészítettem a struktogramjukat, illetve néhány algoritmust leírtam szöveges példával, bemutatva, hogy az adott rendezés lépésről lépésre mit csinál, hogy lássuk a folyamatot. A struktogramokat a stukimania.hu oldalon található szerkesztővel készíttettem el, ahonnan elkészítés után lementettem képfájl-ént .png kiterjesztésekkel, majd ezeket konvertáltam át .eps kiterjesztésű fájlra. Az előző fejezetben ismertetett rendező algoritmusok közül 4-et programoztam le, illetve ezt a 4-et animáltam, hogy folyamatában láthassuk, hogy hogyan működnek. Illetve a program mindegyik algoritmus esetén meghatározza a lépésszámot, hogy megállapíthassuk, hogy ugyanazon bemeneti tömb esetén melyik ér véget kevesebb lépésszámmal. A lépésszám ebben az esetben az összehasonlítások és cserék összegét adja meg. Ezeket eclipsben, JAVA nyelven írtam meg. Ehhez a 4 rendezéshez a folyamatábráikat is megszerkesztettem, Microsoft Visio 2010 programmal. Erre a négy rendező algoritmusra esett a választásom: - Beszúró rendezés, - Minimumkiválasztásos rendezés, - Buborékrendezés, - Javított buborékrendezés.

3.1. A rendezőalgoritmusok megvalósítása java-ban A rendezőalgoritmusok leprogramozását osztályokkal oldottam meg, úgy, hogy azok bármilyen elemszámú tömbökön elvégezzék a rendezést, feltéve, hogy azok elemszáma értelemszerűen nagyobb, vagy egyenlő mint 2. Ugyanis üres tömböt nem kell rendezni, az 1 elemszámú tömb pedig már önmagában rendezett. Az osztályokon belül definiált függvények végzik el a tömbökön a rendezéseket, majd adják vissza a rendezett tömböt. A kiválasztott rendező algoritmusok közül mind a 4 helyben rendez, tehát az input tömbben adja vissza az output (rendezett) tömböt. A JAVA nyelvű program, amit készítettem, grafikus felhasználói felülettel rendelkezik. A kezdő felületen megadhatjuk a tömb elemeit. Itt 8 elem megadására van le33

3.2. A rendező algoritmusok implementációja hetőség. A grafikus kezelőfelület végessége miatt döntöttem amellett, hogy a tömbök mérete ne legyen dinamikusan változtatható, a rendezések megértéséhez, bemutatásához ez is megfelelő. Viszont a megírt függvények nem korlátozódnak a 8 elemű tömbök rendezésére, de ezt a későbbiekben láthatjuk is. Tehát a kezdő felületen megadhatunk 8 elemet, illetve a "Véletlenszám"-ra kattintva a program legenerál nekünk 8 db véletlenszámot. Ezeket rendezhetjük, illetve láthatjuk, hogy melyik algoritmus hány lépésben rendezte az input tömböt, így eldönthetjük, hogy melyik algoritmus volt a leghatékonyabb erre a bemeneti tömbre. Továbbá a program, mind a 4 rendezés esetén, szövegesen ismerteti a menetüket, és animáción keresztül megmutatja lépésről lépésre a menetüket, hogy lássuk folyamatában a működésüket.

3.2. A rendező algoritmusok implementációja

3.2.1. Beszúró rendezés

3.1. ábra. A beszúró rendezés implementációja

34

3.2. A rendező algoritmusok implementációja

3.2.2. Minimumkiválasztásos rendezés

3.2. ábra. A minimumkiválasztásos rendezés implementációja

3.2.3. Buborékrendezés

3.3. ábra. A buborékrendezés implementációja

35

3.3. A program bemutatása

3.2.4. Javított buborékrendezés

3.4. ábra. A javított buborékrendezés implementációja

3.3. A program bemutatása 3.3.1. Kezdő ablak A kezdő ablakban megadhatunk 8 egész számot, amit rendezni szeretnénk. Ezek lehetnek bármilyen nagyságúk, viszont a megjelenítési szempontból azt javaslom, hogy 4-5 számjegyűnél ne legyenek nagyobbak. Itt negatív számokat is megadhatunk. Ha nem szeretnénk számokat megadni, akkor generáltathatunk 8 véletlen, egész számot a "Véletlenszám" gombra kattintva (a Random() függvény segítségével). Ekkor Megjelenik 8 darab véletlen szám a [0, 999] intervallumból. Ha valamelyik számot át szeretnénk írni, akkor ezt is megtehetjük. Amikor úgy gondoljuk, hogy megvannak a számok, amiket rendezni szeretnénk, akkor kattintsunk a "Rendezés" gombra. Ekkor mind a 4 fajta rendezés mellett megjelenik a rendezett tömb, és az, hogy az adott algoritmus hány lépésben rendezte a bemeneti tömböt. A lépésszám az összehasonlítások és cserék összege. Az alábbi képen 8 véletlenszám rendezését láthatjuk.

36

3.3. A program bemutatása

3.5. ábra. Kezdő ablak

A "Demo" gombok a különböző algorimusok bemutatására létrehozott ablakokat indítják el. Ahol részletesebben megismerkedhetünk a menetükkel. Ahhoz, hogy ez láthassuk folyamatában, időzíteni kellett az algoritmusokat. Ehhez átírtam rekurzívvá őket, és a timer.schedule() és a TimerTask() segítségével időzítettem a futásukat.

3.3.2. Beszúró rendezés A kezdő ablakban a beszúró rendezés sorának a végén található "Demo" gombra kattintva megkapjuk azt az ablakot, ami bemutatja a beszúró rendezést. Ebben az ablakban található egy szöveges leírás az algoritmus menetéről, illetve a kezdő ablakban megadott elemek is. Ha rákattintunk az indít gombra, akkor elindul a rendezés. Ha elindítjuk a rendezést, akkor sárga hátérrel láthatjuk az éppen vizsgált elemeket, és ha nincsenek a megfelelő sorrendben, akkor ezeket felcseréljük. A színezett háttér arra szolgál, hogy lépésről-lépésre láthassuk, hogy az algoritmus, hogyan rendezi a tömbünket. Ha véget ér az algoritmus, akkor láthatjuk, hogy a tömb elemei növekvő sorrendben követik egymást.

37

3.3. A program bemutatása

3.6. ábra. A beszúró rendezés ablaka futtatás előtt

3.7. ábra. A beszúró rendezés ablaka futtatás után

38

3.3. A program bemutatása

3.3.3. Minimumkiválasztásos rendezés

A kezdő ablakban a minimumkiválasztásos rendezés sorának a végén található "Demo" gombra kattintva megkapjuk azt az ablakot, ami bemutatja a minimumkiválasztásos rendezést. Ebben az ablakban található egy szöveges leírás az algoritmus menetéről, illetve a kezdő ablakban megadott elemek is. Ha rákattintunk az "Indít" gombra, akkor elindul a rendezés. Ha elindítjuk a rendezést, akkor kék háttérrel láthatjuk az adott kör első elemét, sárgával az éppen vizsgált elemet, zöld háttérrel pedig azt az elemet láthatjuk, amelyet a kör első elemével fel kell cserélni. Ha kék hátterű elem az adott kör minimumeleme, akkor abban a körben nincs zöld hátterű elem, mert akkor azt nem kell felcserélni semmivel, mert a helyén van. A színezett háttér arra szolgál, hogy lépésről-lépésre láthassuk, hogy az algoritmus, hogyan rendezi a tömbünket. Ha véget ér az algoritmus, akkor láthatjuk, hogy a tömb elemei növekvő sorrendben követik egymást.

3.8. ábra. A minimumkiválasztásos rendezés ablaka futtatás előtt

39

3.3. A program bemutatása

3.9. ábra. A minimumkiválasztásos rendezés ablaka futtatás után

3.3.4. Buborékrendezés

A kezdő ablakban a buborékrendezés sorának a végén található "Demo" gombra kattintva megkapjuk azt az ablakot, ami bemutatja a buborékrendezést. Ebben az ablakban található egy szöveges leírás az algoritmus menetéről, illetve a kezdő ablakban megadott elemek is. Ha rákattintunk az "Indít" gombra, akkor elindul a rendezés. Ha elindítjuk a rendezést, akkor sárga hátérrel láthatjuk az éppen vizsgált elemeket, és ha nincsenek a megfelelő sorrendben, akkor ezeket felcseréljük. A színezett háttér arra szolgál, hogy lépésről-lépésre láthassuk, hogy az algoritmus, hogyan rendezi a tömbünket. Ha véget ér az algoritmus, akkor láthatjuk, hogy a tömb elemei növekvő sorrendben követik egymást.

40

3.3. A program bemutatása

3.10. ábra. A buborékrendezés ablaka futtatás előtt

3.11. ábra. A buborékrendezés ablaka futtatás után

41

3.3. A program bemutatása

3.3.5. Javított buborékrendezés

A kezdő ablakban a javított buborékrendezés sorának a végén található "Demo" gombra kattintva megkapjuk azt az ablakot, ami bemutatja a javított buborékrendezést. Ebben az ablakban található egy szöveges leírás az algoritmus menetéről, illetve a kezdő ablakban megadott elemek is. Ha rákattintunk az "Indít" gombra, akkor elindul a rendezés. Ha elindítjuk a rendezést, akkor sárga hátérrel láthatjuk az éppen vizsgált elemeket, és ha nincsenek a megfelelő sorrendben, akkor ezeket felcseréljük. A színezett háttér arra szolgál, hogy lépésről-lépésre láthassuk, hogy az algoritmus, hogyan rendezi a tömbünket. Ha véget ér az algoritmus, akkor láthatjuk, hogy a tömb elemei növekvő sorrendben követik egymást.

3.12. ábra. A javított buborékrendezés ablaka futtatás előtt

42

3.3. A program bemutatása

3.13. ábra. A javított buborékrendezés ablaka futtatás után

3.1. megjegyzés. A képeken láthatjuk, hogy mind a 4 rendező algoritmus növekvő sorrendben rendezi az input tömböt. A képeken a rendezés előtti, illetve utáni állapotokat láthattuk, de a program ezt folyamatában mutatja be.

43

4. fejezet Összefoglalás A szakdolgozatom témája a rendezőalgoritmusok, ezért minél részletesebben, minél több módszerrel próbáltam bemutatni. Ahhoz, hogy a rendező algoritmussal foglalkozzak, elengedhetetlennek tartottam, hogy az algoritmusokról is írjak, de próbáltam csak a legszükségesebb definíciókat, tulajdonságokat megemlíteni, amelyek a rendezések ismertetése során előkerülhetnek, mert nem szerettem volna, hogy a szakdolgozatom nagy része csak úgy általánosságban szóljon az algoritmusokról. Ezért ezt a részt igyekeztem minél koncentráltabban összefoglalni. Tehát először az algoritmusok elméletét mutattam be. Ismertettem az algoritmus definícióját, tuladonságait és a jellemző vonásait. Ezután leírtam a reláció definícióját, hogy aztán a rendezési relációt is definiálhassam. Meghatároztam, hogy milyen adattípusok esetén van értelmezve a rendezés művelete, és hogy milyen igények, illetve elvárások léphetnek fel a megfelelő rendezőalgoritmus megszerkesztésénél. Utána definiáltan az algoritmus tervezési stratégiák közül az oszd meg és uralkodj elvet, mivel az összefésülő rendezés ilyen tulajdonságú. Továbbá röviden ismertettem az algoritmust leíró eszközöket. A pszeudokódot, a folyamatábrát és a struktogramot. Ezután rátértem a rendezőalgoritmusok részletes leírására. A szakdolgozatomban a következő rendező algoritmusok kerültek bemutatásra: - Beszúró rendezés, - Összefésülő rendezés, - Gyorsrendezés, - Buborékrendezés, - Javított buborékrendezés, - Shell rendezés, - Minimumkiválasztásos rendezés, - Leszámláló rendezés, - Edényrendezés. Ezek leírását a dokumentáció rész követi. Itt megadom hogy a struktogramokat, folyamatábrákat mely programok segítségével alkottam meg. Majd ismertettem a beszúró-, minnimumkiválasztásos-, buborék- és javított buborékrendezések implementációját JAVA nyelven Aztán bemutattam a megírt program tulajdonságait, működését képekkel illusztrálva.

44

Irodalomjegyzék [1] Házy Attila, Nagy Ferenc: Adastruktúrák és algoritmusok jegyzet 2011. http://www.uni-miskolc.hu/ matnf/adatst/admin/adat_alg.pdf [2] Thomas H. Cormen, Charles E. Leiserson,Ronald L. Rivest, Clifford Stein: ÚJ ALGORITMUSOK, Scolar Kiadó, Budapest, 2003. [3] http://tenger.web.elte.hu/flash/ [4] Wikipédia, http://hu.wikipedia.org/. [5] Stukimania, http://stukimania.hu/

45

Adathordozó használati útmutató Az adathordozó, jelen esetben CD, tartalmazza a szakdolgozatomat pdf formátumban, a szakdolgozat LaTex-es forrásfájljait, az elkészített program futtatható változatát, ami .jar kiterjesztésű, és a program java-ban megírt forráskódját is. Továbbá a CD-n megtalálhatóak a szakdolgozatomban felhasznált képek is .png kiterjesztéssel. A "Fekete Enikő (YO0ILW) szakdolgozat" mappa struktúrája: - Fekete_Enikő_YO0ILW_Szakdolgozat.pdf: a szakdolgozatom pdf kiterjesztéssel. - Latex forrásfájlok mappa: ebben a mappában találhatóak meg a szakdolgozatom LaTex-es forrásfájljai. Itt is megtalálható a Fekete_Enikő_YO0ILW_Szakdolgozat.pdf fájl, illetve ennek a .tex kiterjesztésű változata. Ahhoz, hogy a szakdolgozat különböző részeit egyben futtathassuk. A mappákon belül pedig ezeknek a különböző részeknek a .tex-es forrásfájlja található. A kepek mappa pedig a szakdolgozatban felhasznált képek .eps, illetve .pdf kiterjesztéssel. - Struktogramok mappa: a szakdolgozatban található struktogramok képei .png kiterjesztéssel. - Folyamatábrák mappa: a szakdolgozatban található folyamatábrák képei .png kiterjesztéssel. - Programkódok mappa: a szakdolgozatban található programkódok képei .png kiterjesztéssel. - Programképek mappa: a szakdolgozatban, program bemutatásakor használt képek .png kiterjesztéssel. - Rendezes mappa: A Rendezes mappán belül található src mappában a megírt java nyelvű program forráskódjai találhatóak. - Rendezes.jar: a megírt program futtatható változata. A Rendezes.jar programot futtatva megjelenik a program kezdő ablaka. Ennek a használatát a Fejlesztői dokumentáció részben írtam le.

46