GRAFICKÉ ZNÁZORNENIE TRIEDIACICH ALGORITMOV RENDEZÉSI ALGORITMUSOK GRAFIKUS ÁBRÁZOLÁSA

UNIVERZITA J. SELYEHO – SELYE JÁNOS EGYETEM EKONOMICKÁ FAKULTA – GAZDASÁGTUDOMÁNYI KAR

GRAFICKÉ ZNÁZORNENIE TRIEDIACICH ALGORITMOV RENDEZÉSI ALGORITMUSOK GRAFIKUS ÁBRÁZOLÁSA Bakalárska práca- Szakdolgozat

Tibor Huršan 2015

UNIVERZITA J. SELYEHO – SELYE JÁNOS EGYETEM EKONOMICKÁ FAKULTA – GAZDASÁGTUDOMÁNYI KAR

GRAFICKÉ ZNÁZORNENIE TRIEDIACICH ALGORITMOV RENDEZÉSI ALGORITMUSOK GRAFIKUS ÁBRÁZOLÁSA Bakalárska práca - Szakdolgozat Študijný program:

AIdb - Aplikovaná informatika

Tanulmányi program:

AIdb – Alkalmazott informatika

Číslo a názov študijného odboru:

2511 Aplikovaná informatika

Tanulmányi szak száma és megnevezése:

2511 Aplikovaná informatika

Školiteľ:

RNDr. Štefan Gubo, PhD.

Témavezető:

RNDr. Gubo István, PhD.

Školiace pracovisko:

Katedra matematiky a informatiky

Tanszék megnevezése:

Matematika és Informatika Tanszék

Tibor Huršan Komárno 2015

Univerzita J. Selyeho Ekonomická fakulta _____________________________________________________________________________________________________

ZADANIE ZÁVEREČNEJ PRÁCE Meno a priezvisko študenta:

Tibor Huršan

Študijný program:

Aplikovaná informatika (Jednoodborové štúdium, bakalársky I. st., denná forma)

Študijný odbor:

9.2.9. aplikovaná informatika

Typ záverečnej práce:

Bakalárska práca

Jazyk práce:

maďarský

Sekundárny jazyk:

slovenský

Téma:

Grafické znázornenie triediacich algoritmov

Anotácia:

Úlohou

autora

pre vizualizáciu

bakalárskej niektorých

práce

bude

triediacich

vytvoriť

algoritmov

aplikáciu (min.

4).

V teoretickej časti práce je potrebné podrobne popísať princíp zvolených algoritmov. Praktická časť by sa mala venovať implementácii a popisu vytvorenej aplikácie. Vedúci:

RNDr. Štefan Gubo, PhD.

Katedra:

KMI - Katedra matematiky a informatiky

Vedúci katedry:

RNDr. Zuzana Árki, PhD.

Dátum zadania:

04.10.2014

Dátum schválenia: 15.12.2014

RNDr. Zuzana Árki, PhD. vedúci katedry

Becsületbeli nyilatkozat Alulírott Tibor Huršan kijelentem, hogy szakdolgozatomat konzultáns tanárom segítségével és a feltüntetett szakirodalmak felhasználásával önállóan készítettem el.

Komárno, 2015.05.15. Aláírás

Köszönetnyilvánítás Ezúton szeretnék köszönetet nyilvánítani RNDr. Gubo István, PhD. tanár úrnak, akinek hálával tartozom, amiért segítséget nyújtott az általam kiválasztott témakör kidolgozásában. Köszönöm szaktudását és türelmét. Hálával tartozom a Selye János Egyetem azon tanárainak is, akiknek köszönhetően olyan ismeretekre tettem szert, melyek segítségemre szolgáltak a szakdolgozat kidolgozásában.

Abstrakt v slovenskom jazyku Cieľom bakalárskej práce je vytvorenie takej učebnej pomôcky, ktorá pomáha osvojiť teóriu algoritmov. Pri jej vytvorení, sme sa zamerali na jednoduchosť a jednoznačnosť pri grafickom znázornení triediacich algoritmov. Naša práca sa skladá z troch častí. V prvej časti predstavujeme samotnú teóriu algoritmov, včítane pôvodu slova, základné vlastnosti, algoritmizácie úloh a jednotlivé možnosti na udanie algoritmov. Druhá časť definuje triediace algoritmy a ich zložitosť a vlastnosti. V poslednej časti predstavujeme náš program, ktorý pomôže pri lahšom porozumeni obsahu našej bakalárskej práce. Výsledkom práce je jednoduchá a ľahko ovládatelná učebná pomôcka, vďaka ktorej získavame prehľad o fungovaní triediacich algoritmov. Kľúčové slová: algoritmus, triediaci algoritmus, zložitosť, grafické znázornenie

Absztrakt magyar nyelven A szakdolgozat célja egy segédeszköz létrehozása, mely által könnyedén elsajátíthatóak a rendezési algoritmusok alapismeretei. A megalkotás során azt tartottuk szem előtt, hogy a grafikus felület keretén belül a felhasználónak minél egyszerűbben és egyértelműbben átadhassuk a rendezések folyamatainak egyes lépéseit. A munka három fejezetből áll. Az első fejezetben egy általános leírást adtunk az algoritmusokról, beleértve a szó eredetét, az algoritmusok tulajdonságait, algoritmizálás lépéseit és megadási eszközeit. A második fejezetben a rendezési algoritmusokat definiáltuk és adtuk meg azok tulajdonságait és bonyolultságukat. Az utolsó fejezetben a munkánk témakörének megértéséhez megalkotott vizualizációs program főbb funkcióit mutattuk be. A szakdolgozat eredménye egy egyszerű, átlátható, könnyen kezelhető oktatási segédlet, mely által áttekintést nyerhetünk a rendezési algoritmusokról. Kulcsszavak: algoritmus, rendezési algoritmus, bonyolultság, grafikus ábrázolás

Abstract in English

The goal of this bachelor's project is to create an educational tool, which helps to understand the theory of sorting algorithms. During the creation of the tool we were focusing on the simplicity and user-friendliness of the interface, which helps the user to easily understand the function of the selected algorithms. Our project consists of three chapters. The first one represents the theory of algorithms, which also includes the origin of the word, their attributes, steps of algorithmization and the kinds of their expression. In the second chapter we define the sorting algorithms and their complexity. In the last chapter we introduce the main functions of the tool we created, which is needed for easier understanding of our bachelor's project. The result of our project is a simple, easily manageable learning tool, which helps us to gain a better overwiev of the theory of the algorithms.

Keywords: algorithm, sorting algorithm, complexity, graphic visualization

Tartalomjegyzék Ábrák jegyzéke.....................................................................................................................9 Bevezetés ............................................................................................................................. 10 1 Az algoritmusok .............................................................................................................. 11 1.1 Az algoritmus szó eredete .......................................................................................... 11 1.2 Az algoritmus fogalma............................................................................................... 11 1.3 Az algoritmusok tulajdonságai .................................................................................. 12 1.4 Feladatok algoritmizálása .......................................................................................... 13 1.5 Algoritmus leíró eszközök ......................................................................................... 14 1.5.1 Szöveges eszközök ............................................................................................. 14 1.5.2 Grafikus eszközök ............................................................................................... 16 2 Rendezési algoritmusok ................................................................................................. 18 2.1 Rendezési algoritmusok osztályozása ........................................................................ 18 2.2 Bonyolultság .............................................................................................................. 19 2.3 Bonyolultsági osztályok ............................................................................................. 20 2.3.1 Konstans idő O(1) ............................................................................................... 20 2.3.2 Lineáris idő: O(n) ................................................................................................ 20 2.3.3 Kvadratikus idő: O(n2) ........................................................................................ 21 2.3.4 Logaritmikus idő: O(log n) és O(n log n) ........................................................... 21 2.4 Összehasonlításokon alapuló rendező módszerek ..................................................... 21 2.4.1 Beszúrásos rendezés ........................................................................................... 22 2.4.2 Buborékos rendezés ............................................................................................ 25 2.4.3 Koktélrendezés.................................................................................................... 26 2.4.4 Kiválasztásos rendezés ....................................................................................... 27 2.5 Oszd meg és uralkodj elv ........................................................................................... 29 2.5.1 Kupacrendezés .................................................................................................... 30 3. Rendezési algoritmusok vizualizációja ........................................................................ 33 3.2 Tömbök megadása ..................................................................................................... 33 3.2 A rendezetlen tömb kirajzolása.................................................................................. 34 3.3 Rendezési mód kiválasztása....................................................................................... 35 3.4 Sebesség beállítása ..................................................................................................... 36 3.5 Rendezés indítása ....................................................................................................... 36 3.5.1 Vászon törlése ..................................................................................................... 37 3.5.2 Tömb kirajzolása................................................................................................. 37 3.5.3 Szüneteltetés, léptetés és gyors lefuttatás ........................................................... 37 3.5.4 A rendezés előkészületei ..................................................................................... 38 3.5.5 A rendezés menete .............................................................................................. 39 Befejezés .............................................................................................................................. 42 Resumé ................................................................................................................................ 43

Ábrák jegyzéke 1. ábra: pszeudokód ........................................................................................................... 15 2. ábra: Backus-Naur-forma ............................................................................................. 15 3. ábra: programkódos megfogalmazás .......................................................................... 16 4. ábra: folyamatábrák építőelemei ................................................................................. 17 5. ábra: SimpleSort (kódrészlet) ....................................................................................... 22 6. ábra: InsertionSort (kódrészlet) ................................................................................... 23 7. ábra: BubbleSort (kódrészlet) ...................................................................................... 25 8. ábra: CocktailSort (kódrészlet) .................................................................................... 27 9. ábra: SelectionSort (kódrészlet) ................................................................................... 28 10. ábra: bináris fa tömbben ............................................................................................. 30 11. ábra: maximum-kupacolás (kódrészlet) .................................................................... 32 12. ábra: maximum-kupac építése (kódrészlet) .............................................................. 32 13. ábra: Kupacrendezés (kódrészlet) .............................................................................. 33 14. ábra: tömbök megadása .............................................................................................. 34 15. ábra: oszlopok skálázása (kódrészlet) ........................................................................ 34 15. ábra: oszlopok skálázása 5, 15, 25, 40 elem esetén.................................................... 35 16. ábra: rendezés kiválasztása......................................................................................... 35 17. ábra: várakoztató eljárás (kódrészlet) ....................................................................... 36 18. ábra: vászon törlése (kódrészlet) ................................................................................ 37 20. ábra: szüneteltetés, léptetés, gyors lefuttatás ............................................................ 38 21. ábra: rendezés megadása (kódrészlet) ....................................................................... 38

9

Bevezetés Szakdolgozatunk témaköreként az algoritmusokat, ezen belül pedig a rendezési algoritmusokat választottuk, mégpedig azoknak definícióját és működésük grafikus ábrázolásmódját. A témakör kiválasztásához nagyban hozzájárult az eddigi tanulmányaim során szerzett tudás, mely által közel került hozzám a témakör. A munkánk három fő részre osztható. Az első fejezetben definiáljuk az algoritmusok általános fogalmát és a szó jelentésének eredetét. A már formálisabb jellemzés érdekében definiáljuk az általános jellegzetességeiket, tulajdonságaikat. Leírjuk a feladatok algoritmizálásának menetét, majd elemezzük az ehhez használható megadási módokat. Az algoritmusok jellemzése után a második fejezetben rátérünk a munkánkhoz már szorosan kapcsolódó rendezési algoritmusokra. Ez a felhasználónak a későbbiekben megkönnyíti a vizualizációs program működésének értelmezését.

Megadjuk az

algoritmusok osztályozását és az egyes bonyolultsági osztályokat. Ezután következnek a vizualizáció során is használt rendezési algoritmusok

általános jellemzései és

bonyolultságuk elemzése. Az utolsó fejezetben térünk rá magára a rendezések vizualizációjára. Egy rövid programleírás után belekezdünk a program legfontosabb funkcióinak elemzésébe. Az ábrázoláshoz oszlopdiagramokat választottunk, melyben a tömbök az egyes rendezési algoritmusok tulajdonságaihoz illően viselkednek. Az egyes oszlopok kivilágításával, villogtatásával a felhasználó egyértelműen láthatja gyakorlatban is a munka elméleti során leírtakat.

10

1 Az algoritmusok 1.1 Az algoritmus szó eredete Az algoritmus szó a mai jelentéstartalmát csak későn, a 19. század végén vette fel. Ezt megelőzőleg az aritmetikai műveletek elvégzését jelentette arab számokkal, és ennek a jelentésnek erednek a gyökerei a 9. századból. Ebben az időben tevékenykedett a perzsa matematikus, Abū ´Abdallāh Muhammad ibn Mūsā al-Khwārizmī, aki lefektette az algebra alapjait. Al Khvarizmi nevének latin fordítása az Algoritmi, ami idővel az algorism alakot vette fel és a jelenben is használatos ebben a formában az eredeti jelentését megőrizve, míg az algorithm forma új jelentést kapott (Knuth, 1997)

1.2 Az algoritmus fogalma Az algoritmusok valójában nem korlátozódnak a számítástechnika világára, akár mindennapi életünk legegyszerűbb tevékenységei is valamilyen algoritmusoknak mondhatóak. Maga a szó a köznyelvben valamilyen műveletsort, tevékenységet jelent, amellyel egy probléma megoldását adjuk meg. Emellett az algoritmusok elengedhetetlenek a számítógépes programok világában is, ma már szinte minden eszközben megtalálhatóak valamilyen formában. Kutatásuk és elemzésük az elméleti informatika és a számítástudomány feladata, mely során konkrét programnyelvet nem használnak. Ez a módszer más matematikai területek megoldásaihoz hasonlít, ahol az elemzés inkább a szóban forgó koncepciókról, mint a konkrét környezetekről szól. Az elemzéshez használt algoritmusokat erősen formalizálják, és a formális szemantika eszközeivel vizsgálják. Az algoritmusok tár- és időigényével a bonyolultságelmélet foglalkozik, és az eredményeket aszimptotikusan adja meg, míg a futásuk befejeződését és az eredményes véget érést a kiszámíthatóságelmélet tárgyalja. (Cormen et al., 2007) Az algoritmus, avagy eljárás, mondható egy önálló, meghatározott sorrendű utasítássorozatnak, amely a feladat megoldását véges számú lépésben eredményezi. Lényeges tényező a véges számú lépésben való végrehajtás, mert az alkalmazott algoritmust később az adott programnyelv környezetébe szükséges implementálnunk, és használnunk. Emellett elengedhetetlen az algoritmusok helyessége is.

11

Egy algoritmust helyesnek nevezünk, ha minden konkrét bemenetre helyes kimenetet ad és megáll. Azt mondjuk, hogy a helyes algoritmus megoldja az adott számítási problémát. Előfordulhat, hogy egy helytelen algoritmus egyáltalán nem áll meg bizonyos bemeneteknél, vagy nem a kívánt válasznál áll meg. Egy helytelen algoritmusnak is hasznát vehetjük, ha a hibaarányának kezelésére képesek vagyunk. Egy algoritmusnak a következő feltételeket kell teljesítenie: 

Az algoritmust képező utasítások legyenek egyértelműek,



az utasítások gépiesen végrehajthatóak,



és a megoldásig véges számú lépésben érhetünk el.

Az olyan algoritmust, amelynek végrehajtására képes egy számítógép, programnak nevezzük. A gépi kódú programozás által felírt algoritmus abban különbözik egy neki megfelelő logikai algoritmustól, hogy a programizált algoritmus szigorú formai előírásokhoz, az adott programozási nyelv jelölésrendszeréhez kötött. (Házy et al., 2011)

1.3 Az algoritmusok tulajdonságai Knuth, A számítógépes programozás művészete (1997, 28-29. o.) című könyvében fontosnak tartja, hogy az alábbi öt, széles körben elfogadott általános tulajdonsággal jellemezzük az algoritmusokat amellett, hogy egy bizonyos fajta feladat megadására alkalmas véges utasítássorozatként tekintünk rá.

1)

Végesség. Ezt a tulajdonságot szokás termináltságnak nevezni. Jelentése az, hogy az algoritmusnak véges sok lépés után be kell fejeződnie, hogy véges idő alatt végrehajtható legyen. Emellett szükséges, hogy az algoritmusok által kezelt adatok is végesek legyenek, azaz például rendezések során nem rendezhető az összes szám, legfeljebb n darab. Vannak azonban kivételek ezen tulajdonság szabályai alól. „Számítási módszernek“ nevezhetünk egy eljárást, ha az megfelel az algoritmussal szemben támasztott követelményeknek a végességi kritériumtól eltekintve. Ilyenek például az operációs rendszerek, vagy a vezérlőrendszerek. Ezek a programok folyamatosan futnak, amíg a számítógép nincs utasítva az ellenkezőjére. 12

2)

Meghatározottság.

Az algoritmus minden egyes lépésének pontosan

definiáltnak kell lennie. A végrehajtandó utasításnak minden esetben világosnak és félreérthetetlennek kell lennie. Szavakkal, természetes nyelvvel való megadás esetén előfordulhat többértelműség is, ám ezen tulajdonság elérését könnyűvé teszik az algritmusok leírására tervezett programnyelvek, mivel azokban minden kifejezésnek formálisan definiált, pontos jelentése van. 3)

Bemenet. Az algoritmus vagy igényel, vagy sem olyan adatokat, amelyeket az elindítása előtt meg kell adni. Az input mindig bizonyos meghatározott halmazokból kerülhet ki. Ezen adatok kerülnek feldolgozásra az algoritmus futása során és ezek segítségével fogjuk megkapni az outputot.

4)

Kimenet. Az algoritmushoz egy vagy több output tartozhat, amelyek meghatározott kapcsolatban állnak az inputtal.

5)

Elvégezhetőség. Elvárjuk, hogy az algoritmust végre lehessen hajtani. Ez alatt azt értjük, hogy az algoritmus során végrehajtandó utasításoknak elég egyszerűeknek kell lenniük ahhoz, hogy egy ember véges időn belül képes legyen azt pontosan végrehajtani csak egy papírt és ceruzát használva.

1.4 Feladatok algoritmizálása Az információk feldolgozása egy folyamat, mely során konkrét bemeneti adatok vannak eredményekké alakítva, melyek elősegítik a program továbbhaladását. Ha bármilyen feladatot szeretnénk számítógépen megoldani, azt előbb fel kell osztani bizonyos előkészítő lépések sorozatává. (Dalal, 2004) A feladatok algoritmizálásának három alapvető lépése van: 

Feladat megfogalmazása: első szükséges feltevés ahhoz, hogy számítógépen a probléma megoldható legyen, először azt egyértelműen, pontosan, tömören kell meghatározni. Emellett fontos egy cél tisztázása és kitűzése, melyet az adott feladat oldása során figyelemmel követünk. Ez után következik a probléma modellezése valamilyen változók és állandók rendszerének segítségével, például matematikai, vagy grafikus eszközök használatával. 13



Feladat analizálása: ebben a lépésben keressük meg a feladat megoldásához szükséges algoritmust. Megállapítjuk, hogy a feladat megoldható-e, egy- ,vagy több megoldással rendelkezik, vázoljuk a lehetséges megoldásokat és döntést hozunk az alkalmazni kívánt módszerekről. A kiválasztott metódusnak biztosítania kell a megfelelő kimeneti információk eredményezését, és pontosan megadja, hogy milyen bemeneti adatokra lesz szükség. A feladat általánosításra kerül és megalkotjuk az első elképzeléseket az algoritmikus megoldhatóságáról.



Megoldó algoritmus felállítsa: ebben a lépésben megadjuk a probléma megoldásának gondolatmenetét, és itt kapjuk majd végül meg a megoldó algoritmust is. Ide tartozik a feladat programozása is, mely által az emberi elképzelések kerülnek számítógépes feldolgozásra alkalmas formába. Ezen tevékenységek eredménye a program.

1.5 Algoritmus leíró eszközök Az algoritmus leíró eszközök feladata, hogy az általánosan megfogalmazott feladat megoldási lépéssorozatát konkrétan megadhassuk. Az, hogy éppen melyik megadási módot választjuk, függ attól, hogy melyiket tudjuk az adott helyzetben a legkönnyebben megvalósítani

és

felhasználni.

Az

ilyen

eszközöknek

alapvetően

két

fajtáját

különböztethetjük meg.

1.5.1 Szöveges eszközök 

Írásos megfogalmazás: az írásos megfogalmazás a legegyszerűbb módja az algoritmusok megadásának, ám emellett a legkevésbé pontos is. Használata során a végrehajtandó lépéseket saját szavainkkal írjuk le, a számunka legmegfelelőbb módon. Ekkor a külön előre elfogadott szabályokhoz nem kell alkalmazkodni, leírásmódot és nyelvet saját választásunk szerint alkalmazhatunk.

14



Pszeudokód: egy olyan mesterségesen kialakított formális nyelv, mely változókkal és egyéb programozási utasításokkal egészíti ki a beszélt nyelv általános szavait és utasításait. Nagyon közel van a magas szintű programozási nyelvek által használt kódhoz, de egyetlen nyelvvel sem azonos a formája, nem követi precízen azok szintaktikai szabályait. Egyezményes formája nincs, általában igyekszünk a célközönség

által

ismert

és

könnyen

értlemezhető

programozási

nyelv

utasításkészletéből kiindulni. Mondható, hogy átmenetet képez a mondatszerű leírás és a kódolás között. (Subecz, 2010) Alapvetően háromféle vezérlési szerkezetet alkalmaz: o Felsorolást o Ismétlést, ciklust o Esetszétválasztást

1. ábra: pszeudokód



Metaszintaxis: környezetfüggetlen nyelvtanok leírására használható, legismertebb formája a Backus-Naur-forma. A BNF a legtöbb programozási nyelv elméleti leírásánál, ideértve az utasítás készleteket és a kommunikációs protokollokat is.

2. ábra: Backus-Naur-forma (Backus-Naur-forma, 2015)

15



Programkódos megfogalmazás: ez a lehetséges legpontosabb módja egy algoritmus megadásának. A programkód egy mesterségesen kialakított nyelv, amelyet viszont a számítógép már képes értelmezni és végrehajtani. Ezen megfogalmazás esetében már fontos, hogy betartsuk a választott nyelv szintaktikai szabályait is, ellenkező esetben a számítógép nem lesz képes az algoritmusban leírt feladatok elvégzésére.

3. ábra: programkódos megfogalmazás

1.5.2 Grafikus eszközök 

Folyamatábra: a folyamatábra egy folyamat lépéseit ábrázoló diagram. Segítségével grafikusan tudjuk ábrázolni az algoritmusokat. Lehet részletező, amikor egyes lépéseket külön folyamatábra-elemként adunk meg, míg az áttekintő folyamatábra esetében több szinten dolgozunk. Itt hierarchikus a megjelenítés, a részproblémák további részproblémákra bonthatóak, egészen amíg részletező folyamatábráig nem jutunk. A folyamatábra építőelemeit különböző formájú geometriai alakzatok és az azokat összekötő irányított vonalak alkotják. Az alakzatok mind egy-egy művelettípust reprezentálnak, míg a vonalak az algoritmus végrehajtásának irányát mutatják. Ezek segítségével lépésről-lépésre le tudjuk írni az algoritmust.

16

A folyamatábrák a leggyakrabban az alábbi építőelemekből épülnek fel: 

Az algoritmus kezdete és vége: egy ellipszissel szimbolizáljuk, melyekbe a START és END feliratokat írjuk. Minden algoritmus egy ilyen elemmel kezdődik és ér véget.



Irányított vonalak: nyilakkal vannak ellátva, ezzel jelölik az algoritmus futásának irányát.



Input és utput: az adat be-, illetve kivitelét egy paralelogramma jelöli, mely az adott művelet nevét tartalmazza



Értékadások és általános műveletek: ezeket téglalappal jelöljük.



Elágazások: rombusszal jelöljük, az előző elemekkel szemben két kimenete van, melyek az igaz/hamis ágak. Hozzá érkezve a feltételtől függően a vezérlés az igaz vagy a hamis ágon folytatódik tovább.

4. ábra: folyamatábrák építőelemei (Folyamatábrák, 2015)

A fenti elemeken kívül további elemek is szerepelhetnek a folyamatábrákban, de azoknak használata nagyon ritka.

17

2 Rendezési algoritmusok A rendezési algoritmusok megalkotása és elemzése az algoritmuselmélet egyik leggyakoribb témája. A mai napig sok kutatást szentelnek rájuk és folyamatosan találják fel az újabb, jobb teljesítményű rendezéseket. Sok esetben elengedhetetlenek számunkra, mivel a programunk soron következő algoritmusai megkövetelik az adatok rendezettségét. Műkodésük során leggyakrabban tömbök elemei szolgálnak bementként , mivel ezek véletlenszerű hozzáférést engednek meg, ellentétben a listával, mely csak szekvenciálisat. Rendezett formájuk sokféle lehet, de leggyakrabban a numerikus vagy a lexikografikus sorrend használt. A rendezés feladatát a következőképpen definiáljuk: Bemenet: n számot tartalmazó sorozat. Kimenet: a bemenet sorozat olyan permutációja (újrarendezése), amelyre a´1 ≤ a´2 ≤ ... ≤ a´n . (Cormen et al., 2001, 1.o )

2.1 Rendezési algoritmusok osztályozása 

Összehasonlítások számának komplexitása (legrosszabb, átlagos és legjobb esetben)



Cserék számának komplexitása



Memória-, és egyéb források használata



Rekurzió. A legtöbb rendezési algoritmus rekurzív vagy nem rekurzív, de léteznek olyanok is, melyekre mindkettő igaz.

A rendezési algoritmusokkal kapcsolatban több szempont szerinti igény léphet fel. Ilyenek az alábbiak: 

Helyben rendezés, azaz a rendezés eredménye az eredeti helyén jelenjen meg, legfeljebb konstans méretű többletmemória felhasználása révén.



Gyorsaság. A rendezési idő legyen minél rövidebb. 18



Adaptivitás: Az algoritmus használja ki a kulcsok között már meglévő rendezettséget.



Stabilitás: A rendezés őrizze meg az azonos kulcsú rekordok esetén a rekordok egymáshoz képesti sorrendjét.



Az algoritmus csak a kulcsokat rendezze a rekordokra mutató pointerekkel, vagy az összes rekordot mozgassa.



Belső rendezés legyen (csak a belső memóriát vegye igénybe a rendezéshez), vagy külső rendezés legyen használva.



Optimális legyen a rendezési algoritmus, vagy sem.



Az összes rendezendő adatnak rendelkezésre kell-e állnia a rendezés folyamata alatt, vagy sem.



A rendezésnek csak a befejeztével van eredménye, vagy menet közben is a már rendezett rész tovább nem változik.



Összehasonlításon alapuljon a rendezés, vagy azt ne vegye igénybe az algoritmus. (Házy et al., 2011)

2.2 Bonyolultság Természetes elvárás, hogy szeretnénk a programunkban szereplő algoritmust a legjobbnak, lehető leghatékonyabbnak tudni, ezért be kell bizonyítanunk, hogy az elvárásainknak megfelelően működik. Általánosságban

elmondhatjuk,

hogy

a

bonyolultság

az

adott

funkció

végrehajtásához szükséges meghatározott erőforrás-mennyiség fokmérője. Ez alatt leggyakrabban az időigényt és a memóriaigényt értjük, de előfordulhatnak algoritmusok, melyek esetében akár a számítógép belső adatátviteli sávszélességének figyelembevételére is szükségünk lehet. Az algoritmusok időigénye elsősorban a bemeneti adat méretétől, és a bemenetre érkező adatok mennyiségétől függ. A műveletek pontos számát rendszerint nincs szükségünk mérni, sokkal fontosabb, hogy miként változik a végrehajtott műveletek száma a probléma méretével.

19

2.3 Bonyolultsági osztályok Az algoritmusok bonyolultságát a funkció végrehajtásához szükséges műveletek számának nagyságrendjével definiálhatjuk a nagy ordó jelölést használva, mely az „order of“, azaz nagyságrend szóból ered. (Harris et al., 2006) Az egyes algoritmusok, ezen belül az általunk választott rendezések konkrét bonyolultságának elemzését a munka későbbi részében fogjuk kifejteni, ám előtte a leggyakrabban alkalmazott nagyságrendek listáját mutatnánk be.

2.3.1 Konstans idő O(1) Elméletben ez az algoritmus ezen futási idő esetében egyetlen művelet igénybe vételével hajtja végre az adott funkciót. Bár ez lehetséges, a gyakorlatban az O(1) idő tulajdonképpen annyit jelent, hogy az algoritmus konstans ideig fut; azaz a probléma mérete által nincs befolyásolva a teljesítménye. Erre jó példaként hozhatóak fel az olyan egyszerű funkciók, mint a számítógép operatív memoriájának címzése, vagy a tömbökben való keresések, melyek garantáltan O(1) ideig tartanak. Az ilyen bonyolultsággal rendelkező algoritmusok esetében a végrehajtáshoz szükséges idő mindig állandó lesz, ám ez még nem garantálja egyben a program gyorsaságát is, így nagyon nehéz ebben az időben dolgozó jó algoritmust találni. Előfordulhatnak olyan esetek, melyekben a futási idő lehet akár több hét is, és ennek ellenére az algoritmus még mindig az O(1) kategóriába fog tartozni.

2.3.2 Lineáris idő: O(n) Az O(n) futási idejű algoritmusok általában elfogadhatóak. Hatékonyságuk legalább olyan jónak tekinthető, mint a konstans idejűeké, így a lineáris időre gyakran tekintenek egy algoritmus kívánatos tulajdonságaként. Ha az algoritmus által használt műveletek száma egyenesen arányos a feldolgozandó elemek számával, akkor O(n) nagyságrendről beszélhetünk. Ide tartoznak például az olyan műveletek, mint egy rendezett tömbben való lineáris keresés,

tömbök

legkisebb

vagy

legnagyobb

elemének

végigolvasása, és a Counting sort, azaz a leszámoló rendezés is. 20

megkeresése,

tömbök

2.3.3 Kvadratikus idő: O(n2) A kvadratikus, vagy O(n2) algoritmusok futási ideje négyzetesen arányos a bemeneti elemek számával. Ide tartozik például a buborékrendezés, beszúró rendezés vagy a bináris beszúró rendezés is. Bármely algoritmus kvadratikusnak mondható, ha két ciklust használ működése során; az egy külső, és egy belső ciklus n-szer ismétlődik, mely esetben n az elemek száma egy bizonyos számsorozatban. „A kvadratikus idővel futó algoritmusok a programozók legvadabb rémálmaiban jelennek meg; bármely O(n2) bonyolultságú algoritmus kizárólag a legjelentéktelenebb problémák megoldására alkalmas.“ (Harris et al., 2006, 8.o)

2.3.4 Logaritmikus idő: O(log n) és O(n log n) A logaritmikus algoritmus futási ideje a probléma méretének logaritmusával együtt növekszik. Ez leggyakrabban kettes alapú növekedést jelent, mivel a számítógépek a bináris számrendszerben dolgoznak. Hasonló nagyságrendű algoritmusok használatosak például a bináris fákkal való dolgozás, vagy a bináris keresések során. Egy O(log n) időigényű algoritmus nagyon hatékonynak mondható, mivel a befejezéshez szükséges műveletek száma folyamatosan csökken a futás során. Jó példa erre egy string típusú bemeneti adat állandó félbevágása. Ezen művelet elvégzésére O(log n) időre lesz szükségünk (melyben n a szöveg hossza), mivel minden egyes alkalommal a szöveg hossza a felére csökken. Az O(n log n) időt szokás még linearitmikus idejű bonyolultságként is nevezni. Ez az időigény azon esetekben következik be, mikor egy adott algoritmus egy logaritmikus, azaz O(log n) funkciót n-szer futtat le.

2.4 Összehasonlításokon alapuló rendező módszerek Az összehasonlításokon alapuló rendezési algoritmusok mind azt az elvet követik, hogy a bemeneti tömb elemeit bizonyos mennyiségű összehasonlításokat követően rendezik a helyükre. Ezen módszer létező legegyszerűbb rendezési formája, mint a neve is mutatja, a Simple Sort, azaz az egyszerű cserés rendezés. 21

Implementálásának könnyűsége ellenére a gyakorlatban szinte egyáltalán nem használt, több más általánosan elfogadott rendezési algoritmust alkalmaznak a kisebb méretű bemenetek rendezésére is. Ezáltal a munkánkban is csak érdekességként tüntetjük fel működési elvét és annak grafikus ábrázolását, ám további mélybemenő elemzésébe nem bocsátkozunk. Működésének alapelve, hogy a tömb első elemét összehasonlítjuk a többi mögötte állóval, és ha valamelyik kisebb nála, akkor megcseréljük azokat. Ezzel elérjük, hogy a sorozat első helyére a már legkisebb elem kerül, így a további rendezést már csak a megmaradt résztömbön kell folytani.

5. ábra: SimpleSort (kódrészlet)

2.4.1 Beszúrásos rendezés A beszúrásos rendezés egyike a legegyszerűbb rendezési algoritmusoknak, mely a végső, rendezett tömböt egyesével építi fel. Nagy adatmennyiség feldolgozása esetén rosszabb teljesítményt produkál mint a modern és fejlett rendezések, ám kisszámú elem rendezésére kifejezetten hatékony. Több előnnyel is rendelkezik: 

Egyszerű implementáció: a szerkezete könnyű, akár pár sorral is kifejezhető a programkódban.



Kevés adat esetén hatékony, és a gyakorlatban gyorsabb a többi kvadratikus algoritmusnál, mint például a kiválasztó vagy a buborékrendezés.



Stabil, azaz nem változtat a hasonló kulcsú elemek sorrendjén.



Adaptív, azaz az előre rendezett adatokat figyelembe veszi és az alapján dolgozik velük.



Helybeni, azaz kevés, O(1) memóriára van szüksége.



Online, azaz képes a rendezésre amint az adatokat megkapja. 22

Az emberi gondolkozáshoz közel álló rendezési algoritmus, melyben a rendezés menete leginkább egy kártyajáték játékmenetéhez hasonlítható. Az asztalon elhelyezkedő lapokat egyesével vesszük fel a kezünkbe, és azok számértéke szerint helyezzük el őket a kezünkben a megfelelő helyre. Ahhoz, hogy a helyüket megtaláljuk, a felvett lapot mindig összehasonlítjuk a már kezünkben levő kártyákkal, így a már nálunk levő lapok minden esetben rendezettek lesznek. A módszer alapgondolata tehát nagyon egyszerű. Tegyük fel, hogy az A[1:k] résztömb már rendezett. Ezt használva rendezzük az A[1:k+1] résztömböt. Az algoritmus elején, amikor k=1, a feltétel nyilván teljesül. Igaz ez a kártyajáték közben is, hiszen az első felhúzott lap a kezünkben önmagában rendezve lesz. Ezután sorba léptetve k-t rendezzük az A[1:2], A[1:3], ..., A[1:n-1], A[1:n] tömböket. Jelen esetben ez a kártyák folyamatos húzásának felel meg, tehát a második lap felhúzását követően megnézzük, hogy az előző laphoz viszonyítva hová kerül, a harmadik lap után pedig az első kettőt vizsgáljuk. Így megyünk végig egészen addig, amíg már nem marad lap az asztalon. Ezzel végül a feladat megoldásra kerül, a rendezés pedig befejeződik. (Rónyai et al., 1999)

6. ábra: InsertionSort (kódrészlet)

23

2.4.1.1 A beszúró rendezés elemzése Az algoritmus által használt idő függ a bemenettől, tehát sok szám rendezése tovább tart, mint kevésé. Sőt, a beszúró rendezés a bementi elemek rendezettségétől függően akár két ugyanolyan méretű sorozatot is rendezhet különböző idő alatt. Az algoritmus futási ideje legrosszabb esetben az összehasonlítások számának szempontjából akkor valósul meg, ha a bemeneti A tömb fordítottan rendezett. Ezen eset fennálltakor a rendezési algoritmus belső ciklusa minden egyes futásakor a még rendezetlen tömb összes elemét át kell, hogy vizsgálja. Ahhoz, hogy az A[k+1] elem helyét megtalálhassuk, k darab összehasonlítást kell végeznünk. Mindezt k = 1, 2, ... , n-1 esetekre összeadva az összehasonlítások számára kapjuk, hogy:

Az elemcserék számának szempontjából is hasonló a helyzet, ilyenkor is a fordítottan rendezett bemeneti A tömb adja a legkedvezőtlenebb esetet. Ekkor az A[k+1] elem beillesztéséhez az A[1..k+1] résztömb összes elemét mozgatni kell, ami összesen k+1 mozgatást jelent. Ezen k=1, 2, ..., n-1 eseteket sorra véve az elemcserék számára kapjuk, hogy:

Az algoritmus futási ideje átlagos esetben sem tér el sokban a legrosszabb esettől, bonyolultsága szintén O(n2), ám a legjobb esetben már nagyon jó eredményeket produkál. Ez akkor fordul elő, ha a bemeneti tömb már előre rendezett. Ebben az esetben az algoritmus minden ciklikus lépés során csak a bemeneti tömb első megmaradt rendezetlen elemét hasonlítja össze a rendezett résztömb jobb oldali utolsó elemével. Ezáltal a beszúrásos rendezés lineáris futási idővel rendelkezik, azaz O(n) időigényű. (Iwatt et al., 2004)

24

2.4.2 Buborékos rendezés A buborékos rendezés szintén egy egyszerű, könnyen implementálható algoritmus. Az eljárás nem túlzottan hatékony, ezért inkább az algoritmuselmélet oktatása során használják, mintsem gyakorlatban. Rövid kódjának köszönhetően könnyen átírható tömb helyett listával megadható bemenetre, így kis sorozatok rendezése során hasznos tud lenni. Működésének elképzeléséhez vegyünk egy függőleges helyzetben álló tömböt, melynek utolsó eleme van legfelül, míg első eleme legalul. Ebben a tömbben az elemek buborékszerűen viselkednek. A nagyobb elemek könnyebbek a kisebbeknél, ezáltal mindig felfelé mozognak, míg a a nehezebb elemek pedig a tömb aljára süllyednek. Rendezésének alapötlete, hogy a rosszul álló szomszédos elempárokat felcseréljük. Ha valamely i-re igaz az, hogy a tömb azon sorszámú cellája kisebb a szomszédjánál, akkor azokat felcseréljük. Ezen elv alapján a tömb elejétől elindulva a rosszul álló szomszédos elemeket felcserélve eljutunk a tömb végéig, amikor már a tömb legnagyobb eleme a helyén, azaz az A[n] helyen van. Utána megismételjük ezt az A[1 : n-1], majd az A[1 : n-2], stb résztömbökre, amíg végül már elfogynak a rosszul álló párok, és a tömbünk rendezetté válik.

7. ábra: BubbleSort (kódrészlet)

2.4.2.1 Buborékos rendezés elemzése Az egyetlen jelentős előnye ezen rendezésnek a többi más gyakrabban használt algoritmussal szemben, hogy képes észrevenni a bemeneti tömb rendezettségét. A legjobb esetben így a bonyolultsága csak O(n).

25

A rendezés bonyolultsága legrosszabb és átlagos esetben is azonos. A külső ciklus j változója vezérli az aktuális A[1..j+1] résztömb méretét, a belső ciklussal pedig végigvizsgáljuk azt. Ezáltal az elvégzett összehasonlítások száma rendre n-1, n-2, ..., 2, 1 lesz. Ezeket összeadva az összehasonlítások számára kapjuk, hogy

Az elemcserék számának szempontjából legkedvezőtlenebb eset akkor áll fent, ha a bemeneti tömb fordítva rendezett. Ekkor minden egyes összehasonlítása során az algoritmusban sor kerül cserére is. (Fekete et al., 2009)

2.4.3 Koktélrendezés A buborékos rendezés feljavított változata. Programkódja és annak implementálása csak egy kicsivel bonyolultabb annál, de stabil marad, és kiküszöböli a „nyulak és teknősök probélmáját“. Az említett probléma abból áll, hogy az egyes elemek pozíciója a buborékrendezés során hatalmas szerepet játszik a teljesítmény változásában. Nagy elemek a lista elején nem jelentenek problémát, mivel gyorsan kicserélődnek. Ezzel szemben a kis számok már nagyon lassan süllyednek a helyükre. Az algoritmus ciklusának első végrehajtása során végignézi a tömb elemeit, kicseréli a rosszul elhelyezkedő elemeket, és a legnehezebb elemet a tömb végére „úsztatja“. Míg a bubble sort ciklusa ezzel véget ér, és kezdi újra előlről, addig a koktélrendezés egy következő lépésbe áll át. Ekkor a ciklus a végétől visszafelé, egészen a tömb elejéig vizsgálja át a tömböt, újra egyenként összehasonlítva az elemeket, ám most már a legnehezebb elemeket „süllyeszti“ a tömb aljára. Ezáltal már a javított algoritmus képes a buborékrendezésnél jobb eredményeket elérni, ám használata még mindig nem túl gyakori, szintén inkább az algoritmuselmélet tanítása során alkalmazott.

26

8. ábra: CocktailSort (kódrészlet)

2.4.3.1 A koktélrendezés elemzése Mivel ez az algoritmus a buborékos rendezés feljavított változata, így bonyolultságuk is általában egyezik. A legrosszabb és legkedvezőtlenebb esetben ez O(n2). Legjobb esetben viszont egy már rendezett, vagy majdnem rendezett tömb esetében az algoritmus időigénye közel kerül az O(n) -hez. Ez azt jelenti, ha a bemeneti tömb minden eleme olyan helyen áll, mely legfeljebb k(k ≥ 1) pozícióval tér el a végleges elhelyezkedésétől, akkor a koktélrendezés bonyolultsága O(k*n) lesz.

2.4.4 Kiválasztásos rendezés A kiválasztásos rendezés egy újabb egyszerű rendezési algoritmus, mely nagy számú beviteli adatok rendezésére nem ajánlott, ám a már említett buborékos rendezésnél jobban teljesít. Megjegyzendő, a már fentebb említett rendezési módszerekhez hasonlóan ez is megkívánja, hogy a rendezés megkezdése előtt minden egyes elem jelen legyen, és egyesével generálja a végső sorozatot. Valójában ez a beszúrásos módszer ellentéte, ahol a

27

bemeneti adatokra egymás után van szükség, de a végső sorrend a rendezés befejeződéséig nem ismert. Két fajta változata létezik. A minimum-, és maximum kiválasztásos rendezés. Mindkettő rendezésének alapötlete az, hogy a rendezendő tömbünk legkisebb (legnagyobb) elemét kicseréljük a tömb legelső (legutolsó) helyen álló elemével. Ezzel a tömb adott eleme megkapja végső értékét. Az algoritmus futása során két ciklust veszünk igénybe. A belső ciklus segítségével vizsgáljuk sorban az adatainkat, először az első elemet összehasonlítva a tömb többi elemével. Ha helytelen sorrendet talál a program, akkor annak pozicióját ideiglenesen elmenti, és a továbbiakban attól folytatja az összehasonlítást. Ha véget ért a belső ciklus egy köre, a minimumként indexelt tömb elemét kicseréli az első elemmel. Ezt követően a program az eljárást a megmaradt résztömbökre ismétli amíg az összes elem a helyére nem kerül.

9. ábra: SelectionSort (kódrészlet)

2.4.4.1 A kiválasztásos rendezés elemzése Ezen módszer esetében az összehasonlítások száma nem függ a bemeneti tömb elemeinek kezdeti állapotban lévő sorrendjétől. A külső ciklus minden esetben ugyan annyiszor fog lefutni. Első futásnál n-1, a másodiknál n-2, ..., az n-1 –edik futásánál pedig egy összehasonlítás fog történni. Ezáltal a következőt kapjuk az összehasonlítások számára a legkedvezőtlenebb esetben:

Az elemcserék számának szempontjából a legkedvezőtlenebb esetet akkor kapjuk, ha a bemeneti tömb fordítva rendezett. Ilyenkor ahhoz, hogy az utolsó helyen álló elemet az első helyre mozgathassuk, n-1 számú elemcserére van szükségünk. 28

Ez így folytatódik egészen az utolsó, A[n-1..n] résztömbig, amikor már egy darab cserét kell elvégeznünk. (Rónyai et al., 1999) Ebből kapjuk, hogy az elemcserék száma:

2.5 Oszd meg és uralkodj elv Ezen elv lényege azon alapul, hogy az adott problémát a program megpróbálja minél több részproblémára felosztani, melyek bár az eredeti problémához hasonló jellegűek, a megoldhatóságuk és időigényük sokkal kisebb és hatékonyabb annál. Ezeket a részproblémákat a továbbiakban rekurzív módon próbálja az algoritmus megoldani, tehát ha szükséges, a részproblémákat újból felosztja kisebb problémákra egészen addig, amíg könnyedén meg nem oldhatóak. Mindezek után az elv utolsó lépéseként a megoldott részproblémákat összekombinálva eljut az eredeti probléma végleges megoldásához. A megosztás és uralkodás elve az alábbi három lépésre bontható: 

Felosztás: az első lépés, melyben a probléma felosztása történik kisebb részproblémákra. Rendezési algoritmusok esetében ez azt jelenti, hogy egy n elemű rendezendő bementi tömböt két n/2 elemű tömbre osztjuk fel.



Uralkodás: Ezen lépésben történik a részproblémák rekurzív módon való további felosztása. Ha már az adott részprobléma kellően kis méretű, akkor az algoritmus egy egyszerű módszert használva megoldja a részproblémát. Az említett példához viszonyítva, ez a rendezési algoritmusok esetében annyit jelent, hogy addig osztjuk a bemeneti tömböt, míg a rendezés könnyedén elvégezhetővé nem válik.



Egyesítés: utolsó lépésként a megoldott részproblémák egyesítésre kerülnek, vagyis a rendezett részhalmazokat az algoritmus összefésüli.

29

2.5.1 Kupacrendezés A kupac elképzelhető egy bináris fa tömbben való ábrázolásaként. A fa minden csúcsa megfelel a tömb egy elemének, amiben a csúcs értékét tárolja. A fa minden szintjének kitöltöttnek kell lennie, kivéve a legalacsonyabb szintet, ahol balról jobbra haladva csak egy bizonyos csúcsig vannak elemek elhelyezve.

10. ábra: bináris fa tömbben (Fekete et al., 2013, 12. o)

Egy kupacot alkotó tömb két tulajdonsággal rendelkezik. Az első a tömb hossza, azaz hossz[A], mely a tömb elemeinek számát foglalja magába. A második pedig a tömbben tárolt kupac elemeinek számát tartalmazza, azaz a kupac-méret[A]. A fa gyökere a tömb A[1]-edig elemének felel meg, és ha i a fa egy csúcsának tömbbeli indexe, akkor őse a Szülő(i), jobb oldali gyerekének Jobb(i), és baloldai gyerekének Bal(i) indexe az alábbi módon egyszerűen kiszámítható: Szülő(i) : return [i/2] Bal(i): return 2i Jobb(i): return 2i+1

A számítógépen alkalmazott kupacrendezés használata során a Bal eljárásban levő 2i értékét az i balra léptetésével számolhatjuk ki. Hasonló az eljárás a Jobb használata során is, ugyanis ilyenkor hasonlóan az i értékét eggyel balra léptetjük úgy, hogy a belépő legalacsonyabb helyi értékű bit 1 legyen. 30

A szülő eljárásban az [i/2]-t az i eggyel jobbra léptetésével számoljuk ki. Ezt a három eljárást gyakran makróként vagy in-line eljárásként készítik el. (Cormen et al., 2003) A bináris kupacoknak két fajtáját különböztetjük meg: a minimum-, és maximumkupac. Mindkét fajta esetében a csúcsok értékei kielégítik a kupactulajdonságot, melynek jellemző tulajdonságai fajtánként eltérhetnek. A maximum-kupac esetében minden i, gyökértől különböző eleme az alábbi kupactolajdonsággal rendelkezik: A[Szülő( i ) ≥ A[ i ], Azaz az adott elem értéke legfeljebb akkora, mint a szülőjének értéke. A minimum-kupac esetében ez épp ellentétes: A[Szülő( i )] ≤ A[ i ].

A továbbiakban bemutatjuk a rendezési algoritmusok által használt eljárásokat és azok alkalmazását. 

Maximum-kupacol eljárás, melyet a maximum-kupactulajdonság fenntartásához használunk.



Maximum-kupacot-épít eljárás, mely a bemeneti tömb elemeiből egy maximumkupacot épít fel.



Kupacrendezés eljárás, mely segítségével az algoritmus helyben rendezi a tömbünket.

2.5.1.1 Maximum-kupacolás Ez az eljárás fontos a maximum-kupacok kezelésének szempontjából. Az A tömb és egy i indexe alkotják a bemeneti adatait. Az eljárás meghívásakor feltételezzük, hogy a Bal(i) és Jobb(i) gyökerű részfák maximum-kupac szerkezetűek, de A[i] értéke kisebb lehet a gyerekeinél, amivel a maximum-kupactulajdonságot megsértheti. Ezen eljárás feladata, hogy az A[i] értékét lefelé mozgassa úgy, hogy végül az i gyökerű részfa kupaccá váljon.

31

11. ábra: maximum-kupacolás (kódrészlet)

2.5.1.2 Maximum-kupac építése A maximum-kupacol eljárást felhasználva alulról felfelé haladva az A[1..n] tömböt kupaccá alaktíjuk. Az építés során csak a csúcsokon kell végighaladnunk, mivel a tömbünk A[( [n/1]+1)..n] levelei levelek, melyek egyelemű kupacnak tekinthetők.

12. ábra: maximum-kupac építése (kódrészlet)

2.5.1.3 Kupacrendezés Az algoritmus a maximum-kupacot-épít meghívásával kezdődik, amely az A[1..n] tömböt maximum-kupaccá alakítja. A legnagyobb elem az A[1] elemben található, tehát felcseréljük az A[1] és A[n] elemeket és a legnagyobb elem a helyére kerül. Ezáltal az n számát eggyel csökkentve a legnagyobb elem helyét már kizárhatjuk a kupacból. A megmaradt A[1..(n-1)] elemeket ismét maximum-kupaccá alakítjuk, csak az új gyökérelem miatt

hívjuk

meg

a

maximum-kupacol(A,1)

funckiót,

mivel

az

sértheti

a

kupactulajdonságot. Ezt az eljárást ismételjük a kupac méretét állandóan csökkentve, amíg az n el nem éri a 2-t. (Rónyai et al., 1999)

32

13. ábra: Kupacrendezés (kódrészlet)

3. Rendezési algoritmusok vizualizációja Munkánk célja, hogy az eddigiekben ismertetett rendezési algoritmusok gyakorlati működését grafikus eszközök segítségével ábrázoljuk a felhasználó számára, ezzel pedig egy teljesebb képet kaphat azok viselkedéséről. A program elkészítésére a Borland Delphit válaszottuk, ezen belül annak 2005-ös szerkesztői verzióját. A vizualizáció használatához egy egyszerű oszlopdiagramos megjelenítést fogunk alkalmazni, melynek oszlopai a bemeneti tömbök egyes elemeinek felelnek meg. A program elkészítése során nagy figyelmet fektettünk az egyértelműségre és a folyamatosságra, így a felhasználó bármiféle használati útmutató nélkül is képes annak használatára. Az alkalmazás főbb funkcióival, és azoknak részletesebb leírásával a továbbiakban fogunk foglalkozni.

3.1 Tömbök megadása Ahhoz, hogy a vizualizáció véghez mehessen, először is egy bemeneti tömbre van szükségünk, amit a későbbiekben rendezni fogunk. Megadását a felhasználó kétféleképpen is megteheti. Ennek kivitelezésére két lehetőség áll rendelkezésre, a „véletlenszerű számok és „saját számok megadása“ feliratú gombok. Mindkettő megnyomása esetén először egy Edit komponens válik elérhetővé, mely elkéri a kívánt tömb nagyságát. A „véletlenszerű számok“ választását követően a program véletlenszerű számokat generál ki, és ezeket menti bele a tömb egyes elemeibe. A saját számok megadása esetén a tömb méretének bekérése után elérhetővé válik egy StringGrid elem is, melynek hossza a kívánt tömb mérete szerint változik. Ezekbe a cellákba írva a felhasználó megadhatja az elemeinek konkrét értékét. 33

14. ábra: tömbök megadása

Miután a bemeneti adatok bevitelre kerültek, az azoknak megfelelő oszlopdiagram kirajzolódik és egy új funkció válik elérhetővé.

3.2 A rendezetlen tömb kirajzolása A bemeneti adatok változtatása után a program automatikusan kirajzolja az oszlopokat egy Image komponens vásznára. Ezt a véletlenszerű megadás választása esetén az Edit, míg a saját számok megadásakor a StringGrid elem OnChange eseményének hívásakor viszi végbe a program. A rendezetlen és a rendezett tömb esetében is beépítettünk egy skálázást, mely a bevitt tömb nagyságához arányosan méretezi és helyezi át a tömböt a kellő pozícióba.

15. ábra: oszlopok skálázása (kódrészlet)

34

Ezeket a számításokat használva a tömbök mérete a képeken négy különböző méretben állhatnak elő, attól függően, hogy mekkora a megadott tömb. A méretek mellett egy belső eltolás is alkalmazva van, mely folyamatosan a kép közepére rendezi a tömböket.

15. ábra: oszlopok skálázása: 5, 15, 25, 40 elem esetén

3.3 Rendezési mód kiválasztása A bemeneti adatok bevitelét követően ez a következő funkció, mely a felhasználó számára elérhetővé válik. Itt kiválaszthatja, hogy mely rendezést használva kívánja sorba rakni a tömbök elemeit. Ez a funkció a későbbiekben már állandóan elérhető lesz, hogy lehetőség szerint képesek legyünk lefuttatni több rendezési formát is ugyanazon tömbre.

16. ábra: rendezés kiválasztása

A hat rendezés közül valamelyik kiválasztása után újabb két funkció válik a programban elérhetővé.

35

3.4 Sebesség beállítása A rendezés kiválasztása után elérhetővé válik a sebesség beállítása, mely egy ScrollBar komponens segítségével, pontosabban annak is az OnChange eseményével valósul meg. Helyzetének értékét a későbbiekben egy wait nevű procedúra fogja használni, mely a programon belüli ciklusok futását késleltetésre kényszeríti.

17. ábra: várakoztató eljárás (kódrészlet)

A procedúrát legtöbbször egy sebesség változó segítségével hívjuk meg, mely a ScrollBar jelenlegi pozícióját menti magába, és ebből az adatból számított ideig utasítja késleltetésre a programot. A ciklus addig fut, míg el nem éri a kellő időhatárt, vagy be nem zárjuk a programot. Egy harmadik eset is előfordulhat, mikor a sebesség változó nullás értéket kap, ám ezt csak később, a szüneteltetés funkció során elemezzük.

3.5 Rendezés indítása A program legfontosabb része a gomb, mely elindítja a kívánt rendezési algoritmust. Megnyomását követően elérhetővé válik két új funkció is, melyek a szüneteltetés és a gyors lefuttatás. Ezeken és a sebesség beállításán kívül az összes többi funkció ideiglenesen inaktív lesz. A rendezés megkezdése előtt szükséges kifejtenünk néhány nagyon fontos, a vizualizáció szempontjából elengedhetetlen eljárást.

36

3.5.1 Vászon törlése Minden rajzolási animációt egyenként viszünk végbe a program futtatása során. Minden egyes új elem kirajzolásakor szükség van arra, hogy először letöröljük a már meglévő vásznat. Erre a következő, törlés eljárást használjuk.

18. ábra: vászon törlése (kódrészlet)

3.5.2 Tömb kirajzolása A törlés után következhet a tömb újbóli kirajzolása már a változott értékekkel, melyet a kirajzolás eljárás biztosít számunkra.

19. ábra: tömb kirajzolása (kódrészlet)

A kirajzolandó négyzet első és harmadik adata függ a tömb elemeitől, ezek tartalmazzák az elhelyezkedési koordinátájukat az x1 és x2 részeikben, melyeket a tömb kigenerálása során kapnak. A negyedik paramétert a tömb x4 elemével számítjuk ki, melyek már a felhasználó által is ismert adatok, ezek tartalmazzák ugyanis az egyes elemek értékét, azaz az oszlopok magasságát.

3.5.3 Szüneteltetés, léptetés és gyors lefuttatás Mindhárom gomb programkódja rövid, valójában csak a nekik megfelelő változókat állítják be a megfelelő értékekre, és teszik elérhetővé, vagy éppen elérhetetlenné egyes gombok használatát. A rendezést indítva a szüneteltetés nevű gomb elérhetővé válik, melyet megnyomva lehetőségünk van léptetni a programunkat, vagy esetlegesen tovább folytatni annak futását. 37

A léptetés gomb a léptet változó értékét állítja nullára. Ezzel lépegethetünk az egyes, a rendezés algoritmusának kódjába beépített „várakozási kapuk“ közt. A gyors lefuttatás gombot megnyomva szintén csak a sebbesség változónkat állítjuk nullára, ezáltal a wait funkció már nem fogja kényszeríteni az algoritmust késleltetésre, így a rendezés másodperceken belül befejeződik.

20. ábra: szüneteltetés, léptetés, gyors lefuttatás

Az említett funkciók implementációját és használatát a későbbiekben, a rendezés menetének elemzése során fogjuk bemutatni.

3.5.4 A rendezés előkészületei Első lépésként a program ideiglenesen átmenti a rendezni kívánt tömb értékeit egy másik tömbbe. Erre azért van szükség, hogy a rendezés teljes lefutása után az értékeket visszamentve lehetősége legyen a felhasználónak a már előzőleg megadott tömbjét újrarendezni egy másik rendezési formát kiválasztva. A program jobb oldalában megjelenik egy másik Image komponens is, melynek vásznára a rendezés alatt álló tömb lesz mindig rajzolva. Miután kezdésként felrajzoltuk a vászonra a még rendezetlen tömböt, kezdődhet annak rendezése. Először egy feltétellel megvizsgáljuk, hogy a felhasználó melyik rendezési módszert választotta, és annak mefelelően egy esetválasztással folytatjuk az adott rendezéseket.

21. ábra: rendezés megadása (kódrészlet)

38

3.5.5 A rendezés menete Az egyes rendezési menetek a tulajdonságaiktól függően csak kevésben térnek el egymástól, ezért egy adott rendezési forma működését fogjuk a továbbiakban elemezni. Jelen esetben ez a BubbleSort, avagy a buborékos rendezés lesz. Az algoritmus első soraiban átállítjuk a combobox elemünk nevét, ezzel informálva a felhasználót arról, hogy éppen melyik rendezés van folyamatban. Emellett beállítjuk a rendezéshez szükséges változók értékeit.

22. ábra: változók beállítása (kódrészlet)

Mint ahogy azt már a munkánk eddigi részében megismertettük, a buborékos rendezés elindul a tömb első elemétől, és összehasonlítja a szomszédos párokat. Ilyenkor először kék színt állítunk be, és a két elemet újrafestjük, ezzel ábrázolva, hogy az algoritmus éppen melyik két elemmel dolgozik. Utána a sebességnek megfelelően a wait eljárást meghívva késleltetjük a ciklus továbbindulását.

23. ábra: összehasonlítás és késleltetés (kódrészlet)

Ezt követően lesz szükségünk egy „léptető kapura“, ami arra szolgál, hogy amíg a szüneteltetés gombunk lenyomva van, addig ezen a ponton a ciklus nem halad tovább, kivéve ha a folytatás vagy a léptetés gomb meg lett nyomva.

24. ábra: változók beállítása (kódrészlet)

39

A program tovább futtatása után következik a rendezési algoritmus egy megkövetelt kódja, amely megvizsgálja, hogy a már az előzőekben kékkel befestett oszlopok helyes sorrendben állnak-e. Ha ez a feltétel igaz, akkor sor fog kerülni cserére. Ezt a felhasználó számára egy villogással tesszük egyértelművé, melyet a villogás nevű eljárás meghívásával hajtunk végre. Ez az eljárás valójában csak annyit tesz, hogy az oszlop színeinek gyors váltogatásával éri el a kívánt vizuális hatást. Ezután egy újabb kapuhoz érkezünk, mely szüneteltetés esetén a továbbindulás pillanatáig folytatja a villogást.

25. ábra: villogás (kódrészlet)

Ha a villogás már véget ért, sor kerülhet az elemek cseréjére. A csere után a képernyőt letöröljük, és piros színt beállítva újra kirajzoljuk azt, de már az új adatokkal.

26. ábra: csere (kódrészlet)

Mivel a tömbünk eddig még csak piros volt, ami a rendezetlenség színét jelzi, ezért megpróbáljuk átfesteni zöldre a már helyükön levő elemeket. Ehhez egy léptető nevű változót veszünk igénybe, mellyel a rendezési eljárás végén fogunk találkozni.

27. ábra: kirajzolás (kódrészlet)

40

A továbbiakban már csak azt láthatjuk, hogy ha az algoritmus nem talál helytelenül álló párokat, akkor is átrajzolja a tömböt, utána pedig egy újabb léptetési kapuhoz érkezik. A buborékrendezés szabályaihoz tartva magunkat csökkentjük a külső ciklus változóját, majd a zölddel való rajzolás számlálóját növeljük, amit követve folytatódik a rendezés amíg meg nem kapjuk a rendezett tömbünket. Ekkor a végén még utoljára kirajzoljuk azt, és ezzel a rendezés futása befejeződött.

28. ábra: BubbleSort menete (kódrészlet)

41

Befejezés A munkánk legfőbb célja egy olyan segédeszköz létrehozása, mely segít a felhasználónak a rendezési algoritmusok működésének megértéséhez. Ahhoz, hogy ezt a leghatékonyabban tudjuk elérni, először a munkánk elméleti részében ismertettük az algoritmusokkal kapcsolatos alapfogalmakat. A munkánkat három fő részre osztottuk. Az első fejezetben először egy általános definíciót adtunk az algoritmusokról és a szó eredetéről. Később már egy formálisabb jellemzés érdekében összegyűjtöttük azok általános jellegzetességeit. Leírtuk, hogy miként lehet a feladatokat algoritmizálni és ezek megadására milyen eszközök állnak rendelkezésre. A továbbiakban már a rendezési algoritmusokkal foglalkoztunk. Ezen fejezetben leírtakat implementáltuk a programunkba, így az egyes rendezések elméleti definiálása és gyakorlati működése egyben már egy teljes képet adhat a felhasználónak azok tényleges viselkedéséről. Egy, a bonyolultságról és a bonyolultsági osztályokról szóló jellemzés után megadtuk a kiválasztott rendezési algoritmusok általános működési elvét és részletes elemzését. A munka utolsó fejezetében tértünk rá a rendezések vizualizációjára. Leírtuk, hogy a felhasználó milyen funkciók háttérmunkájának köszönhetően kaphat egy képet az rendezések működéséről. Elgondolásunk szerint helyesen sikerült létrehozni egy olyan oktatási segédeszközt, mely a felhasználót lépésenként vezeti végig a tömb megadásától egészen a rendezés irányításáig, így egy letisztult, egyszerű és áttekinthető alkalmazás keretein belül ismerheti meg a rendezési algoritmusok érdekes működését.

42

Resumé Cieľom záverečnej práce je vytvorenie programu, ktorý graficky simuluje priebeh a jednotlivé postupy triediacich algoritmov. Aby používateľ mohol čo najlahšie používať nášu aplikáciu, najprv budeme venovať teoretickému popisu algoritmov. Naša bakalárska práca je rozdelená do troch kapitol. V úvodnej kapitole sa zaoberáme s pojmom algoritmov. Najprv sme zadali pôvod slova algoritmus, že je odvodené od mena stredovekého matematika Muhammada al-Chorezmiho. Potom sme podali neformálnu, všeobecnú definíciu algoritmov, že sú to konečné postupnosti presne definovaných inštrukcií na splnenie danej úlohy. Môžu, ale nemusia byť len vo forme počítačových programov. Algoritmy sú súčasťou nášho každodenného života, aj naše najjednoduchšie činnosti môžu byť interpretované ako algoritmy. Uviedli sme aké podmienky musia splniť, aby sme získali správnosť algoritmu. Hneď potom sme rozpísali základné vlastnosti algoritmov, aby sme už mohli dostať formálnejšiu definíciu slova algoritmus. Algoritmy majú nasledujúce vlastnosti: konečnosť, špecifikovanosť, vykonateľnosť, vstup a výstup. Zaoerali sme aj s etapmi algoritmizácie úloh. Aby sme mali možnosť nejakú úlohu riešiť pomocou počítača, musíme ju najprv rozdeliť na tri základné etapy: formulácia úlohy, analýza úlohy a zostavenie riešiaceho algoritmu. Potom sme zadali jednotlivé možnosti na udanie algoritmov. Spôsoby udania možu byť rozdelené na dve hlavné časti: spisovné a grafické. Medzi spisovné spôsoby patrí slovné zadanie, zadanie pomocou metasintaxu, pseudokódu, alebo zdrojového kódu. Pseudo-kód sa líši od zdrojového kódu v tom, že pi požívaní pseudo-kódu naše udanie môže obsahovať aj slovne vyjadrené príkazy, a nemusíme dodržiavať žiadne syntaktické pravidlá. Posledný spôsob je požívanie vývojového diagramu, ktorý slúži ku grafickému znázornení jednotlivých krokov algoritmu. Obsahuje obrazy rôzného tvaru, ktoré sú pripojené navzájom pomocou šípkov. V nasledujúcej kapitole sme sa zaoberali so základnými pojmamy triediacich algoritmov. Triediace algoritmy riešia problém triedenia definovanú následovne: Vstup: postupnosť n čísel Výstup: jedna permutácia

43

Rozpísali sme aj triedenie daných algoritmov. Tie sú: využitie pamäte, používanie rekurzie, zložitosť podľa počtu výmen a porovnaní. Triediace algoritmy musia splniť aj nasledujúce pohľadávky: stabilita, optimálnosť, metóda triedenia, rýchlosť a adaptívnosť. Potom sme podali základné pojmy týkajúce sa zložitosti triediacich algoritmov, a podali sme najpoužívanejšie triedy zložitosti, ktoré sú:

O(1)

Konstantná

napr. Jednoduché udelenie hodnoty

O(n)

Lineárna

napr. Counting sort, vypočítavanie n!

O(n)

Odmocninová

napr. Bubble Sort, Insertion Sort

O(log n)

Logaritmická

napr.

binárne

hladanie,

pracovanie

s binárnym stromom

V ďalšej časti sme sa oboznámili s triediacimi algoritmami, ktorí sme používali aj na grafické znázornenie. Prvý z algoritmov je Insertion sort. Princíp algoritmu môžeme vysvetliť na princípe triedenia hráčskych kariet. Keď dostaneme karty do ruky, vždy sa ich snažíme usporiadať podľa ich hodnoty tak, že zoberieme prvú kartu a vložíme ju na správne miesto. Druhým algoritmom bol Bubble sort. Názov dostal vďaka tomu, že menšie prvky sa prebublinkujú na začiatok zoznamu. Je to veľmi známy triediaci algoritmus, pričom je to aj jeden z najmenej efektívnych spôsobov triedenia, preto ho používajú len pri učení algoritmov. Pracuje opakovaným prechodom cez daný zoznam, ktorý má byť utriedený porovnávajúc vždy len dva susedné prvky. Ak algoritmus nájde prvky, ktoré nie sú v správnom poradí, zamení ich. Porovnávanie trvá pokial sú ešte potrebné výmeny. Potom sme vybrali triediaci algoritmus s menom Cocktail sort, alebo Shaker sort. Je aj známy ako obojsmerný Bubble sort, lebo je to varianta triedenia pomocou prebublovania. Líšia sa v tom, že Bubble sort prechádza poľom vždy len jedným smerom, kým pri používaní Shaker sortu triedenie sa deje v oboch smeroch. Ďalším algoritmom bol Selection sort. Je to jednoduchý, ale nestabilný triediaci algoritmus. Je rýchlejší ako ostatné kvadratické algoritmy, avšak ešte stále pomalší než insertion sort. Princíp fungovania je, že algoritmus vždy vyberie z nezotriedenej časti postupnosti prvok, ktorý má najmenšiu alebo najväčšiu hodnotu, a vloží na koniec alebo začiatok zotriedenej časti postupnosti.

44

Ďalej prišiel na rad princíp „rozdeľ a panuj“, ktorým onačujeme tie algoritmy, ktoré riešia problémy rozdelením úlohy. Často sa implementuje rekurzívne a úloha sa stále delí na menšie časti, kým už niektoré úrovne dosáhnu konštantnú komplexitu. Potom len zložíme ich riešenie a dostaneme riešenie pôvodného problému. Posledným algoritmom bol jeden z najlepších všeobecných triediacich algoritmov, Heap sort. Základnou myšlienkou algoritmu je využitie dátovej štruktúry označovaná ako hromada (heap). Je to stromová dátová štruktúra, ktorá spĺňa lokálnu a štrukturálnu podmienku usporiadania. Táto jednoduchá štruktúra umožňuje veľmi efektívne operácie, ako sú napríklad vloženie prvku a výber najväčšieho alebo najmenšieho prvku. V poslednej kapitole Vám predstavíme aplikáciou, ktorá nám graficky znázorňuje fungovanie jednotlivých triediacich algoritmov. Vypracovanie našej práce sme uskutočnili v Delphi programovacom jazyku, v Borland Delphi 2005 textovom editore. Ako najdôležitejšie sme brali do úvahy, aby používateľ bez akýchkoľvek inštrukcií a návodov vedel plynule a bezproblémovo využiť náš program. Potom sme sa pustili do programovania. Najprv sme pristúpili k časti programu, ktorá umožňuje používatelovi zadať vstupné údaje. Má na to dve spôsoby: automatické vygenerovanie náhodných čísiel, alebo vlastné zadanie jednotlivých údajov. Potom sme definovali prácu funkcie, ktorá vykreslí ešte netriedený diagram podla zadaných čisiel. Pri každej zmene vstupných údajov aktualizuje náš obraz a zabudovali sme aj škálovanie, ktoré umožňuje vykreslenie diagramu vždy na stred plátna. Po zadaní údajov už používateľ môže vybrať jeden zo šiestich spôsobov triedenia a rýchlosť behu algoritmu. Uviedli sme aj funkciu, ktorá umožňuje uneskorenie priebehu triedenia, čím už ľahko môžeme znázorniť jednotlivé kroky algoritmu. Potom nasledovala najdôležitejšia funkcia programu, spustenie samotného triedenia údajov. Najprv sme opísali dve funkcie, ktoré umožňujú zmazanie plátna a vykreslenie nových údajov naňho. Sem patria aj funkcie ktoré zabezpečujú pozastavenie, krokovanie zrýchlenie behu algoritmu. V poslednej časti poslednej kapitoly sme vybrali jeden z triediacich algoritmov, ktorý bol bublinkové triedenie, a detailne sme opísali všetky časti kódu. Tie boli: zvýraznenie stĺpcov, blikanie v prípade zmeny, vykreslenie už triedených stĺpcov a implementácia funkcie pozastavenia a krokovania. Sme presvedčení, že sa nám podarilo vytvoriť ľahko a jednoznačne ovládateľný program, ktorý umožňuje používateľovi čo najjednoduchšie aplikovanie v budúcnosti. 45

Irodalomjegyzék CORMEN, Thomas H. - LEISERSON, Charles E. – RIVEST, Ronald L. - STEIN, Clifford Új algoritmusok. Budapest : Scolar Kiadó, 2003. – 992 o.- ISBN 978-963-9193-90-1 CORMEN, Thomas H. - LEISERSON, Charles E. – RIVEST, Ronald L. Algoritmusok. Budapest : Műszaki Könyvkiadó, 2001. – 884 o.- ISBN 963-16-3029-3

KNUTH, Donald H. The Art of Computer Programming: Fundamental Algorithms. 3. kiadás. USA: Addison Wesley Longman, 1997. 650 o. ISBN 0-201-89683-4 KNUTH, Donald H. The Art of Computer Programming: Sorting and Searching. 2. kiadás. USA: Addison Wesley Professional, 1998. 800 o. ISBN 0-201-89685-0 RÓNYAI, L. – IVANYOS, G. – SZABÓ, R. Algoritmusok. Budapest: Typotex, 1999. – 349 o. – ISBN 963-9132-16-0

Internetes források SZABÓ, L. Algoritmusok [online]. Sopron: [2015]. Elérhető az interneten: < https://inf.nyme.hu/~lszabo/konyvek/alg/alg.pdf > HÁZY, A. – NAGY, F. Adatstruktúrák és algoritmusok [online]. [2011. 4. 6.] Elérhető az interneten: < http://www.uni-miskolc.hu/~matnf/adatst/admin/adat_alg.pdf > SCHUSTER, GY. – SÁNDOR, T. Algoritmusok [online]. [2012] Elérhető az interneten:< http://www.uniobuda.hu/users/sandor.tamas/Programozas1_Informatika_labor/algoritmusok.pdf >

SUBECZ, Z. Algoritmusok [online]. [2010] Elérhető az interneten: < http://suzo2.uw.hu/Webprog/Algoritmusok/Algoritmusok.doc > 46

FEKETE, I. – HUNYADVÁRI, L. Algoritmusok és adatszerkezetek [online]. [2013] Elérhető az interneten: < http://tamop412.elte.hu/tananyagok/algoritmusok/lecke17_lap1.html >

Backus-Naur-forma [online]. [2015. 03. 14.] Elérhető az interneten: < http://hu.wikipedia.org/wiki/Backus–Naur-forma >

NIEMANN, T. Sorting and Searching Algorithms: A Cookbook [online]. [2011] Elérhető az interneten: < http://mmhs.ca/ccc/pdfbooks/s_man.pdf >

DALAL, A. CS. Searching and Sorting Algorithms [online]. [2004] Elérhető az interneten: < http://www.cs.carleton.edu/faculty/adalal/teaching/f04/117/notes/searchSort.pdf > Folyamatábrák [online]. [2015] Elérhető az interneten: < http://wiki.prog.hu/wiki/Algoritmus#Folyamat.C3.A1br.C3.A1k > HARRIS, S. – ROSS, J. Kezdőkönyv az algoritmusokról [online]. [2006] Elérhető az interneten: <

http://hu.scribd.com/doc/131694597/Kezdokonyv-az-Algoritmusokrol-2006-eBook-

DigIT#scribd >

47