Programming | Delphi » Fábián Zoltán - Szoftvertechnológia I. tételek

A Maxmin eljárás Feladat: adott egy sorozat. Válasszuk ki a legnagyobb és a legkisebb elemét! 1. megoldás: a minimum –és a maximumkeresés tételének alkalmazása 2. megoldás: a Maxmin eljárás Algoritmus Eljárás Maxmin2(A, max, min) Max=A(1) Min=A(1) Ciklus i=2-től n-ig Ha A(i)>max akkor max=A(1) Különben Ha A(i)<min akkor min=A(i) Eljárás vége Eljárás MM(A, B, max, min) Ha A>B akkor max=A min=B Különben max=B min=A Eljárás vége Eljárás Maxmin3(A,max,min) Ha n páros akkor MM(A(1), A(2), max, min) Ciklus i=3-tól n-1-ig (2-esével) MM(A(i),A(i+1),b,a) Ha a<min akkor min=a Ha b>max akkor max=b Ciklus vége Ha vége Különben max=A(1) és min=A(i) ciklus j=2-től n-1-ig (2-esével) MM(A(i), A(i+1), b, a) Ha (a<min) akkor min=a Ha b>max akkor max=b Ciklus vége Különben vége Eljárás vége 4. A Bingo-rendezés Eljárás MaxMin3 (L, MaxValue, MinValue) Bingo=MinValue NextAvail=1 NextBingo=MaxValue //Min és Max érték Ciklus

amíg Bingo<MaxValue StartPos=NextAvail Ciklus i=Startpos to n do //annyiszor fut le, ahány különböző elem van Ha L[i]=Bingo akkor //A belső rész a kicsi elemeket egyből a helyére rakja csere(L[i],L[NextAvail]) //nem veszi észre, ha a tömb rendezett inc(NextAvail) különben ha L[i]<NextBingo akkor //az aktuális min beállítása //m x n -el arányos lépésszám (maximum m2+n) NextBingo=L[i] ciklus vége //1<m<<n esetben működik jól Bingo=NextBingo NextBingo=MaxValue ciklus vége eljárás vége Eljárás MergeSort (L, Low, High) Ha Low<High akkor Mid = ((Low+High)/2) //az alsó egészrész MergeSort(L,Low,Mid) MergeSort(L,Mid+1,High) MergeSort(L,Low,Mid,High) eljárás vége Eljárás Merge (L,Low,X,High) C1=Low C2=x+1 Count=Low //az ideiglenes tömb indexét jelöli ki ciklus amíg (C1<X) és (C2<=High) Ha L[C1]<=L[C2] akkor Temp(count)=L[C1] inc(C1) különben Temp(count)=L[C2] C2=C2+1 inc(count) ciklus vége //valamelyik tömbrészlet

elfogyhat //Ha C1>X, akkor az első tömbrészlet elemei a helyükön vannak, //a ciklus a temp tömbbe másolja a második megmaradt elemeit //a maradék elemek között van egy, amely az előző legnagyobb //eleménél is nagyobb Ha C1>X akkor Ciklus k=C2 to High do Temp(count)=L[k] inc(count) ciklus vége különben ciklus k=C1 to X do Temp(count)=L[k] inc(count) ciklus vége ciklus k=Low to High do L[k]=Temp(k) ciklus vége Eljárás vége //kiindulásként a két résztömb rendezett volt //A már feldolgozott tömbrészt visszamásoljuk a helyére //A merge összefűzi az elemeket (rendezett összefűzés) 5. A Shell-rendezés Alapötlet: jó, ha az elemek gyorsan a helyük közelébe kerülnek. Például először minden hetediket, majd minden másodikat, stb. rendezzük, egy rendezési algoritmussal (átlagosan n/2 idő alatt) Algoritmus eljárás Shell(L,D) ciklus i=1 to n do Beilleszteses(L,D[i]) ciklus vége eljárás vége eljárás Beilleszteses(L,K) //K

– ahányadik elemmel kell dolgozni //K-val visszafelé lépked, amíg el nem éri az egyet ciklus i=k+1 to n do C=L[i] //C a korlátozó változó pos=i-k //Ha k helyére 1-et írunk, megkapjuk a sima beill. rendezést ciklus amíg (pos>=1) és (C<L[pos]) L[pos+k]=L[pos] pos=pos-k ciklus vége L[pos+k]=c ciklus vége eljárás vége 6. A Radix-rendezés Mindegyik elemet (x) a megfelelő helyre tesszük egy tömbben (T): (T[x]). Ha a beszúrandó elemből már van a tömbben, az adott elem után láncoljuk. Tegyük fel, hogy mindegyik elem ugyanolyan hosszú (számjegyek, betűk). A rendezendő sorozat: 45242, 45230, 97432, 74239, 12335, 43239, 40122, 98773, 41123, 61230 Az elemeket az utolsó karakterük szerint rendezzük sorba. Tehát, ha az utolsó karakter 0, akkor a nulladik helyre kerül a tömbben. Ahova több elem kerül, azokat fűzzük láncba, majd írjuk le a sorozatot: 45230, 61230, 45242, 97432, 40122, 98773, 41123, 12335, 74239, 43239 Ugyanígy hátulról

előrefelé haladva, az első számjegyig: 40122, 41123, 45230, 61230, 97432, 12335, 74239, 43239, 45242, 98773 40122, 41123, 45230, 61230, 74239, 43239, 45242, 12335, 97432, 98773 . 12335, 40122, 41123, 43239, 45230, 45242, 61230, 74239, 97432, 98773 Megjegyzések: • Elölről hátrafelé haladva nem működne • Különböző hosszú számok esetén először hosszuk szerint kell őket sorba rendezni I. Algoritmus (összesen n+m művelet) Ha (a1, a2, , an) számok (0m-1) között vannak: 1. Az összes (0m-1) számhoz vegyünk fel egy üres sort 2. Balról jobbra végighaladva a1an számokon, helyezzük az ai elemet az i-edik sorba 3. Kapcsoljuk össze a sorokat II. Azonos hosszúságú számok esetén Bemenet: A1An sorozat, amelyben minden Ai pontosan k hosszú. Az Ai sorok 0m-1 közé esnek. Kimenet: B1Bn sorozat, ami A1An sorozat egy permutációja. 1 ≤ i ≤ n –re Bi ≤ Bi+1 Algoritmus Eljárás Tegyük A1.An-t a SOR-ba ciklus j=k to 1 (-1-esével) do ciklus L=0-tól M-ig

kiürítés(Q[L]) ciklus vége ciklus amíg a SOR nem üres inc(i) Legyen Ai a SOR első eleme Tegyük az Ai SORból Q[aij] helyre ciklus vége ciklus L=0 to M-1 do csatoljuk a SOR végére: Q[L] ciklus vége ciklus vége eljárás vége III. Különböző hosszúságú láncok lexikografikus rendezése Algoritmus Eljárás ürítsük ki a SOR-t ciklus j=0 to m-1 do ürítés (Q[j]) ciklus vége ciklus L=Lmax to 1 (-1-esével) do Hosszúság(L) csatolása a SOR elejére ciklus amíg a SOR nem üres Ai legyen első a SOR-ban Tegyük Ai elemet a Q[aij] helyre ciklus vége ciklus minden j-re és nem üres L-re csatoljuk Q[J] elemet a SOR végére kiürítés (Q[J]) ciklus vége ciklus vége Eljárás vége 5. A Kupacrendezés A Kupac A (bináris) kupac adatszerkezet úgyis szemlélhető, mint egy majdnem teljes bináris fa egy tömbben reprezentálva. A fa minden csúcsa megfelel tömb egy elemének, mely a csúcs értekét tárolja. A fa minden szintjén teljesen kitöltött,

kivéve a legalacsonyabb szintet, ahol balról jobbra haladva csak egy adott csúcsig vannak elemek. Az A tömbhöz, mely egy kupacot alkot, két tulajdonságot rendelünk: hossz[A], mely a tömb elemeinek száma. és kupac-méret[A], mely az A tömbben tárolt kupac elemeinek száma. Így, jóllehet A[1 hossz[A]] minden eleme értékes adatot tartalmaz, 1[kupac-méret[A]] utáni értékek, ahol kupac-méret[A] < hossz[A]. már nem tartoznak a kupachoz. A fa gyökere A[1], és ha i a fa egy adott csúcsának tömbbeli indexe, akkor az ősének Szülő(i), baloldali gyerekének BAL(i), és jobboldali gyerekének JOBB(i) indexe egyszerűen kiszámítható: SZÜLŐ(i) return [i/2] BAL(i) return 2i JOBB(i) return 2i + 1 7.1 ábra A kupac mint bináris fa (a) és mint tömb (b) A körök belsejébe írt szám a fa csúcsához tartozó érték, a kör mellé írt szám a csúcsnak megfelelő tömbelem indexe. A kupac minden i, gyökértől különböző elemére igaz a következő kupac

tulajdonság: A[SzüLő(i)] > A[i] azaz az elem értéke kisebb vagy egyenlő mint a szülőjének értéke. Így a kupac legnagyobb eleme a gyökér és egy adott csúcs alatti részfa minden elemének értéke kisebb vagy egyenlő az adott csúcsban lévő elem értékénél. A fa egy elemének a magassága legyen azon leghosszabb út éleinek a száma, mely az adott csúcshól egy levélhez vezet, a fa magassága legyen a gyökérelem magassága. A kupacon végzett alapműveletek végrehajtási ideje a fa magasságával, azaz O(lg n)-nel arányos. A kupac tulajdonság fenntartása A KUPACOL eljárás fontos a kupacok kezeléséhez. Bemenő adatai az A tömb, és annak egy indexe i. A KUPACOL meghívásakor feltesszük, hogy a BAL(i) és JOBB(i) gyökerű részfák kupac szerkezetűek, de A[i] kisebb lehet a gyerekeinél, így megsértheti a kupac tulajdonságot. A KUPACOL feladata, hogy A[i] értéket „lefelé mozgassa" úgy, hogy az i gyökerű részfa kupaccá

alakuljon. KUPACOL(A, i) L = BAL(i) R = JOBB(i) if (L < kupac-méret[A]) és (A[L] > A[i]) then legnagyobb = L else legnagyobb = i if (R ≤ kupac-méret[A]) és (A[R] > A[legnagyobb]) then legnagyobb = R if legnagyobb ≠ i then csere (A[i], A[legnagyobb]) KUPACOL(A,legnagyobb) (a) (b) (c) A KUPACOL(A, 2) működése, ahol kupac-méret[A] = 10. (a) Kiinduláskor A[2] az i = 2es csúcsnál sérti a kupac tulajdonságot, mivel nem nagyobb a gyerekeinél. A kupac tulajdonságot helyreállítjuk a 2-es csúcsra nézve (b) azzal, hogy A[2] és A[4] elemeket felcseréljük, de elrontjuk a 4-es csúcsra nézve. A KUPACOL(A,4) rekurzív hívása i-t 4-re állítja. A[4] és A[9] felcserélése után, ahogy azt (c) mutatja, a 4 értékű elem helyére kerül, és a KUPACOL(A,9) rekurzív hívás már nem talál változtatni valót az adatszerkezeten. Az ábra KUPACOL eljárás működését mutatja be. Minden lépésnél meghatározzuk A[i], A[BAL(i)] és A[JOBB(i)] közül a

legnagyobbat, és indexét a legnagyobb nevű változóba tesszük. Ha A[i] a legnagyobb, akkor az i gyökerű részfa kupac és az eljárásnak vége Egyébként a két gyerek valamelyike a legnagyobb elem, ezért A[i]-t felcseréljük A[legnagyobb]-bal, így az i csúcs és gyerekei kielégítik a kupac tulajdonságot. A legnagyobb indexű csúcs felveszi az eredeti A[i] érléket, ezért a legnagyobb gyökerű részfa sértheti a kupac tulajdonságot. Következésképpen a KUPACOL eljárást rekurzívan újra meg kell hívni erre a részfára. A kupac építése A KUPACOL eljárást felhasználhatjuk, hogy az A[1. n] tömböt, ahol n = hossz[A] alulról felfelé haladva kupaccá alakítsuk. Minthogy az A tömb A[([n/2] + 1) n] elemei levelek, egyelemű kupacnak vehetők. A KUPACOT-ÉPÍT eljárásnak tehát csak a többi csúcson kell végighaladnia, és minden egyes csúcsra lefuttatni a KUPACOL eljárást. A csöcspontok feldolgozási sorrendje garantálja, hogy mikor egy i

csúcsra lefuttatjuk a KUPACOL eljárást annak gyerekei már kupacot alkotnak. A KUPACOL futási ideje függ a csúcs magasságától a fában, ami a csúcsok többségére kicsi. KUPACOT-ÉPÍT(A) kupac-méret[A] = hossz[A] for i = hossz└A]/2 ┘ downto 1 do KUPACOL(A,i) //└az alsó egész rész┘ A KUPACOT-ÉPÍT működése. Az ábra mutatja az adatszerkezetet KUPACOL meghívása előtt (KUPACOTÉPÍT 3 sor)(a) Adott egy 10 elemű A tömb, melyet egy bináris fa ábrázolásának tekintünk Mint az ábrán látjuk, i ciklusváltozó az 5. csúcsra mutat a KUPACOL(A, i) hívásakor (b) ábrázolja az eredményt, ekkor i ciklusváltozó már a 4. csúcsra mutat (c)-(e) a for ciklus egymást követő iterációit szemlélteti Figyeljük meg, hogy a KUPACOL adott csúcsra való meghívásakor a csúcs alatti két részfa már kupac. (f) mutatja a KUPACOT-ÉPÍT tevékenységének végeredményét. A kupacrendezés algoritmus Az algoritmus a KUPACOT-ÉPÍT meghívásával

kezdődik, mely kupaccá alakítja az A[1 . n] bemenő tömböt, ahol n = hossz[A]. A kupac tulajdonság miatt a legnagyobb elem a gyökérelem, tehát ha felcseréljük A[1] és A[n] elemeket, a legnagyobb elem a rendezés szerinti helyére kerül. Az n elemet kizárva a kupacból (kupac-méret[A]-t eggyel csökkentve), a maradék A[1. (n - 1)] elemet ismét könnyen kupaccá alakíthatjuk, ugyanis a gyökér gyerekeihez tartozó részfák kupac tulajdonságúak (71), csak a gyökérbe került elem sértheti azt KUPACOL(A, 1) hívásával helyreállíthatjuk a kupac tulajdonságot az A[1. (n - 1)] tömbön Ezt ismételjük a kupac méretét csökkentve n - 1-től 2-ig. A KUPACRENDEZÉS futási ideje O(n lg n), minthogy a KUPACOT-ÉPIT 0(n) idő alatt fut, és a KUPACOL eljárás minden egyes, n - l-szer történő lefutása O(lg n) idejű. KUPACRENDEZÉS(A) KUPACOT-ÉPÍT(A) for i = hossz [A] downto 2 do csere( A[1], A[i]) kupac-méret[A] = kupac-méret[A] - 1 KUPACOL(A, 1) A

KUPACRENDEZÉS működése. (a) A KUPACOT-ÉPÍT eljárás által felépített kupac adatszerkezet. (b)-(j) az adatszerkezet KUPACOL egy-egy futása után (algoritmus 5 sor) Az ábra mutatja i változó pillanatnyi értékét. A kupacban csak a világos körben lévő elemek maradtak. (k) Az eredményül kapott rendezett A tömb 66666 Megjegyzések • Tömbös ábrázolás esetén a közvetlen címzés miatt egyszerű és gyors adatszerkezet • Az olyan részfa, amely csak egy levélből áll, önmagában kupac