Programming | Delphi » Keresési és rendezési algoritmusok

Keresési és rendezési algoritmusok Készítette: Németh Veronika III./11tk Építőmérnöki kar Földmérő és térinformatika szak 1998/99 Budapest, 1998.V10 Tartalomjegyzék 1. Rendezési algoritmusok 1.0 Rendezésekről általában 1.1 Beszúrásos (insertion) 1.2 Buborék (bubble) 1.3 Heap 1.4 Minimum-kiválasztásos (exchange) 1.5 Shell 1.6 Quick 1.7 Egyéb speciális rendezések 1.8 Az egyes algoritmusok összehasonlítása 2. Keresési algoritmusok 2.1 Lineáris keresés 2.2 Binális keresés 2.3 Más kereső fák 3. Melléklet - az egyes rendezési algoritmusok programlistája Basic nyelven Németh Veronika Bp.1998V10 1. Rendezési algoritmusok 1.0Rendezésekről általában Ma, a számítógépek világában rengeteg adat áll rendelkezésünkre. Ezeket a megfelelő módon kell kezelnünk, hiszen egy rendszertelen adattömeget nem tudunk jól hasznosítani. A leglényegesebb az adatszerkezet megfelelő kialakítása. Az adatokat általában rendezni is

kell, mert ez később gyorsabb keresést tesz lehetővé. Ám ha nem a gyorsaság a célunk, csak az adatok megléte a fontos, s csak ritkán keresünk benne, akkor ez a rendezés nem feltétlenül szükséges. Sok féle rendezési algoritmus közül választhatunk, a célnak megfelelően Ha sokszor kell rendeznünk egy adatbázist (minden új elem bevitelekor, módosításkor), akkor célszerűbb egy gyorsabb, de bonyolultabb, nagyobb háttérigényű rendezési módszert választanunk. Kisebb adatállomány esetén például nincsen döntő különbség aközt, hogy rendezett vagy rendezetlen tömbben keresünk. Nagy mennyiségű adat esetén azonban rendezés elengedhetetlen, mert a rendezetlenség miatt igen megnő a keresési idő. Mindig mérlegelni kell, hogy mi a fontos számunkra a gyors elérhetőség, vagy az, hogy adatainkat kis helyen tudjuk tárolni. Ebben az esetben tömörítésre van szükség, emiatt a keresés is lassul, mert nem tudjuk az adatokat közvetlenül

elérni. Sorba rendezni többféle feltétel szerint tudunk. Az alapfeltétel, hogy két elem közül egyértelműen meg tudjuk mondani, hogy melyik a nagyobb, melyik kerüljön előrébb / hátrább a rendezett listánkban. Számok esetén ez triviális, nevek esetén általában az ABC sorrendet választjuk, de lehet például betűszám, szótagszám, vagy akár magánhangzók / mássalhangzók száma alapján rendezni. Az alább ismertetett rendezési algoritmusok a legismertebbek, azonban ezen kívül létezik számos egyéb általános és speciális problémákra kidolgozott módszer. 1.1 Beszúrásos rendezés Az egyik legegyszerűbb rendezés. A tömb elejéről indulva vizsgálja az elemeket, és ha talál egy olyan elemet, ami kisebb bármelyik eddig vizsgáltnál, akkor annak megkeresi a helyét a már vizsgált tömbrészben, majd beszúrja oda (így minden egyes követő elemet "feljebb" kell csúsztatni  lásd az ábrán) A cserék érdekében a minimális

értéket előbb egy ideiglenes változóban kell eltárolni, amíg ez az odébbcsúsztatás megtörténik. Előnye a rövid és egyszerű programozhatóság (nem bonyolult az algoritmus). Hátránya viszont az, hogy nagyon sok cserét kell végrehajtani, ez nagyon lassítja a rendezési időt. 1.2 Buborék rendezés A legegyszerűbben programozható rendezési eljárás. A tömböt az elejétől vizsgálva az egymás után következő elemeket hasonlítja össze. Ha olyat talál, hogy a második elem kisebb, mint az első, megcseréli a két elemet. Így a nagy elemek mint egy buborék haladnak a tömb vége felé, a helyükre. Ha eléri a tömb végét, újra indul elölről A rendezés akkor fejeződik be, ha az újraindulás után már nem történt egyetlen csere sem. Az előző algoritmussal szemben ez valamennyivel kevesebb cserét végez, de még mindig elég lassú. 1.3 Heap rendezés A heap rendezés alapvetően két külön algoritmuson alapul. Az első algoritmus egy

faszerkezetet hoz (ábra) létre. A tetején van a tömb legelső eleme, alatta van a 2 és a 3 és így tovább. Ennek a faszerkezetnék tetején az 1. elemet szülőcsomópontnak nevezzük, és a belőle kiágazók lesznek (2.,3) a gyerekcsomópontok Ezek természetesen a következő szintre nézve már szülőcsomópontok. A kialakításkor az algoritmus úgy rendez, hogy a szülőcsomópont elemei mindig nagyobbak legyenek a gyerekcsomópont elemeinél. A szülő-gyerek kapcsolat eldöntésére az algoritmus azt az egyszerű összefüggést használja, hogy az elemszámot elosztja kettővel, és veszi az egészrészét, és így a szülőcsomópont sorszámát kapjuk. Így haladva folyamatosan vizsgálja azt a feltételt, hogy kisebb-e a gyerek az apjánál, és ha nem, akkor kicseréli a két elemet egymással. De ilyenkor tovább kell vizsgálni, hogy a kicserélt helyen kisebb-e már a gyerek az apjánál. Ha igen, akkor folytathatjuk a rendezést ott, ahol az első csere

történt, ha nem, akkor folytatni kell a feltételvizsgálatokat és cseréket addig, amíg jó nem lesz a faszerkezetünk. Ha így teljesen jó már a faszerkezetünk, akkor az teljesen biztos, hogy a legelső elem a legnagyobb. Ezt kicseréljük a tömb legutolsó elemével majd a tömbméretet eggyel kisebbre vesszük. Itt kap szerepet a második algoritmus Ennek az a feladata, hogy ezzel a cserével "elrontott" faszerkezet visszaállítása. Ezt úgy teszi, hogy megnézi, hogy az 1. elem két gyereke közül melyik a nagyobb, azzal kicseréli az első elemet Majd megint megnézi, hogy a következő két gyereke közül melyik a nagyobb, és azzal kicseréli az apát. Ezt egészen addig kell folytatni, amíg újra helyre nem áll a faszerkezet, vagyis minden apa nagyobb lesz mind a két gyerekénél. Így most megint a legnagyobb elem van legfölül. Ezt most megint ki kell cserélni az csökkentett tömb legutolsó elememével, és csökkenteni még eggyel a

tömbméretet. Így most már két elemünk van jó helyen Ezt az eljárást addig kell folytatni, amíg az elemek rendezett állapotba nem kerülnek. Az előző algoritmusokhoz képest gyorsabb, de még mindig nagyon sok cserét végez. 1.4 Minimum kiválasztásos A tömb egészét vizsgálva megkeresi a legkisebb elemet, majd kicseréli a legelső elemmel. Aztán már a második elemtől kezdve megint megkeresi a legkisebb elemet, majd kicseréli a második elemmel. Ez is már aránylag gyorsan működik, előnye, hogy csak kevés cserét végez 1.5 Shell rendezés Ez a rendezés nagyon hasonló a buborékhoz. De itt nem egymás melletti elemeket vizsgál induláskor, hanem az offset távolságra lévőket hasonlítja össze. Kezdetben ez az offset érték a fele a tömbméretnek. Majd ha ebben a fél-offset távolságban már rendezve van a tömb (a legutolsó lépésben már nem volt csere), akkor ezt az offset értéket a felére csökkentjük, majd az előzőeket újra

elvégezzük. Ezt a műveletsort egészen addig kell ismételni, amíg az offset értéke lecsökken egyre (vagyis már hagyományos buborékrendezésről van szó), és már nem történik több csere. Ekkor a tömbünk rendezett 1.6 Quick rendezés A ma ismert talán leggyorsabb általános rendezési módszer. Lényege, hogy a tömbben kiválaszt egy tetszőleges elemet, és úgy rendezi, hogy ennek az egyik oldalán csak a nála kisebb, a másik oldalán csak a nála nagyobb elemek szerepeljenek. Majd újra meghívja saját magát (rekurzív függvényhívás), de ezúttal már nem a teljes tömb területén jelöl ki magának egy tetszőleges elemet, ami alá és fölé rendezi a számokat, hanem az előzőekben kijelölt számnál kisebb/vagy nagyobb számokat tartalmazó tömbrészben. Ezt addig ismétli, amíg már csak 2 elemű lesz ez a résztömb, és ezek az elemek a megfelelő sorrendben vannak. Ennek az algoritmusnak az egyik speciális problémája, hogy ha a

(rész)tömbben az X-edik elemet választom ki, akkor nem biztos, hogy abban a tömbben pontosan X-1 db nála kisebb elem lesz (vagyis nem férnek be elé a kisebb elemek). Ezért úgy működik, hogy elmenti ezt a bizonyos elemet a résztömb végére, majd elölről elkezdi vizsgálni, hogy minden elem kisebb-e nála. Ha talál egy nagyobb elemet (I), akkor megáll, és a végéről kezdi vizsgálni, hogy minden elem nagyobb-e nála. Ha talál egy kisebb elemet (J), akkor ezt a két elemet felcseréli egymással. Majd újra kezdi az elölről majd hátulról vizsgálást Ennek a ciklusnak akkor van vége, ha az I. nagyobb lesz, mint a J, vagyis az elemek a megfelelő sorrendben vannak (I alatt vannak a kisebb a számnál kisebb elemek, és J fölött vannak a nagyobb elemek). Ekkor kicseréli az I. elemet az utolsó helyre elmentett számmal, és így máris meg van oldva a feladat: a szám előtt sorakoznak a nála kisebb elemek, és mögötte a nála nagyobb elemek. 1.7 Egyéb

speciális rendezések Speciális esetekben kidolgozhatóak olyan eljárások, amelyek az adott esetben jól funkcionálnak, de általánosan nem működnek. Éppen ezért, mivel nem tudunk általánosan beszélni a speciális problémákról, egy példát mutatok be. Az űrfelvételek feldolgozásánál szükség van többek között az egyes sávok intenzitás értékeinek mediánjaira. Hagyományos esetben ennek a megkeresése úgy történne, hogy sorbarendezzük a tömböt, majd ebből kiválasztjuk a középső elemet. Sokkal egyszerűbben és gyorsabban elvégezhető ez a feladat, ha kihasználjuk azt, hogy azokon a műholdfelvételeken, amelyekkel mi szoktunk dolgozni, az egyes sávok intenzitás értékei mindig 0 és 255 közé eső egész számok. Létre kell hozni egy 256 elemű tömböt, és a képet végigvizsgálva ebbe a tömbbe csak azt írjuk be, hogy melyik intenzitás érték hányszor fordul elő (ez a lépés tulajdonképpen hisztogram készítésként is

felfogható). Azt tudjuk, hogy a képünkön összesen hány pixel van. A medián megkeresése annyiból áll, hogy a 256 elemű tömbünk elemeit sorra elkezdjük összeadogatni, és amely intenzitás értéknél az összeg meghaladja az összes pixel felét, azaz intenzitás érték a keresett medián. 1.8 Az egyes rendezési algoritmusok összehasonlítása Az algoritmusokat Basic programnyelvben megírt (a mellékletben megtalálható) programokkal hasonlítottam össze. Az egyes algoritmusok ugyan azt a rendezetlen tömböt rendezték. Ezek az értékek csak nagyságrendi tájékoztatást adnak, hiszen ha más hosszúságú, más rendezetlenségű tömböt kellett volna rendezni, ezek az értékek változnának az egyes algoritmusok működési elvének megfelelően. Továbbá befolyásolhatná ezeket az értékeket, ha más programnyelvben írnánk meg az egyes algoritmusokat. beszúrásos 55,973 mp buborék 51,188 mp heap 24,059 mp min.kiválasztásos 18,020 mp shell 11,098 mp

quick 8,184 mp 2.Keresési algoritmusok 2.1 Lineáris keresés A lineáris keresés alkalmazható mind rendezett, mind rendezetlen listában. Lényege, hogy az első elemtől kezdve egyesével folyamatosan megvizsgál minden elemet, hogy azonos-e a keresettel. Kis adatbázisok esetében még aránylag hatékonyan alkalmazható, de nagyobb adatbázisok esetén nagyon megnő a keresési idő. Igaz ugyan, hogy szélsőséges esetben (az első pár elem között van a keresett) akár gyorsabb is lehet, mint a következőkben ismertetésre kerülő binális keresés, de ez nem jellemző. 2.2 Binális keresés Kizárólag rendezett listákban alkalmazható keresési módszer. Működése jól szemléltethető a kereső fán. A fa legtetején a rendezett lista középső eleme található Innen két elágazás indul ki, az egyiknek a végén a fa tetején lévő elem által két részre osztott lista egyikének a középső eleme, a másik végén a másik fél rendezett lista középső

eleme található. Ezekből az ágakból újabb 2-2 ág indul ki, amelyek végén található értékeket az előzőek analógiájára képezzük. Majd ezekből is ugyanilyenek, egészen addig, amíg már nem tudjuk tovább osztani a rendezett listánkat. Az alábbi ábrán egy 30 elemből álló tömb kereső fáját ábrázoltam A keresést a fa tetejéről kell indítani. Meg kell nézni, hogy a keresett elem kisebb vagy nagyobb-e mint a fa tetején lévő elem. Ha kisebb balra lefelé, ha nagyobb balra lefelé kell folytatni a keresést. Ha nem is kisebb, és nem is nagyobb, az azt jelenti, hogy egyenlő, tehát megvan a keresett elemünk. A fa megfelelő ágán elindulva azt vizsgáljuk, hogy a fa ágán következő elemnél a keresett elem kisebb vagy nagyobb a keresett elemnél, és az előzőek analógiájára jobbra vagy balra lefelé folytatjuk az utat. Ezt a műveletet addig kell ismételni, amíg el nem jutunk a keresett elemhez. A módszer egyik előnye, hogy azonos

adatbázis esetén akármelyik elemre is keresünk, a lépések száma nem halad meg egy bizonyos számot (a fa szintjeinek a számát, ami a kettő annyiadik hatványa, amelyik már nagyobb, mint a tömb elemeinek a száma), míg lineáris keresés esetén szélsőséges esetben a keresési lépések száma megegyezhet a tömb elemeinek számával. 2.3 Más kereső fák Olyan esetekben, hogyha az egyes elemek nem azonos gyakorisággal fordulnak elő, asszimetrikus kereső fákat alkalmazhatunk. Ilyenkor a tartományokból nem mindig a középső elemet választjuk ki, hanem a súlyoknak megfelelő optimális elemet. Ezeknek a fáknak az optimalizálása igen hosszadalmas és bonyolult feladat. Egy ilyenre mutat példát az alábbi ábra (a szavak alatt lévő szám az előfordulási gyakoriságot jelzi). Nem szimmetrikus kereső fákat fel tudunk állítani nem rendezett lista alapján is. Itt a fa tetejére egy tetszőlegesen kiválasztott elemet teszünk (általában a tömb

első elemét), és ebből fejlesztjük tovább a fát. Ennek az lehet a problémája, hogy elfajul a fa, és már csak lineáris keresésként működik, de nagy elemszám esetén ennek nagyon kicsi a valószínűsége. Ez különösen láncolt listák esetében alkalmazható jól, mert új elemeket tudunk könnyedén beszúrni, a tömb újrarendezése nélkül. Irodalomjegyzék Gács-Lovász Algoritmusok D.EKnuth A számítógép programozás művészete (IIIkötet) Qbasic demofile-ok Melléklet InsertionSort SUB InsertionSort STATIC DIM TempVal AS SortType FOR Row = 2 TO MaxRow TempVal = SortArray(Row) TempLength = TempVal.Length FOR J = Row TO 2 STEP -1 As long as the length of the J-1st element is greater than the length of the original element in SortArray(Row), keep shifting the array elements down: IF SortArray(J - 1).Length > TempLength THEN SortArray(J) = SortArray(J - 1) Otherwise, exit the FOR.NEXT loop: ELSE EXIT FOR END IF NEXT J Insert the original value of

SortArray(Row) in SortArray(J): SortArray(J) = TempVal NEXT Row END SUB BubbleSort SUB BubbleSort STATIC Limit = MaxRow DO Switch = FALSE FOR Row = 1 TO (Limit - 1) Two adjacent elements are out of order, so swap their values and redraw those two bars: IF SortArray(Row).Length > SortArray(Row + 1)Length THEN SWAP SortArray(Row), SortArray(Row + 1) Switch = Row END IF NEXT Row Sort on next pass only to where the last switch was made: Limit = Switch LOOP WHILE Switch Heap SUB HeapSort STATIC FOR I = 2 TO MaxRow PercolateUp I NEXT I FOR I = MaxRow TO 2 STEP -1 SWAP SortArray(1), SortArray(I) PercolateDown I - 1 NEXT I END SUB PercolateDown SUB PercolateDown (MaxLevel) STATIC I=1 Move the value in SortArray(1) down the heap until it has reached its proper node (that is, until it is less than its parent node or until it has reached MaxLevel, the bottom of the current heap): DO Child = 2 * I Get the subscript for the child node. Reached the bottom of the heap, so exit this

procedure: IF Child > MaxLevel THEN EXIT DO If there are two child nodes, find out which one is bigger: IF Child + 1 <= MaxLevel THEN IF SortArray(Child + 1).Length > SortArray(Child)Length THEN Child = Child + 1 END IF END IF Move the value down if it is still not bigger than either one of its children: IF SortArray(I).Length < SortArray(Child)Length THEN SWAP SortArray(I), SortArray(Child) SwapBars I, Child I = Child Otherwise, SortArray has been restored to a heap from 1 to MaxLevel, so exit: ELSE EXIT DO END IF LOOP END SUB PercolateUp SUB PercolateUp (MaxLevel) STATIC I = MaxLevel Move the value in SortArray(MaxLevel) up the heap until it has reached its proper node (that is, until it is greater than either of its child nodes, or until it has reached 1, the top of the heap): DO UNTIL I = 1 Parent = I 2 Get the subscript for the parent node. The value at the current node is still bigger than the value at its parent node, so swap these two array elements:

IF SortArray(I).Length > SortArray(Parent)Length THEN SWAP SortArray(Parent), SortArray(I) SwapBars Parent, I I = Parent Otherwise, the element has reached its proper place in the heap, so exit this procedure: ELSE EXIT DO END IF LOOP END SUB Shell SUB ShellSort STATIC Set comparison offset to half the number of records in SortArray: Offset = MaxRow 2 DO WHILE Offset > 0 Loop until offset gets to zero. Limit = MaxRow - Offset DO Switch = FALSE Assume no switches at this offset. Compare elements and switch ones out of order: FOR Row = 1 TO Limit IF SortArray(Row).Length > SortArray(Row + Offset)Length THEN SWAP SortArray(Row), SortArray(Row + Offset) Switch = Row END IF NEXT Row Sort on next pass only to where last switch was made: Limit = Switch - Offset LOOP WHILE Switch No switches at last offset, try one half as big: Offset = Offset 2 LOOP END SUB Quick SUB QuickSort (Low, High) IF Low < High THEN Only two elements in this subdivision; swap them if they

are out of order, then end recursive calls: IF High - Low = 1 THEN IF SortArray(Low).Length > SortArray(High)Length THEN SWAP SortArray(Low), SortArray(High) END IF ELSE Pick a pivot element at random, then move it to the end: RandIndex = RandInt%(Low, High) SWAP SortArray(High), SortArray(RandIndex) SwapBars High, RandIndex Partition = SortArray(High).Length DO Move in from both sides towards the pivot element: I = Low: J = High DO WHILE (I < J) AND (SortArray(I).Length <= Partition) I=I+1 LOOP DO WHILE (J > I) AND (SortArray(J).Length >= Partition) J=J-1 LOOP If we havent reached the pivot element, it means that two elements on either side are out of order, so swap them: IF I < J THEN SWAP SortArray(I), SortArray(J) END IF LOOP WHILE I < J Move the pivot element back to its proper place in the array: SWAP SortArray(I), SortArray(High) Recursively call the QuickSort procedure (pass the smaller subdivision first to use less stack space): IF (I - Low) <

(High - I) THEN QuickSort Low, I - 1 QuickSort I + 1, High ELSE QuickSort I + 1, High QuickSort Low, I - 1 END IF END IF END IF END SUB Binális keresés rendezett tömbben FUNCTION binker (elem) i1 = 0: i2 = 10 elso elem es max. elemszam, T tombben DO IF i1 > i2 THEN binker = -1: EXIT FUNCTION Nincs talalat p = INT((i1 + i2) / 2) IF T(p) < elem THEN i1 = p + 1 ELSEIF T(p) > elem THEN i2 = p - 1 END IF LOOP UNTIL T(p) = elem binker = p END FUNCTION